Garbage CollectionStatic vs. Dynamic AllocationSlide 3What is Garbage Collection?How to Find GarbageAbstract GC AlgorithmWhen to Garbage Collect?How to Decide?Some Typical GC AlgorithmsReference CountersStop and CopyGenerationalMark & SweepInternallyBut where are free cells?Free ListSlide 17Clear?Mark -- Sweep AlgorithmMarkSlide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31SweepSlide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61Slide 62Slide 63Simple?Variable Sized CellsQuestions?Slide 67Garbage CollectionCSCI 2720Spring 2005Static vs. Dynamic Allocation•Early versions of Fortran–All memory was static•C–Mix of static and dynamic allocation–Dynamic allocation must be managed 100% by programmer•malloc•realloc•calloc•free•Lisp–Completely dynamic–Separate programmer from machineGarbage Collection•Sometimes called Automatic Memory Management (OO)•Affects design of programs–Tendency to use painless features–Does have cost•Part of overall heap management problem•Not the only solution•Two flavors–Constant sized allocation units–Variable sized allocation units•C does not have Garbage Collection!What is Garbage Collection?•Program(mer) requests allocation of memory from heap.•If allocation is granted, memory is allocated and address is returned and stored in pointer variable.•Contents of pointer variable may be copied so that multiple pointers may exist pointing to same location•The allocated area becomes "garbage" if it is no longer being referenced by any pointer.•Typically garbage collection occurs when the runtime system no longer has any free memory to allocateHow to Find Garbage•Root Set–Set of all pointers that are either global or on activation stack•All memory referenced by root set pointers OR by pointers in memory that is referenced by root set pointers•Think about a linked list!Abstract GC Algorithm 1. Stop the machine. 2. Partition the heap into live data and garbage. 3. Mark or rearrange heap so that garbage can be reused. 4. Restart the machine.When to Garbage Collect?•When unable to allocate. •When remaining free space is low. •Periodically. •When user program pauses for terminal or disk I/O. •Note: Good news?–Memory is plentiful–Virtual memory makes memory appear larger (cost?)May be worst May be worst possible timepossible timeHow to Decide?•Which collector algorithm will be used•Whether the application program is interactive•How much memory is available on the machine•The allocation behavior of the program•etc.Some Typical GC Algorithms•Reference Counters•Stop and Copy•Generational•Mark/SweepReference Counters•Each allocated block of memory contains a counter.–Each time another pointer starts pointing to the block the counter is incremented–Each time a pointer stops pointing at a block the counter is decremented–If the counter = 0 the block is returned to the free memory list•Problems–If the blocks are small the storage taken up by counters becomes significant–Execution time penalty–Circular structures pose difficulties (not insurmountable)Known as the Eager ApproachKnown as the Eager ApproachStop and Copy•Heap is divided into two partitions (to-space and from-space)•When GC runs copy all live allocations from the from-space partition to the t o -space partition–To-space partition now contains contiguous memory–This will typically run faster on modern hardware (Caches)•Swap to-space and from-space (labels)•Bad things–Requires twice as much memory–Will repeatedly copy large long-lived things (needlessly)Generational•Overcomes the problem of repeatedly copying large long-lived objects?–Observation: Most allocated data dies young. •Idea: Use multiple generation spaces with the to-space of a younger generation equal to the from-space of an older generation. –Collect from from-space 0 to to-spac e of generation 1. –Collect from generation 1 from-space to generation 2 to-space, etc. •Only the oldest generation needs its own to-space.•Collect younger generations more frequently than older ones.Mark & Sweep•Language such as Lisp or Scheme based on constant size memory cells: cons cellCons cellCons cellInternally foo bar baz() foo blarg() bar baz()XXYYBut where are free cells?Free ListFreeFree () Allocating a cons cell means getting firstAllocating a cons cell means getting firstcell in free list. Deallocation just reverses cell in free list. Deallocation just reverses the process.the process.Free ListXX()()YY()FreeFree()Internallyfoo bar baz()foo blarg()bar baz()XXYYClear?Mark -- Sweep Algorithm•Each block must contain bit (mark bit)•Initially all blocks are unmarked•Starting at each symbol perform a depth-first search marking all blocks reachable (mark means in-use)•Sweep through all blocks.–If marked: Unmark–If unmarked: move to free list•Note: Algorithm must be only thing running•Garbage collection is only done when necessary–i.e. When free list is emptyMarkFree ListXX()()YY()FreeFree()MarkMarkInternallyfoo bar baz()foo blarg()bar baz()XXYYFree ListXX()()YY()FreeFree()MarkMarkInternallyfoo bar baz()foo blarg()bar baz()XXYYFree ListXX()()YY()FreeFree()MarkMarkInternallyfoo bar baz()foo blarg()bar baz()XXYYFree ListXX()()YY()FreeFree()MarkMarkInternallyfoo bar baz()foo blarg()bar baz()XXYYFree ListXX()()YY()FreeFree()MarkMarkInternallyfoo bar baz()foo blarg()bar baz()XXYYFree ListXX()()YY()FreeFree()MarkMarkInternallyfoo bar baz()foo blarg()bar baz()XXYYFree ListXX()()YY()FreeFree()MarkMarkInternallyfoo bar baz()foo blarg()bar baz()XXYYFree ListXX()()YY()FreeFree()MarkMarkInternallyfoo bar baz()foo blarg()bar baz()XXYYFree ListXX()()YY()FreeFree()MarkMarkInternallyfoo bar baz()foo blarg()bar baz()XXYYFree ListXX()()YY()FreeFree()MarkMarkInternallyfoo bar baz()foo blarg()bar baz()XXYYFree ListXX()()YY()FreeFree()MarkMarkInternallyfoo bar baz()foo blarg()bar baz()XXYYSweepFree ListXX()()YY()FreeFree()Internallyfoo bar baz()foo blarg()bar baz()XXYYSweepSweepFree ListXX()()YY()FreeFreeSweepSweepInternallyfoo bar baz()foo blarg()bar baz()XXYYFree ListXX()()YY()FreeFreeSweepSweepInternallyfoo bar baz()foo blarg()bar baz()XXYYFree