CMSC 330: Organization of Programming Languages Garbage Collection CMSC 330 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 reuse CMSC 330 3 Memory Attributes (cont’d) •! Most programming languages are concerned with some subset of the following 4 memory classes: –! Fixed (or static) memory –! Automatic memory –! Programmer allocated memory –! Persistent memory CMSC 330 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 terminatesMemory Classes (cont’d) •! 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 5 Memory Classes (cont’d) •! 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 •! See databases (CMSC 242) CMSC 330 6 CMSC 330 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() –! This is called explicit or manual memory management •! Deletions must be done by the user CMSC 330 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 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 C CMSC 330 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 memory CMSC 330 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 memory CMSC 330 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 13 Second Memory Problem: Fragmentation allocate(a); allocate(x); allocate(y); free(a); allocate(z); free(y); allocate(b); ! No contiguous space for b CMSC 330 14 (Compacting) Garbage Collection Goal •! Process to reclaim memory. (Also solve Fragmentation problem.) •! To do this, need to find every pointer in the program –! If you move allocated storage, update the pointer to it •! Easy to get this information in Java, Ruby, OCaml, ... •! Hard in C, C++, Pascal, Ada CMSC 330 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 •! Goals: Reduce memory leaks, and make dangling pointers impossible CMSC 330 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 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 leaks CMSC 330 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, we also consider the register set (usually stores local or global variables) •! Next: techniques for pointer chasing CMSC 330 19 Reference Counting •! Old technique (1960) •! Each object has count of number of pointers to it from other objects and from the stack –! When count reaches 0, object can be deallocated •! Counts tracked by either compiler or manually •! To find pointers, need to know layout of objects –! In particular, need to distinguish pointers from ints •! Method works mostly for reclaiming memory –! Doesn’t handle fragmentation problem CMSC 330 20 Reference Counting Example stack 1
View Full Document
Unlocking...