Garbage Collector

Computer Science

How It Works

The Mark-and-Sweep garbage collection algorithm automates dynamic heap memory management by identifying and recycling unreferenced memory blocks. In the initial Mark phase, the runtime traverses object connectivity graphs originating from known root pointers (thread registers, call stacks, globals), tagging every visited object as reachable. In the subsequent Sweep phase, the collector sweeps linear heap memory, recycling unmarked objects back to the allocation free list.

Governing Equation
Reachable(x) ⟺ ∃ path(Root → x) , Reclaimed = ∑_{x ∉ Reachable} Size(x)