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

Mark-and-Sweep Collection

Two-phase algorithm: mark all reachable objects, then sweep memory to free unmarked objects.

Mark-and-Sweep Collection

What you'll learn: How the mark-and-sweep algorithm reclaims unused memory by identifying and freeing unreachable objects in two distinct phases.

The Core Idea

Mark-and-sweep is a fundamental garbage collection algorithm that works in two sequential phases. First, it marks every object reachable from the root set (global variables, stack variables, registers). Then it sweeps through all of memory, freeing any objects that weren't marked—these are unreachable and therefore garbage.

Think of it like cleaning out a storage unit: First, you walk through and put sticky notes on everything you still need (mark phase). Then you make a second pass and throw away anything without a sticky note (sweep phase).

How It Works

Phase 1: Mark

  • Start from the root set (remember, these are your program's active references)
  • Traverse all reachable objects, following pointers/references
  • Set a "mark bit" or flag on each visited object
  • Continue recursively until all reachable objects are marked

Phase 2: Sweep

  • Scan through the entire heap memory sequentially
  • For each object: if marked, clear the mark bit (prepare for next collection); if unmarked, add it to the free list and reclaim its memory
  • After sweeping, only live objects remain

Characteristics

  • Simple conceptually: Two clear, separate phases
  • Stops the world: The program must pause during collection (marking ensures no objects become unreachable mid-scan)
  • Handles cycles: Unlike reference counting, mark-and-sweep correctly identifies circular references as garbage if the cycle itself is unreachable
  • Memory overhead: Requires a mark bit per object

Key Takeaway: Mark-and-sweep garbage collection uses a two-phase approach—first marking all live objects by traversing from roots, then sweeping through memory to free everything unmarked—providing automatic memory management that handles circular references correctly.