Java Reference
In-Depth Information
Global pointer P
Reference Count = 2
Link
Data
Reference Count = 1
Link
Data
Figure 12.15: An Example of Circular Structures
An important aspect of reference counting is that it is
incremental
.That
is, whenever a pointer is manipulated, a small amount of work is done to
support garbage collection. This is both an advantage and a disadvantage. It
is an advantage in that the cost of garbage collection is smoothly distributed
throughout a computation. A programdoes not need to stop when heap space
grows short and do a lengthy collection. This can be crucial when fast real-time
response is required. (We do not want the controls of an aircraft to suddenly
“freeze” for a second or two while a program collects garbage!)
The incremental nature of reference counting can also be a disadvantage
when garbage collection is not really needed. If we have a complex data
structure in which pointers are frequently updated, but in which few objects
ever are discarded, reference counting always adjusts counts that rarely, if ever,
go to zero.
How big should a reference count field be? Interestingly, experience has
shown that it does not need to be particularly large. Often only a few bits
su
ce. The idea here is that if a count ever reaches themaximum representable
count (perhaps 7 or 15 or 31), we “lock” the count at that value. Objects with a
locked reference count will never ever be detected as garbage by their counts,
but they can be collected using other techniques when circular structures are
collected.
In summary, reference counting is a simple technique whose incremental
nature is sometimes useful. Because of its inability to handle circular struc-
tures and its significant per-pointer operation cost, other garbage collection
techniques, as described below, are often more attractive alternatives.
Mark-Sweep Collection
Rather than incrementally collecting garbage as
pointers are manipulated, we can take a batch approach. We do nothing
until heap space is nearly exhausted. Then we execute a
marking phase
,
which aims to identify all live (non-garbage) heap objects.
Starting with global pointers and pointers in stack frames, we mark reach-
able heap objects (perhaps setting a bit in the object's header). We then follow
