Data Structures and Algorithms with Object-Oriented Design Patterns in Java

Mark-and-Compact Garbage Collection

The mark-and-sweep algorithm described in Section has the unfortunate tendency to fragment the heap. The stop-and-copy algorithm described in Section 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 ();

Handles