Memory Management [Chapter 6]

Here, we ask not what to store in the memory, but where to store it, and how to keep track of what memory is used and what is vacant.

Static allocation

Early versions of Fortran use static allocation. The idea is that every variable, including local variables of functions, are allocated when the program is loaded into memory. Nothing ever moves, and the size of the program's data are is fixed.

Static allocation
Early versions of Fortran use static allocation. The idea is that every variable, including local variables of functions, are allocated when the program is loaded into memory. Nothing ever moves, and the size of the program's data are is fixed.

Stack allocation

Algol 60 introduced stack allocation, which stores local variables of functions (and some additional information) into the run-time stack.

The stack grows and shrinks as the program runs. Each time a function is called, it gets space in the run-time stack for its information. When the function returns, all of its space is deallocated.

Stack allocation
Algol 60 introduced stack allocation, which stores local variables of functions (and some additional information) into the run-time stack. The stack grows and shrinks as the program runs. Each time a function is called, it gets space in the run-time stack for its information. When the function returns, all of its space is deallocated.

Heap allocation

Later programming languages introduced the heap, where programs can allocate data that stays around longer than the function that did the allocation.

There are two ways to manage the heap, manually or automatically.

Manual management

The program is given two functions, such as alloc and free, one that gets more memory and another that deallocates memory. This is what is done by Pascal and C++.

This has the problem that the programmer must keep track of memory. Knowing when to deallocate is a major problem, and mistakes in this are common and serious.

Automatic heap management

The run-time system can learn, on its own, which memory is no longer in use, and can deallocate that memory automatically. This greatly reduces the strain on programmers.

Reference counts

One approach is to use reference counts. Each block of memory keeps track of the number of pointers that point to it. When that number becomes 0, that block is deallocated.

Garbage collector

A mark and sweep garbage collector finds unused memory in two stages.

All data structures used by the program are traversed. Pointers are followed. Everything that is accessible is marked.

The heap is traversed. Anything that is not marked is deallocated.

Fragmentation and compactification

Memory can become fragmented: all available memory is cut up into small pieces, alternating with used pieces.

To avoid fragmentation, a garbage collector can move the used memory together. It compactifies it.

Unfortunately, pointers become wrong when memory is moved. The pointers need to be changed. That is called relocation.

You can relocate by using two heaps. At any given time, one of the heaps is in use, and the other is fallow. When you compactify, you move all blocks to the fallow heap, leaving behind "forwarding addresses" in the previously used heap. The forwarding addresses are used to achieve relocation.