Java Reference
In-Depth Information
g
h
Figure12.17
Garbage cycle example. All memory elements in the cycle have
non-zero reference counts because each element has one pointer to it, even though
the entire cycle is garbage (i.e., no static variable in the program points to it).
Reference counts have several major disadvantages. First, a reference count
must be maintained for each memory object. This works well when the objects are
large, such as a file. However, it will not work well in a system such as LISP where
the memory objects typically consist of two pointers or a value (an atom). Another
major problem occurs when garbage contains cycles. Consider Figure 12.17. Here
each memory object is pointed to once, but the collection of objects is still garbage
because no pointer points to the collection. Thus, reference counts only work when
the memory objects are linked together without cycles, such as the UNIX file sys-
tem where files can only be organized as a DAG.
Another approach to garbage collection is the mark/sweep strategy. Here, each
memory object needs only a single mark bit rather than a reference counter field.
When free store is exhausted, a separate garbage collection phase takes place as
follows.
1. Clear all mark bits.
2. Perform depth-first search (DFS) following pointers beginning with each
variable on the system's list of static variables. Each memory element en-
countered during the DFS has its mark bit turned on.
3. A “sweep” is made through the memory pool, visiting all elements.
Un-
marked elements are considered garbage and placed in free store.
The advantages of the mark/sweep approach are that it needs less space than is
necessary for reference counts, and it works for cycles. However, there is a major
disadvantage. This is a “hidden” space requirement needed to do the processing.
DFS is a recursive algorithm: Either it must be implemented recursively, in which
case the compiler's runtime system maintains a stack, or else the memory manager
can maintain its own stack. What happens if all memory is contained in a single
linked list? Then the depth of the recursion (or the size of the stack) is the number
of memory cells! Unfortunately, the space for the DFS stack must be available at
the worst conceivable time, that is, when free memory has been exhausted.
Fortunately, a clever technique allows DFS to be performed without requiring
additional space for a stack. Instead, the structure being traversed is used to hold
the stack. At each step deeper into the traversal, instead of storing a pointer on the
stack, we “borrow” the pointer being followed. This pointer is set to point back
to the node we just came from in the previous step, as illustrated by Figure 12.18.
Each borrowed pointer stores an additional bit to tell us whether we came down
