To accomplish this properly, the garbage collector program must know the names of all data structures in use. We have assumed that these are accessible through variables outside the heap. After marking, every record of the heap that is not marked will be made known (that is, placed on the available space list). Every record that is marked will be reset to unmarked so that the garbage collector will work properly on its next call. The marking phase of the garbage collector works by traversing all data structures in use. Thus marking routines generally take execution time proportional to the number of records in use and are therefore slow. Similarly, the collection routine, which inserts the unmarked records on the list of available space, takes time proportional to the heap size.
Example 13.7
Apply garbage collection to the heap of Example 13.4. n
In the marking phase, the garbage collection would traverse l and t, marking all their nodes. The collection phase would then traverse the heap and collect all unmarked nodes on the available space list. Assuming the garbage collector recognizes when two unmarked nodes are adjacent and combines them into a larger node, the resultant heap would appear as shown in Figure 13.7. A better approach might be to garbage collect and compact together, thus producing an available list consisting of one large block, reducing fragmentation.
Figure 13.7 Heap from Example 13.4 after Garbage Collection