Logo Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Mark-and-Compact Garbage Collection

The mark-and-sweep algorithm described in Section gif has the unfortunate tendency to fragment the heap. The stop-and-copy algorithm described in Section gif avoids fragmentation at the expense of doubling the size of the heap. This section describes the mark-and-compact   approach to garbage collection which eliminates fragmentation without the space penalty of stop-and-copy.

The mark-and-compact algorithm consists of two phases: In the first phase, it finds and marks all live objects. The first phase is called the mark phase. In the second phase, the garbage collection algorithm compacts the heap by moving all the live objects into contiguous memory locations. The second phase is called the compaction  phase. The algorithm can be expressed as follows:

for each root variable r
    mark (r);
compact ();