ALGORITHM Mark and sweep

5.7.2.4.1 ALGORITHM : Mark and sweep

// The first tracing garbage collection algorithm.
// The mark-sweep algorithm is invoked when the mutator requests memory but there is
// insufficient free space.
// The mutator is stopped while the mark-sweep is executed.
// Mark phase: Identifies all reachable objects by setting a mark
// Sweep phase: Reclaims garbage objects

function DFS(x) {
if (x is a heap pointer)
if (x is not marked)
{
mark x
for(i = 1; i <= │x│; i++)
DFS(x,f1)
}
}

function Mark() {
for each (v in a stack frame)
DFS(V)
}
function Sweep() {
p = first address in heap
while (p < last address in heap)
{
if (p is marked)
unmark p;
else
{
p. f1 = freelist
freelist = p
}

p = p + sizeof(p)
}
}