CMSC 330: Organization of Programming Languages Garbage Collection CMSC 330 - Spring 2011 1CMSC 330 - Spring 2011 2 Memory Attributes ! Memory to store data in programming languages has several attributes • Persistence (or lifetime) How long the memory exists • Allocation When the memory is available for use • Recovery When the system recovers the memory for reuseCMSC 330 - Spring 2011 3 Memory Attributes (cont.) ! Most programming languages are concerned with some subset of the following 4 memory classes 1. Fixed (or static) memory 2. Automatic memory 3. Programmer allocated memory 4. Persistent memoryCMSC 330 - Spring 2011 4 Memory Classes ! Static memory – Usually a fixed address in memory • Persistence – Lifetime of execution of program • Allocation – By compiler for entire execution • Recovery – By system when program terminates ! Automatic memory – Usually on a stack • Persistence – Lifetime of method using that data • Allocation – When method is invoked • Recovery – When method terminatesCMSC 330 - Spring 2011 5 Memory Classes (cont.) ! Allocated memory – Usually memory on a heap • Persistence – As long as memory is needed • Allocation – Explicitly by programmer • Recovery – Either by programmer or automatically (when possible and depends upon language)CMSC 330 - Spring 2011 6 Memory Classes (cont.) ! Persistent memory – Usually the file system • Persistence – Multiple execution of a program E.g., files or databases • Allocation – By program or user Often outside of program execution • Recovery – When data no longer needed • Dealing with persistent memory → databases CMSC 424CMSC 330 - Spring 2011 7 Memory Management in C ! Local variables live on the stack • Allocated at function invocation time • Deallocated when function returns • Storage space reused after function returns ! Space on the heap allocated with malloc() • Must be explicitly freed with free() • Called explicit or manual memory management Deletions must be done by the userCMSC 330 - Spring 2011 8 Memory Management Mistakes ! May forget to free memory (memory leak) { int *x = (int *) malloc(sizeof(int)); } ! May retain ptr to freed memory (dangling pointer) { int *x = ...malloc(); free(x); *x = 5; /* oops! */ } ! May try to free something twice { int *x = ...malloc(); free(x); free(x); } This may corrupt the memory management data structures • E.g., the memory allocator maintains a free list of space on the heap thatʼs availableCMSC 330 - Spring 2011 9 Ways to Avoid Mistakes ! Donʼt allocate memory on the heap • Often impractical • Leads to confusing code (e.g., alloca() ) ! Never free memory • OS will reclaim processʼs memory anyway at exit • Memory is cheap; who cares about a little leak? • LISP model – System halts program and reclaims unused memory when there is no more available ! Use a garbage collector • E.g., conservative Boehm-Weiser collector for CCMSC 330 - Spring 2011 10 Memory Management in Ruby ! Local variables live on the stack • Storage reclaimed when method returns ! Objects live on the heap • Created with calls to Class.new ! Objects never explicitly freed • Ruby uses automatic memory management Uses a garbage collector to reclaim memoryCMSC 330 - Spring 2011 11 Memory Management in OCaml ! Local variables live on the stack ! Tuples, closures, and constructed types live on the heap • let x = (3, 4) (* heap-allocated *) • let f x y = x + y in f 3 (* result heap-allocated *) • type ʻa t = None | Some of ʻa • None (* not on the heap–just a primitive *) • Some 37 (* heap-allocated *) ! Garbage collection reclaims memoryCMSC 330 - Spring 2011 12 Memory Management in Java ! Local variables live on the stack • Allocated at method invocation time • Deallocated when method returns ! Other data lives on the heap • Memory is allocated with new • But never explicitly deallocated Java uses automatic memory managementCMSC 330 - Spring 2011 13 Fragmentation ! Another memory management problem ! Example sequence of calls allocate(a); allocate(x); allocate(y); free(a); allocate(z); free(y); allocate(b); ⇒ Not enough contiguous space for bCMSC 330 - Spring 2011 14 Garbage Collection Goal ! Process to reclaim memory • Also solve fragmentation ! Algorithm: You can do garbage collection and memory compaction if you know where every pointer is in a program. If you move the allocated storage, simply change the pointer to it. ! This is true in LISP, OCAML, Java, Prolog ! Not true in C, C++, Pascal, AdaCMSC 330 - Spring 2011 15 Garbage Collection (GC) ! At any point during execution, can divide the objects in the heap into two classes • Live objects will be used later • Dead objects will never be used again They are “garbage” ! Idea • Can reuse memory from dead objects (recycling!) ! Goals • Reduce memory leaks • Make dangling pointers impossibleCMSC 330 - Spring 2011 16 Many GC Techniques ! In most languages we canʼt know for sure which objects are really live or dead • Undecidable, like solving the halting problem ! Thus we need to make an approximation • OK if we decide something is live when itʼs not • But weʼd better not deallocate an object that will be used later onCMSC 330 - Spring 2011 17 Reachability ! An object is reachable if it can be accessed by chasing pointers from live data ! Safe policy: delete unreachable objects • An unreachable object can never be accessed again by the program The object is definitely garbage • A reachable object may be accessed in the future The object could be garbage but will be retained anyway Could lead to memory leaksCMSC 330 - Spring 2011 18 Roots ! At a given program point, we define liveness as being data reachable from the root set • Global variables What are these in Java? Ruby? OCaml? • Local variables of all live method activations I.e., the stack ! At the machine level • Also consider the register set Usually stores local
View Full Document
Unlocking...