GC

Lecture slide: click here

Garbage collection, allocation/deallocation, reference counting, concurrent programming. Readings: Scott, ch. 7

Types of allocation

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.

Heap deallocation methods

Manual deallocation, free, delete
Automatic deallocation via GC
Semi-automatic deallocation, using destructors (C++, Ada)

Allocation methods

Two basic methods: free list and heap pointer.

Kinds of fragmentation that happen when allocating

Internal fragmentation: memory allocated but not used. Typical for fixed block allocation. External fragmentation: available memory blocks too small to be used.

Free list

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.

First fit

Select the first block large enough to satisfy the request.

Best fit

Select the smallest block large enough to satisfy the request.

Worst fit

Always select the largest available block.

Heap pointer

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.

Automatic deallocation

Basic garbage collection algorithms: mark/sweep, copying, hybrid(combination of copy and mark & sweep) and reference counting.

GC