Cycle Tracing
Outline
Concurrent Mark Sweep
Collector-Mutator Race
Base Backup Tracing Algorithm
Concurrency Optimization
Inherent Acyclic Objects
Sweep Optimization
Implementation with RC
An Example

Base Backup Tracing Algorithm
Roots: All objects referenced by roots are added to the work queue.
Mark: The work queue is exhaustively processed.
Process: Each object is taken off the work queue, and if the object is not marked, it is marked and then each of its referents are added to the work queue.
Check: Before leaving the mark phase, we process any object potentially subject to the collector—mutator race. If any of these objects are not marked, they are marked, added to the work queue, and the Mark phase is resumed.
Sweep: Reclaim space used by objects that have not been marked.