CSE 341 -- Memory Management

It is useful to understand how storage is managed in different programming languages and for different kinds of data. Three important cases are:


Static Storage Allocation

Static storage allocation is appropriate when the storage requirements are known at compile time. For a compiled, linked language, the compiler can include the specific memory address for the variable or constant in the code it generates. (This may be adjusted by an offset at link time.)

Examples:


Stack-Based Storage Allocation

Stack-based storage allocation is appropriate when the storage requirements are not known at compile time, but the requests obey a last-in, last-out discipline.

Examples:

Stack-based allocation is normally used in C, Ada, Algol, and Pascal for local variables in a procedure and for procedure call information. It allows for recursive procedures, and also allocates data only when the procedure or function has been called -- but is reasonably efficient at the same time.

Typically a pointer to the base of the current stack frame is held in a register, say R0. A reference to a local scalar variable can be compiled as a load of the contents of R0 plus a fixed offset. Note that this relies on the data having known size. To compile a reference to a dynamically sized object, e.g. an array, use indirection. The stack contains an array descriptor, of fixed size, at a known offset from the base of the current stack frame. The descriptor then contains the actual address of the array, in addition to bounds information.

There are two important limitations to pure stack-based storage allocation. First, the only way to return data from a procedure or function is to copy it -- if you try to simply return a reference to it, the storage for the date will have vanished after the procedure or function returns. This isn't an issue for scalar data (integers, floats, booleans), but is an issue for large objects such as arrays. For this reason you can't for example return a loclly declared array from a function in Algol-60 or C. Second, you can't return a procedure or function as a value, or assign a procedure or function to a global variable (procedures or function values aren't first class citizens). The reason for this restriction is that procedure-valued variables need to be closures -- that is, they need to include a reference to the procedure body along with a pointer to the environment of definition of the procedure. With a stack-based storage allocation scheme, if we tried to say assign a procedure to a global variable, environment of definition may have disappeared when we try to call the procedure.


Heap-Based Storage Allocation

The most flexible allocation scheme is heap-based allocation. Here, storage can be allocated and deallocated dynamically at arbitrary times during program execution. This will be more expensive than either static or stack-based allocation. The important distinction is between explicit allocation/deallocation and automatic memory management (garbage collection).

It is easiest to think of the heap of consisting of memory which are either inuse or free. The free memory is in a linked list. When new memory is needed a block of memory is taken from the free list (perhaps subdividing a block). When blocks are no longer needed, they can be put back onto the free list. If blocks of storage are not returned, then the system may eventually run out of memory. If a block of memory is returned when it is still in-use, the memory may become corrupted, leading to a program failure. In general, it is much worse to return a block to storage too early than to hold onto a block unnecessarily.

Issue: when is storage allocated and deallocated?

Allocation is easy. In C, malloc (a standard library function) allocates fresh storage. In Lisp, a new cons cell is allocated when the cons function is called, array storage can be allocated using make-array, and so forth. In Smalltalk, new storage is allocated when someone sends the new message to a class.

Deallocation is harder. There are two approaches: programmer-controlled and automatic. In languages such as C, the programmer is in charge of deciding when heap storage can be freed (in C using the free function). This is efficient but can lead to problems if the programmer makes a mistake -- either storage is not freed even though it is no longer needed (memory leak), or is freed but referred to later (dangling pointer). Dangling pointers can lead to type insecurities or other errors -- one can refer to storage that has been re-allocated for another purpose with data of a different type.

Garbage Collection

Lisp and Smalltalk, as well as various other languages, use automatic storage management. There is no explicit deallocate function; rather, storage is automatically reclaimed some time after it is no longer accessible. The most common technique is garbage collection; its simplest form is mark and sweep. In for example Lisp, when the system runs out of storage, first mark all cons cells as unreferenced. Then start with known references (global variables, local variables in the stack, etc) and mark the cells it references as to be kept. Follow the car and cdr pointers, marking those cells as to be kept, then the cells they refer to, and so forth. (Stop when you encounter a cons cell that is already marked to prevent infinite looping.) After the process is completed, sweep through memory, linking all the unreferenced cells into the free list.

There has been much research on garbage collection, and a variety of more efficient algorithms have been developed. (For example, the average lifetime of objects is bimodal -- either objects have very short lifetimes or long lifetimes -- and efficient algorithms can take advantage of this fact.)

Reference Counting The basic idea for reference counting is to keep track of how many pointers there are to each block. Whenever a pointer changes, the number of references to the block is changed. When the number of references gets down to zero, the block goes away. The advantages of reference counting are that it is incremental (a small cost at each step), and is relatively simple. The downside is the cycles of blocks can't be collected - so some other mechanism needs to be used to cover the general case.

Mark and Sweep Mark and sweep is the classical garbage collection algorithm, which first traces through all live blocks (via DFS or BFS), and then makes a pass through all of memory saving the marked blocks, and disposing of the unmarked block. The drawbacks to Mark and Sweep are that it is monolithic (everything stops when there is a collection), and that it involves looking at all of memory, instead of just the live stuff.

Copying collectors The basic idea of a copying collector is that all of the live blocks are moved to a new area - and whats left is discarded as the garbage. Copying collectors divide memory into to space and from space. When all the live blocks have been moved from one side to the other, the two spaces switch roles. One advantage of a copying collector is that only the live blocks need to be looked at. This means that short lived objects may not need to be collected - since if they are born and die between collections, they are created in the from space, and never moved. (Creation is easy in this scheme - since the free space is in a single block). There are many enhancements to copying collection - such as mechanisms for making it incremental, which make copying collectors the best in practice.

Generational collectors It has been observed that the life times of objects is bimodal - most objects have very short life spans, but there are some objects which live for very long periods of times. Garbage collectors can take advantage of this by using different regions of memory for long lived objects, and applying collection to the different regions at different rates. When a block survives a number of collections, it is promoted (or tenured), and moved to the next level, reducing the frequency at which it is examined. This scheme can by used in copying garbage collectors.