\section{Introduction}
%
% Dynamic Memory Allocation
%   o Can be stack based or heap based
%   o Stack based provides automatic deallocation
%   o Heap based deallocation may be explicit or implicit.
%

Most modern programming languages provide facilities for programmers
to perform dynamic memory allocation.  Dynamic memory allocation may
be broadly classified as either stack-based or heap-based.  In the
case of stack-based allocation, allocation occurs on the runtime
control stack and the storage is usually deallocated automatically
when the function or procedure which performed the allocation returns.
Stack-based allocation is generally used for small amounts of
temporary storage since, in most systems, the stack is relatively
small.

Heap-based dynamic allocation is typically used far more frequently
and for much larger data structures.  In Pascal and \C, heap-based
dynamic memory allocation is performed by using a language primitive
({\tt new}) or a library routine ({\tt malloc}).  In a typical Common
Lisp implementation on stock hardware, almost all allocation is
heap-based -- calls to functions such as {\tt CONS} and {\tt
MAKE-ARRAY} cause storage to be allocated from the heap.

Heap-allocated storage may be deallocated explicitly by the programmer
or implicitly by the run time system.  C, Pascal, and most other
Algol-like languages use the former method.  In such languages, the
programmer is burdened with the task of explicitly calling
deallocation primitives ({\it e.g.} {\tt new}) or routines ({\it e.g.}
{\tt free}) with any block of storage the program no longer needs or
fear running out of memory.  Further, the programmer must ensure that
no other pointers in the program refer to the block of storage.
Performing explicit deallocation can be non-trivial in a large program
with complex data structures and it is often performed incorrectly or
incompletely in such programs.  When performed incorrectly, the bugs
created may be insidious as the side effects of incorrect deallocation
are often subtle and can have many unrelated manifestations.  It can
be quite difficult to locate and fix such bugs.  When performed
incompletely, a storage ``leak'' occurs which may cause the program to
perform poorly or run out of memory and crash.

The alternative to explicit heap deallocation is implicit deallocation
by the runtime system.  In such a scheme, the runtime system, not the
programmer, is responsible for detecting blocks of storage that can no
longer be accessed by the user's program and allowing those blocks to
be reused.  This is often known colloquially as ``garbage
collection.''  Garbage collection frees the programmer to solve the
problem at hand \cite{standish80} and not get bogged down in the
details of storage reclamation.

This paper primarily focuses on garbage collection in Lisp systems but
the techniques and algorithms described within are applicable to a
wide variety of programming languages and environments.

