Introduction: All trace-based algorithms compute the set of reachable objects and then take the complement of this set. Memory is therefore recycled as follows:

a)      The program or mutator runs and makes allocation requests.

b)      The garbage collector discovers reachability by tracing.

c)       The garbage collector reclaims the storage for unreachable objects.

This cycle is illustrated in Fig. 7.23 in terms of four states for chunks of memory: Free, Unreached, Unscanned, and Scanned. The state of a chunk might be stored in the chunk itself, or it might be implicit in the data structures used by the garbage-collection algorithm.

While trace-based algorithms may differ in their implementation, they can all be described in terms of the following states:

1. Free. A chunk is in the Free State if it is ready to be allocated. Thus, a free chunk must not hold a reachable object.

2. Unreached. Chunks are presumed unreachable, unless proven reachable by tracing. A chunk is in the Unreached state at any point during garbage collection if its reachability has not yet been established. Whenever a chunk is allocated by the memory manager, its state is set to Unreached as illustrated in Fig. 7.23(a). Also, after a round of garbage collection, the state of a reachable object is reset to Unreached to get ready for the next round; see the transition from Scanned to Unreached, which is shown dashed to emphasize that it prepares for the next round.

3. Unscanned. Chunks that are known to be reachable are either in state Unscanned or state Scanned. A chunk is in the unscanned state if it is known to be reachable, but its pointers have not yet been scanned. The transition to Unscanned from Unreached occurs when we discover that a chunk is reachable; see Fig. 7.23(b).

4. Scanned. Every Unscanned object will eventually be scanned and transition to the Scanned state. To scan an object, we examine each of the pointers within it and follow those pointers to the objects to which they refer. If a reference is to an unreached object, then that object is put in the unscanned state. When the scan of an object is completed, that object is placed in the Scanned state; see the lower transition in Fig. 7.23(b). A Scanned object can only contain references to other Scanned or Unscanned objects, and never to unreached objects.

When no objects are left in the unscanned state, the computation of reachability is complete. Objects left in the unreached state at the end are truly unreachable. The garbage collector reclaims the space they occupy and places the chunks in the Free State, as illustrated by the solid transition in Fig. 7.23(c). To get ready for the next cycle of garbage collection, objects in the Scanned state are returned to the unreached state; see the dashed transition in Fig. 7.23(c). Again, remember that these objects really are reachable right now. The Unreachable state is appropriate because we shall want to start all objects out in this state when garbage collection next begins, by which time any of the currently reachable objects may indeed have been rendered unreachable.

Example: Let us see how the data structures of Algorithm Mark-and-sweep garbage collection relate to the four states introduced above. Using the reached-bit and membership on lists Free and Unscanned, we can distinguish among all four states. The table of Fig. 7.24 summarizes the characterization of the four states in terms of the data structure for Algorithm Mark-and-sweep garbage collection.

Previous Next