Java Reference
In-Depth Information
q=p=malloc(1000);
free(p);
/* code containing a number of malloc's */
q[100] = 1234;
After p is freed, q is a dangling pointer. That is, q points to heap space that is no
longer considered allocated. Calls to mallocmay reassign the space pointed to
by q. Assignment through q is illegal, but this error is almost never detected.
Such an assignment may change data that is now part of another heap object,
leading to very subtle errors. It may even change a header field or a free space
link, causing the heap allocator itself to fail.
The alternative tomanual deallocation of heap space is automatic deallocation,
commonly called
garbage collection
. Compiler-generated code and support
subroutines track pointer usage. After a heap object is no longer live, the object
is automatically deallocated (collected) and made available for subsequent
reuse.
Garbage collection techniques vary greatly in their speed, e
ectiveness,
and complexity. We shall consider briefly some of the most important ap-
proaches. For a more thorough discussion see [Wil92, JL96].
ff
Reference Counting
One of the oldest and simplest garbage collection tech-
niques is
reference counting
. A field is added to the header of each heap
object. This field, the object's
reference count
, records how many references
(pointers) to the heap object exist. When an object's reference count reaches
zero, it is garbage and may be added to the free space list for future reuse.
The reference count fieldmust be updatedwhenever a reference is created,
copied, or destroyed. When a subprogram returns, the reference counts for
all objects pointed to by local variables must be decremented. Similarly, when
a reference count reaches zero and an object is collected, all pointers in the
collected object must also be followed and corresponding reference counts
decremented.
As shown in Figure 12.15, reference counting has particular di
culty with
circular heap structures
.Ifpointerp is set to null, the object's reference count is
reduced to 1. Now both objects have a non-zero count, but neither is accessible
through any external pointer. That is, the two objects are garbage, but will not
be recognized as such.
If circular structures are rare, this deficiency will not bemuch of a problem.
If they are common, then an auxiliary technique, like mark-sweep collection,
will be needed to collect garbage that reference counting misses.
