Prof. Bodik CS 164 Lecture 18 1Automatic Memory ManagementLecture 18Prof. Bodik CS 164 Lecture 18 2Lecture Outine• Why Automatic Memory Management?• Garbage Collection• Three Techniques– Mark and Sweep–Stop and Copy– Reference CountingProf. Bodik CS 164 Lecture 18 3Why Automatic Memory Management?• Storage management is still a hard problem in modern programming• C and C++ programs have many storage bugs– forgetting to free unused memory– dereferencing a dangling pointer– overwriting parts of a data structure by accident– and so on...• Storage bugs are hard to find– a bug can lead to a visible effect far away in time and program text from the sourceProf. Bodik CS 164 Lecture 18 4Type Safety and Memory Management• Some storage bugs can be prevented in a strongly typed language– e.g., you cannot overrun the array limits• Can types prevent errors in programs with manual allocation and deallocation of memory?– Some fancy type systems (linear types) were designed for this purpose but they complicate programming significantly• If you want type safety then you must use automatic memory management Prof. Bodik CS 164 Lecture 18 5Automatic Memory Management• This is an old problem: – Studied since the 1950s for LISP• There are several well-known techniques for performing completely automatic memory management• Until recently they were unpopular outside the Lisp family of languages– just like type safety used to be unpopularProf. Bodik CS 164 Lecture 18 6The Basic Idea• When an object that takes memory space is created, unused space is automatically allocated– In Decaf, new objects are created by new X• After a while there is no more unused space• Some space is occupied by objects that will never be used again• This space can be freed to be reused laterProf. Bodik CS 164 Lecture 18 7The Basic Idea (Cont.)• How can we tell whether an object will “never be used again”?– In general it is impossible to tell– We will have to use a heuristic to find many (not all) objects that will never be used again• Observation: a program can use only the objects that it can find:x = new A(); x = y;–After x = y there is no way to access the newly allocated objectProf. Bodik CS 164 Lecture 18 8Garbage•An object x is reachableif and only if:– A register contains a pointer to x, or– Another reachable object y contains a pointer to x• You can find all reachable objects by starting from registers and following all the pointers• An unreachable object can never by referred by the program– These objects are called garbageProf. Bodik CS 164 Lecture 18 9Reachability is an Approximation• Consider the program:x = new A();y = new B();x = y;if alwaysTrue() { x = new A() } else { x.foo(); }•After x = y (assuming y becomes dead there)– The object A is not reachable anymore– The object B is reachable (through x)– Thus B is not garbage and is not collected– But object B is never going to be usedProf. Bodik CS 164 Lecture 18 10Tracing Reachable Values in Decaf• In a simple implementation of Decaf, the only register is the accumulator– it points to an object– and this object may point to other objects, etc.•The stack is more complex– each stack frame contains pointers• e.g., method parameters– each stack frame also contains non-pointers• e.g., return address– if we know the layout of the frame we can find the pointers in itProf. Bodik CS 164 Lecture 18 11A Simple Example• We start tracing from acc and stack– they are called the roots• Note that B and D are not reachable from acc or the stack• Thus we can reuse their storageABCFrame 1Frame 2D EaccSPProf. Bodik CS 164 Lecture 18 12Elements of Garbage Collection• Every garbage collection scheme has the following steps1. Allocate space as needed for new objects2. When space runs out:a) Compute what objects might be used again (generally by tracing objects reachable from a set of “root” registers)b) Free the space used by objects not found in (a)• Some strategies perform garbage collection before the space actually runs outProf. Bodik CS 164 Lecture 18 13Mark and Sweep• When memory runs out, GC executes two phases– the mark phase: traces reachable objects– the sweep phase: collects garbage objects• Every object has an extra bit: the mark bit– reserved for memory management– initially the mark bit is 0– set to 1 for the reachable objects in the mark phaseProf. Bodik CS 164 Lecture 18 14Mark and Sweep ExampleABCD Froot Efree000000ABCD Froot Efree10 1 001After mark:ABCD Froot Efree000000After sweep:Prof. Bodik CS 164 Lecture 18 15The Mark Phaselet todo = { all roots }while todo ≠∅dopick v ∈ todotodo ← todo - { v }if mark(v) = 0 then (* v is unmarked yet *)mark(v) ← 1let v1,...,vnbe the pointers contained in vtodo ← todo ∪ {v1,...,vn}fiodProf. Bodik CS 164 Lecture 18 16The Sweep Phase• The sweep phase scans the heap looking for objects with mark bit 0– these objects have not been visited in the mark phase–they are garbage• Any such object is added to the free list• The objects with a mark bit 1 have their mark bit reset to 0Prof. Bodik CS 164 Lecture 18 17The Sweep Phase (Cont.)/* sizeof(p) is the size of block starting at p */p ← bottom of heapwhile p < top of heap doif mark(p) = 1 then mark(p) ← 0elseadd block p...(p+sizeof(p)-1) to freelistfip ← p + sizeof(p)odProf. Bodik CS 164 Lecture 18 18Details• While conceptually simple, this algorithm has a number of tricky details– this is typical of GC algorithms• A serious problem with the mark phase– it is invoked when we are out of space– yet it needs space to construct the todo list– the size of the todo list is unbounded so we cannot reserve space for it a prioriProf. Bodik CS 164 Lecture 18 19Mark and Sweep: Details• The todo list is used as an auxiliary data structure to perform the reachability analysis• There is a trick that allows the auxiliary data to be stored in the objects themselves– pointer reversal: when a pointer is followed it is reversed to point to its parent• Similarly, the free list is stored in the free objects themselvesProf. Bodik CS 164 Lecture 18 20Mark and Sweep. Evaluation• Space for a new object is allocated from the new list– a block large enough is picked– an area of the necessary size is allocated from it– the left-over is put back in the free list•
View Full Document
Unlocking...