Memory ManagementModes of Object ManagementSlide 3Slide 4Slide 5Programmer Controlled DeallocationAutomatic Memory ManagementReference counting(cont)Garbage CollectionReachability is an ApproximationSoundness issue : C++ ProblemMark and Sweep AlgorithmMark phase : Using an explicit stackSweep phaseMark and Sweep ExampleCopying CollectionStop and Copy GC: ExampleImplementation of Stop and CopyImplementation of Stop and Copy (Cont.)Stop and Copy. Example (1)Stop and Copy. Example (2)Stop and Copy. Example (3)Stop and Copy. Example (4)Stop and Copy. Example (5)Stop and Copy. Example (6)Generational CollectorsGenerational Garbage CollectionPractical IssuesMemory Leakage in Java (Unintended References)Slide 32Other Java Detailsceg860 (Prasad) L9GC 1Memory ManagementGarbage Collectionceg860 (Prasad) L9GC 2Modes of Object Management•Static * An entity may become attached to at most one run-time object during the entire execution.•E.g., FORTRAN variables.+ Simple and Efficient.–Precludes recursion.–Precludes dynamic data structures.–Note, FORTRAN 90 supports recursion and pointers.ceg860 (Prasad) L9GC 3•Stac k-ba sed* An entity may at run-time become attached to several objects in succession, and the allocation and deallocation of these objects is in last-in first-out discipline.•E.g., Pascal, C/C++, Java, etc.+ Well-matched with block-structuring.+ Allocation and Deallocation automatic.+ Supports recursion.+ Supports Ada “unconstrained” array types, etc.–Does not support flexible data structures.ceg860 (Prasad) L9GC 4•Heap-based* Objects are created dynamically through explicit requests.•E.g., C++, LISP, Java/C#, etc.+ Enables construction of complex dynamic data structures (with “unpredictable” lifetimes).–Requires techniques for memory reclamation. •Objects may become unreachableunreachable as a result of an assignment or a method-return. •Even systems with large virtual memory can thrash if memory is not recycled.ceg860 (Prasad) L9GC 5ceg860 (Prasad) L9GC 6Programmer Controlled Deallocation•Using language primitives•E.g., Pascal’s dispose, C’s free, C++’s delete, C++ destructors, etc.–Reliability issue•Dangling reference problem (“premature freeing”)•Memory Leakage (“incomplete recycling”)–Ease of software development issue•Component-level approachceg860 (Prasad) L9GC 7Automatic Memory Management Language implementation techniques (run-time system)•Reference counting–Restricted to acyclic data structures.•Garbage collection+ Applicable to general dynamic data structures.–Unsuitable in certain areas such as hard real-time systems.ceg860 (Prasad) L9GC 8Reference counting•Keep count of number of references to each object.•Update the count in response to operations.–initialize : create/clone –increment : assignment, method call–decrement : assignment, method return.ceg860 (Prasad) L9GC 9(cont)•Limitations •Space/time overhead to maintain count. •Memory leakage when cycles in data.•Advantage•Incremental algorithm•Applications •UNIX File System - Symbolic Links•Java RMI, Strings, COM/DCOM•Pure Functional Languages•Scripting Languages : Python, PERL, etcceg860 (Prasad) L9GC 10Garbage Collection•Detecting and reclaiming unreachable objects automatically.•Soundness / Safety•Every collected object is unreachable.•Completeness•Every unreachable object is eventually collected.ceg860 (Prasad) L9GC 11Reachability is an Approximation•Consider the program: x  new A; y  new B; x  y; if alwaysTrue() then x  new A else x.foo() fi•After x  y (assuming y becomes dead there)•the initial 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 usedceg860 (Prasad) L9GC 12Soundness issue : C++ Problemvoid main(void){ Point *aptr = new Point(); // casting an object reference to an int int i = (int) aptr;int i = (int) aptr; // normal access to an object and its fields aptr->print(); aptr->printxy(); // freeing an object and nulling a reference to it delete(aptr);delete(aptr); aptr = NULL; aptr->print();// segmentation fault only when the object fields are accessed // aptr->printxy(); // casting the int back to object reference aptr = (Point*) i;aptr = (Point*) i; // object resurrected !!aptr->print(); aptr->printxy();}ceg860 (Prasad) L9GC 13Mark and SweepMark and Sweep Algorithm•Garbage Detection•Depth-first search to mark live data cells (cells in heap reachable from variables on run-time stack).•Garbage Reclamation•Sweep through entire memory, putting unmarked nodes on freelist. Sweep also unmarks the marked nodes.ceg860 (Prasad) L9GC 14Mark phase : Using an explicit stackfunction DFS(r) if r is a reference and object r not marked then { mark object r; t <- 1; stack[t] <- r; while (t > 0) { p <- stack[t--]; foreach field p.fi do { if p.fi is a reference and object p.fi not marked then { mark object p.fi; stack[++t] <- p.fi }}}}ceg860 (Prasad) L9GC 15Sweep phasep <- first address in heap;while (p < last address in heap) { if marked object p then unmark object p else { let f be the first field in object p; p.f <- freelist; freelist <- p; } p <- p + (size of object p)}ceg860 (Prasad) L9GC 16Mark and Sweep ExampleAB C D Froot Efree00 0 0 0 0AB C D Froot Efree10 1 0 0 1After mark:AB C D Froot Efree00 0 0 0 0After sweep:ceg860 (Prasad) L9GC 17 •Problems–Memory Fragmentation.–Work proportional to size of heap.–Potential lack of locality of reference for newly allocated objects (fragmentation).•Solution–Compaction–Contiguous live objects, contiguous free spaceceg860 (Prasad) L9GC 18Copying Collection •Divide heap into two “semispaces”. •Allocate from one space (fromspace) till full.•Copy live data into other space (tospace).•Switch roles of the spaces.•Requires fixing pointers to moved data (forwarding).•Eliminates fragmentation.•DFS improves locality, while BFS does not require any extra storage.ceg860 (Prasad) L9GC 19Stop and Copy GC: ExampleAB C D Froot EBefore collection:new spaceA C Frootnew spaceAfter collection:freeheap pointerceg860 (Prasad) L9GC 20Implementation of Stop and Copy•We find and copy all the reachable objects into the new space, and fix ALL pointers pointing to moved objects!•As we copy an object, we store in the old copy a