# GC

> Lecture slide: [click here](https://www.kdocs.cn/p/110422566840)

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.

### Mark / sweep

Works for free list. Algorithm at slide P16.

### Copying GC

Works for heap pointer. Algorithm at slide P18.

### Generational GC

Slide P19.

### Reference counting

Slide P22.