GC
Last updated
Last updated
Lecture slide:
Garbage collection, allocation/deallocation, reference counting, concurrent programming. Readings: Scott, ch. 7
Static: absolute address retained throughout program’s execution. Such as: static variables, global variables, certain fixed data like string literals, constants.
Stack: last-in, first-out ordering. Such as subroutine arguments, local variables, and runtime system data structures like displays.
Heap: general storage, foe allocation at arbitrary times. It's explicitly or automatically allocated, things like resizable types (e.g. String), Java class instances, all objects and data structures in Python.
Manual deallocation, free, delete
Automatic deallocation via GC
Semi-automatic deallocation, using destructors (C++, Ada)
Two basic methods: free list and heap pointer.
Internal fragmentation: memory allocated but not used. Typical for fixed block allocation. External fragmentation: available memory blocks too small to be used.
A linked list of unused blocks of memory is maintained (the free list).
Allocation: a search is done to find a free block of adequate size, then remove the found block from the list. Deallocation: the freed block is placed back on the free list.
Problems: may take some time to find a free block of the right size; memory eventually becomes fragmented.
Select the first block large enough to satisfy the request.
Select the smallest block large enough to satisfy the request.
Always select the largest available block.
Initially, the heap pointer is set to bottom of heap.
Allocation: the heap pointer is incremented an appropriate amount Deallocation: defragmentation eventually required.
Problem: requires moving live objects in memory.
Basic garbage collection algorithms: mark/sweep, copying, hybrid(combination of copy and mark & sweep) and reference counting.
Works for free list. Algorithm at slide P16.
Works for heap pointer. Algorithm at slide P18.
Slide P19.
Slide P22.