Course contentsShow
← Computer Science
Lesson 2099 of 2,87247. Memory Management in LanguagesFree lesson

Tri-Color Marking

Incremental marking algorithm using white, gray, and black colors to track object traversal state.

Tri-Color Marking

What you'll learn: How garbage collectors use a three-color scheme to track which objects have been visited during the mark phase without stopping your program completely.


The Core Idea

In basic mark-and-sweep collection (lesson 2096), the collector must pause your entire program to trace through all reachable objects. Tri-color marking is an incremental algorithm that breaks this work into smaller steps, allowing the collector to run alongside your program with minimal pauses.

The algorithm assigns every object one of three colors:

  • White: Not yet visited; candidates for collection
  • Gray: Visited, but references from this object haven't been scanned yet; work queue
  • Black: Fully processed—this object and all objects it points to have been examined; definitely alive

How It Works

  1. Initialize: All objects start white. The root set (stack, globals) is marked gray.
  2. Scan incrementally: Pick a gray object, scan its references, and color any white objects it points to as gray. Mark the scanned object black.
  3. Repeat: Continue until no gray objects remain.
  4. Sweep: All remaining white objects are unreachable garbage and can be reclaimed.

The Analogy

Think of exploring a cave system: white rooms are unexplored, gray rooms have been entered but their exits haven't been checked, and black rooms are fully mapped. You incrementally explore, gradually turning everything either black (reachable) or leaving it white (inaccessible).

The key insight: black objects never point to white objects during collection (this is called the tri-color invariant), ensuring correctness even when your program mutates the heap between marking steps.

Key Takeaway: Tri-color marking enables incremental garbage collection by categorizing objects as white (unvisited), gray (work pending), or black (fully scanned), allowing the collector to pause and resume without losing progress.