300 Chapter 6 Data Types
arise when a collection of cells is connected circularly. The problem here is that
each cell in the circular list has a reference counter value of at least 1, which
prevents it from being collected and placed back on the list of available space. A
solution to this problem can be found in Friedman and Wise (1979).
The advantage of the reference counter approach is that it is intrinsically
incremental. Its actions are interleaved with those of the application, so it never
causes significant delays in the execution of the application.
The original mark-sweep process of garbage collection operates as follows:
The run-time system allocates storage cells as requested and disconnects point-
ers from cells as necessary, without regard for storage reclamation (allowing
garbage to accumulate), until it has allocated all available cells. At this point, a
mark-sweep process is begun to gather all the garbage left floating around in
the heap. To facilitate the process, every heap cell has an extra indicator bit or
field that is used by the collection algorithm.
The mark-sweep process consists of three distinct phases. First, all cells in
the heap have their indicators set to indicate they are garbage. This is, of course,
a correct assumption for only some of the cells. The second part, called the mark-
ing phase, is the most difficult. Every pointer in the program is traced into the
heap, and all reachable cells are marked as not being garbage. After this, the third
phase, called the sweep phase, is executed: All cells in the heap that have not been
specifically marked as still being used are returned to the list of available space.
To illustrate the flavor of algorithms used to mark the cells that are cur-
rently in use, we provide the following simple version of a marking algorithm.
We assume that all heap-dynamic variables, or heap cells, consist of an informa-
tion part; a part for the mark, named marker; and two pointers named llink
and rlink. These cells are used to build directed graphs with at most two
edges leading from any node. The marking algorithm traverses all spanning
trees of the graphs, marking all cells that are found. Like other graph traversals,
the marking algorithm uses recursion.for every pointer r do
mark(r)void mark(void * ptr) {
if (ptr != 0)
if (*ptr.marker is not marked) {
set *ptr.marker
mark(*ptr.llink)
mark(*ptr.rlink)
}
}An example of the actions of this procedure on a given graph is shown in
Figure 6.11. This simple marking algorithm requires a great deal of storage (for
stack space to support recursion). A marking process that does not require addi-
tional stack space was developed by Schorr and Waite (1967). Their method