Two-Phase Reachability Analysis
Mark-and-sweep garbage collection has two phases. In the mark phase, the collector traverses the object graph starting from roots (global variables, stack frames, registers). Every reachable object is marked (a flag set in the object header or a separate marking array). Objects unreachable from the roots are left unmarked.
In the sweep phase, the collector walks the entire heap. Unmarked objects are added to the free list, and marked objects are unmarked for the next collection. Sweep doesn't move objects; it just adds dead objects back to the free list. This in-place reclamation avoids the 50% space overhead of copying collectors.
Fragmentation and Incremental Variants
Mark-and-sweep can cause heap fragmentation: if objects are allocated and freed in irregular patterns, the free list becomes scattered, and large allocations may fail despite enough total free space. Solutions include defragmentation compaction (moving objects to fill holes, updating all references), or segregating object sizes into different pools.
The classic mark-and-sweep does the entire collection in one stop-the-world pause, which is visible in latency-sensitive applications. Incremental mark-and-sweep spreads the collection over many small pauses, allowing the application to run between phases. Concurrent mark-and-sweep (tri-color marking) allows the application to run during the marking phase, with careful synchronization to handle changes to the object graph. Java's G1GC and Go's GC use these advanced variants to keep pauses under 10 milliseconds even on large heaps.