Java Reference
In-Depth Information
Global pointer
Global pointer
Internal pointer
Object 1
Object 5
Object 3
Figure 12.16: Mark-Sweep Garbage Collection
pointers in marked heap objects until all live heap objects are marked.
After the marking phase, we know that any object not marked is garbage
that may be freed. We then “sweep” through the heap, collecting all unmarked
objects and returning them to the free space list for later reuse. During the
sweep phase
we also clear all marks from heap objects found to still be in use.
Mark-sweep garbage collection is illustrated in Figure 12.16. Objects 1
and 3 are marked because they are pointed to by global pointers. Object 5 is
marked because it is pointed to by object 3, which is marked. Shaded objects
are not marked and will be added to the free space list.
In any mark-sweep collector it is vital that we mark
all
accessible heap
objects. If we miss a pointer we may fail to mark a live heap object and
later incorrectly free it. Finding all pointers is not too di
cult in languages
like Lisp and Scheme that have very uniform data structures, but it is a bit
tricky in languages like Java, C, and C
, that have pointers mixed with other
types within data structures, implicit pointers to temporaries, and so forth.
Considerable information about data structures and frames must be available
at runtime for this purpose. In cases where we cannot be sure if a value is a
pointer or not, we may need to do conservative garbage collection (see below).
Mark-sweep garbage collection also has the problem that all heap objects
must be swept. This can be costly if most objects are dead. Other collection
schemes, like copying collectors, examine only live objects.
After the sweep phase, live heap objects are distributed throughout the
heap space. This can lead to poor locality. If live objects span many mem-
ory pages, paging overhead may be increased. Cache locality may also be
degraded.
We can add a
compaction phase
to mark-sweep garbage collection. After
live objects are identified, they are placed together at one end of the heap.
This involves another tracing phase in which global, local, and internal heap
pointers are found and adjusted to reflect the object's new location. Pointers
are adjusted by the total size of all garbage objects between the start of the
heap and the current object. This is illustrated in Figure 12.17.
Compaction is attractive because all garbage objects are merged together
into one large block of free heap space. Fragments are no longer a problem.
++
