Mark and Sweep

TL;DR

• Mark and Sweep is the foundational algorithm used by almost all Garbage Collectors.
• Mark Phase: The GC starts at GC Roots and traces all references, “marking” objects as alive.
• Sweep Phase: The GC scans the heap and deletes any object that was not marked.

Concept

Imagine a massive warehouse full of boxes (The Heap). You want to throw away boxes that nobody cares about.
Instead of looking at every box and asking “Does someone care about this?”, you use a different strategy.

1. The Mark Phase: You take a list of all active employees (GC Roots). You ask Employee 1 which boxes they need. They point to Box A. You paint Box A green (Alive). You open Box A, and inside it says “I also need Box B”. So you walk over and paint Box B green. You repeat this recursively until every needed box is painted green.
2. The Sweep Phase: You tell a bulldozer to drive through the warehouse. If a box is painted green, leave it alone. If a box is NOT painted green, immediately crush it and throw it in the dumpster.

The Problem: Fragmentation

The biggest flaw with Mark and Sweep is that the bulldozer leaves the warehouse looking like Swiss cheese. There are random empty spaces everywhere. If an employee asks to store a massive new Couch, it might not fit in any of the individual small holes, even though the total empty space in the warehouse is large enough.

Examples

class Node {
    Node next;
}

public class MarkAndSweepDemo {
    public static void main(String[] args) {
        
        Node n1 = new Node(); // GC Root points here
        Node n2 = new Node(); 
        Node n3 = new Node(); 
        
        n1.next = n2; 
        
        // n3 is not connected to n1 or n2. 
        // During the MARK phase, the GC starts at the local variables (n1, n2, n3).
        
        n3 = null; // n3 local variable is destroyed.
        
        // NEW MARK PHASE:
        // GC starts at 'n1'. Marks Node 1 as alive. 
        // Node 1 points to Node 2. Marks Node 2 as alive.
        // Nothing points to Node 3. It is not marked.
        
        // SWEEP PHASE:
        // GC deletes Node 3. 
    }
}

Interview Questions

Q: How does Mark and Sweep solve the “Circular Reference” problem?
A: Older algorithms like “Reference Counting” failed with circular references. If Object A points to Object B, and Object B points to Object A, their reference counts are both 1, so they never get deleted, even if the main application lost track of them.
Mark and Sweep solves this elegantly. The algorithm starts from GC Roots (active threads/variables). If the main application lost the reference to A, the GC will never reach A during its trace. It will never reach B either. Neither will be marked, and both will be swept away safely.