Dynamic Memory ManagementMemory ManagementMemory Managementldots Memory Managementldots Interface to Dynamic allocationExplicit DeallocationMemory LeaksMemory Leaksldots FragmentationImplicit DeallocationImplicit Deallocationldots Algorithm: Reference CountsAlgorithm: Reference Countsldots Algorithm: Reference Countsldots Readings and ReferencesReadings and Referencesldots520—Spring 2005—38CSc 520Principles of ProgrammingLanguages38: Garbage Collection — IntroductionChristian [email protected] of Computer ScienceUniversity of ArizonaCopyrightc 2005 Christian Collberg[1]520—Spring 2005—38Dynamic Memory ManagementThe run-time system linked in with the generated codeshould contain routines for allocation/deallocation ofdynamic memory.Pascal, C, C++, Modula-2 Explicit deallocation of dynamicmemory only. I.e. the programmer is required to keeptrack of all allocated memory and when it’s safe to freeit.Eiffel Implicit deallocation only. Dynamic memory which isno longer used is recycled by the garbage collector.Ada Implicit or explicit deallocation (implementationdefined).Modula-3 Implicit and explicit deallocation (programmer’schoice).[2]520—Spring 2005—38Memory ManagementIn a language such as C or Pascal, there are threeways to allocate memory:1. Static allocation. Global variables are allocated atcompile time, by reserving2. Stack allocation. The stack is used to storeactivation records, which holds procedure call chainsand local variables.3. Dynamic allocation. The user can create newmemory at will, by calling anew or (in unix) mallocprocedure.The compiler and run-time system divide the availableaddress space (memory) into three sections, one foreach type of allocation:[3]520—Spring 2005—38Memory Management...1. The static section is generated by the compiler andcannot be extended at run-time. Called theuninitialized data section in unix’s a.out.2. The stack. The stack grows and shrinks duringexecution, according to the depth of the call chain.Infinite recursion often leads to stack overflow. Largeparameters can also result in the program runningout of stack space.3. The heap. When the program makes a request formore dynamic memory (by callingmalloc, forexample), a suitable chunk of memory is allocatedon the heap.[4]520—Spring 2005—38Memory Management...Static allocation – GlobalvariablesStack allocation – Procedurecall chains, Local variables.Dynamic allocation – NEW,malloc, On the heap.Uninitialized Data(Global Variables)Initialized Data(strings,reals...)Program CodeStackHeap[5]520—Spring 2005—38Interface to Dynamic allocationC, C++: char* malloc(size) and free(char*) arestandard library routines.Pascal: new(pointer var) and dispose(pointervar) are builtin standard procedures.Java: new(class name) is a standard function.LISP: cons creates new cells:nullbcnullabc’(b c) ’(a b c)TailHead(cons ’a ’(b c))[6]520—Spring 2005—38Explicit DeallocationPascal’s new/dispose, Modula-2’sALLOCATE/DEALLOCATE, C’s malloc/free, C++’snew/delete, Ada’s new/unchecked deallocation(some implementations).Problem 1: Dangling references: p=malloc(); q=p;free(p);.Problem 2: Memory leaks, Heap fragmentation.free list:free list:48163264Large cellSmall cellHeap:128512[7]520—Spring 2005—38Memory LeaksDEFINITION MODULE Complex;TYPE T;PROCEDURE Create (Re, Im : REAL) : T;PROCEDURE Add (A, B : T) : T;END Complex.IMPLEMENTATION MODULE Complex;TYPE T = POINTER TO RECORDRe, Im : REAL; END;PROCEDURE Create (Re, Im : REAL) : T;BEGINNEW(x); x↑.Re := Re; x↑.Im := Im;RETURN x; END Create;PROCEDURE Add (A, B : T) : T;BEGINNEW(x); x↑.Re := · · ·; x↑.Im := · · ·;RETURN x; END Add;END Complex;[8]520—Spring 2005—38Memory Leaks...MODULE Use;IMPORT Complex;VAR a,b,c,d : Complex.T;BEGINa := Complex.Create(1.0, 2.4);b := Complex.Create(3.4, 4.0);c := Complex.Create(9.4, 6.6);d := Complex.Add(a,Complex.Add(b,c));END Use.Complex.Add(b, c) creates a new object which can never be reclaimed.c dba1.0 3.4 9.4 12.8 13.82.4 4.0 6.6 10.6 13.0Heapb+c[9]520—Spring 2005—38FragmentationVAR a, b, c, d : POINTER TOARRAY [1..1000] OF BYTE;VAR x : POINTER TOARRAY [1..2000] OF BYTE;BEGINNEW(a); NEW(b); NEW(c); NEW(d);DISPOSE(a); DISPOSE(c); NEW(x);1000 1000 1000c dba xFree list:HeapWithout compaction the last allocation will fail, even though enough memory isavailable.[10]520—Spring 2005—38Implicit DeallocationLISP, Prolog – Equal-sized cells; No changes to oldcells.Eiffel, Modula-3 – Different-sized cells; Frequentchanges to old cells.When do we GC?Stop-and-copy Perform a GC whenever we run out ofheapspace (Modula-3).Real-time/Incremental Perform a partial GC for eachpointer assignment or new (Eiffel, Modula-3).Concurrent Run the GC in a separate process.[11]520—Spring 2005—38Implicit Deallocation...Fragmentation – Compact the heap as a part of the GC,or only when the GC fails to return a large enoughblock.Algorithms: Reference counts, Mark/ssweep, Copying,Generational.[12]520—Spring 2005—38Algorithm: Reference CountsAn extra field is kept in each object containing a countof the number of pointers which point to the object.Each time a pointer is made to point to an object, thatobject’s count has to be incremented.Similarly, every time a pointer no longer points to anobject, that object’s count has to be decremented.When we run out of dynamic memory we scan throughthe heap and put objects with a zero reference countback on the free-list.Maintaining the reference count is costly. Also, circularstructures (circular linked lists, for example) will not becollected.[13]520—Spring 2005—38Algorithm: Reference Counts...Every object records the number of pointers pointing to it.When a pointer changes, the corresponding object’s reference count has to beupdated.GC: reclaim objects with a zero count. Circular structures will not bereclaimed.1 2 1 1be reclaimed)Garbage (will Garbage (won’tbe reclaimed)1HeapbaGlobalVariables10Live cells[14]520—Spring 2005—38Algorithm: Reference Counts...NEW(p) is implemented as:malloc(p); p↑.rc := 0;p↑.next:=q is implemented as:z := p↑.next;if z 6= nil thenz↑.rc--; if z↑.rc = 0 then reclaim z↑ endif;endif;p↑.next := q;q↑.rc++;This code sequence has to be inserted by the compilerfor every pointer assignment in the program. This isvery expensive.[15]520—Spring 2005—38Readings and ReferencesRead Scott, pp. 395–401.Apple’s Tiger book, pp. 257–282Topics in
View Full Document
Unlocking...