# 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.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://notes.dizy.cc/programming-languages/gc.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.