Slide 1OutlineConcurrent Mark SweepCollector-Mutator RaceCollector-Mutator RaceBase Backup Tracing AlgorithmConcurrency OptimizationInherent Acyclic ObjectsSweep OptimizationImplementation with RCAn ExampleAn ExampleAn ExampleAn ExampleAn ExampleAn ExampleCYCLE TRACINGChapter 4, pages 41--56, 2010. From: "Garbage Collection and the Case for High-level Low-level Programming," Daniel Frampton, Doctoral Dissertation, Australian National University.OutlineBrief Intro: Snapshot-at-the-Beginning Concurrent Mark-SweepBase Backup Tracing AlgorithmOptimizations In a Ref Count EnvironmentConcurrency: Reduce the fix-up setAcyclic objectsSweep less than whole heapMore Interaction with the RCExample2Concurrent Mark SweepCollector processes a work queueHeap objects are one of:Collector and mutator run simultaneouslySnapshot-at-the-beginning – trace heap as it wasOnly want to track changes that were harmfulUnvisitedVisited ChildrenVisited3Collector-Mutator RaceC1: A pointer from a black object to a white object is createdC2: The original reference to a white object is destroyed4Collector-Mutator RaceC1: A pointer from a black object to a white object is createdC2’: The original path reference to a white object is destroyed5Base Backup Tracing Algorithm1. Roots: All objects referenced by roots are added to the work queue.2. Mark: The work queue is exhaustively processed.a) 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.b) 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.3. Sweep: Reclaim space used by objects that have not been marked.6Concurrency OptimizationC1: A pointer from a black object to a white object is createdC2’: The original path to a white object is destroyedFor C2’ to happen, white object or some object in the path to it gets a reference count decrement to nonzeroWe trace the fix-up set, so we can add any object in the path to the white obj.Objects whose ref count decrements to nonzero become the new fix-up setBetter: we only need to determine this as we are collecting7Inherent Acyclic ObjectsProposed by Bacon and Rajan[2001]Acyclic objectNo pointer fieldsOR can only point to another acyclic objectWe’ll make them greenTrivial to skip in mark phase: green=marked8Sweep OptimizationLimit sweep to potentially cyclic garbage: purple setAcyclic garbage swept by reference counterDisadvantage: now we need the purple set to be known9Implementation with RCConsistent root set for objects: already in RCFix-up set must be added to gray-queue when known to be completeTrivial if we make the RC a stop-the-world, even if the tracing algorithm is concurrentRC cannot free objects known to the trace algorithmDangling pointersMark purple or grey objects, cycle tracer will free them when removed from queue10An ExampleRegisters!11An ExampleRegisters!12An ExampleRegisters!13An ExampleRegisters!14An ExampleRegisters!15An
View Full Document
Unlocking...