Introduction: The final step in the basic mark-and-sweep algorithm is expensive because there is no easy way to find only the unreachable objects without examining the entire heap. An improved algorithm, due to Baker, keeps a list of all allocated objects. To find the set of unreachable objects, which we must return to free space, we take the set difference of the allocated objects and the reached objects.
Algorithm: Baker's mark-and-sweep collector.
INPUT: A root set of objects, a heap, a free list Free, and a list of allocated objects, which we refer to as Unreached.
OUTPUT: Modified lists Free and Unreached, which holds allocated objects.
METHOD: In this algorithm, shown in Fig. 7.25, the data structure for garbage collection is four lists named Free, Unreached, Unscanned, and Scanned, each of which holds all the objects in the state of the same name. These lists may be implemented by embedded, doubly linked lists, as was discussed in Section 7.4.4. A reached-bit in objects is not used, but we assume that each object contains bits telling which of the four states it is in. Initially, Free is the free list maintained by the memory manager, and all allocated objects are on the unreached list (also maintained by the memory manager as it allocates chunks to objects).
Lines (1) and (2) initialize scanned to be the empty list, and unscanned to have only the objects reached from the root set. Note that these objects were presumably on the list Unreached and must be removed from there. Lines (3) through (7) are a straightforward implementation of the basic marking algorithm, using these lists. That is, the for-loop of lines (5) through (7) examines the references in one Unscanned object o, and if any of those references o' have not yet been reached, line (7) changes o' to the unscanned state.
At the end, line (8) takes those objects that are still on the unreached list and deallocates their chunks, by moving them to the free list. Then, line (9) takes all the objects in state Scanned, which are the reachable objects, and reinitializes the unreached list to be exactly those objects. Presumably, as the memory manager creates new objects, those too will be added to the unreached list and removed from the free list.
In both algorithms of this section, we have assumed that chunks returned to the free list remain as they were before deallocation. However, as discussed in Section 7.4.4, it is often advantageous to combine adjacent free chunks into larger chunks. If we wish to do so, then every time we return a chunk to the free list, line (8) of Fig. 7.25, we examine the chunks to its left and right, and merge if one is free.