On-the-Fly GarbageCollection: An Exercise inCooperationRudy Kaplan DepenaCS 395T: Memory ManagementMarch 30th, 2009Edsger W. Dijkstra, LeslieLamport, A.J. Martin, C.S.Scholten and E.F.M Steffens(Communications of the ACM, November 1978)• Motivation• Setting up the Playing Field• First Coarse-Grain Solution• Second Coarse-Grain Solution• Fine Grain Solution• The EndOutlineGarbage Collection is a useful tool for…1. Automating Memory Management2. Making Memory Management less error-prone (Developer doesn’t have to think about the memorymodel or use special keywords.)MotivationHowever, using GC is very costly for themutator because …1. In the case of McCarthy’s Mark-Sweep (andother GC algorithms), collection is performed onthe whole heap2. Whole heap collectors incur long pause timeswhich hault the mutator from executing andunpredictableMotivation (cont.)However, using GC is very costly for the mutatorbecause …1. In the case of McCarthy’s Mark-Sweep (and other GCalgorithms), collection is performed on the whole heap2. Whole heap collectors incur long pause times whichhault the mutator from executingMotivation (cont.)Steele* proposes using two (or more) processors …1. One processor is in charge of mutator program2. One processor is in charge of the garbage collectorGoal: Have little to no pause times interrupting themutator by housekeeping concurrently. However,exclusion and synchronization of processorsare an overhead.Motivation (cont.)* Multiprocessing Compactifying Garbage Collection (Communications of the ACM, 1975)• Dijkstra et. al. proposes the use ofmulti-processing garbagecollection, but keep exclusionand synchronization constraintsweak• Weak constraints mean that weavoid highly frequent mutualexclusion of activities amongstprocessors. (e.g. - markingobjects)• The above may help reducemutator overhead• Paper’s Goal: Not to make GCbetter, but to have a use-case formulti-processor interactionMotivation (cont.)• Although we would like to keep these weakconstraints on exclusion (avoid use of commonresource) and synchronization (timekeeping) thereare a few unavoidable situations …• When needing a new object from the free list, themutator may be delayed until collector hasappended some objects to the free list• Between the marking phase and appending/collectionphase, it is impossible to guarantee that we appendall garbage: new garbage could have been createdbetween marking and appending phase.Motivation (cont.)• The paper reasons about the problem of managingweak synch and exclusion by using a DirectedGraph with a few constraints …• Fixed number of nodes• Each node has at most 2 outgoing edgesSetting up the Playing Field• A few tidbits in terminology …• Roots - A fixed set of nodes• Reachable - Node is reachable if reachable if there existsa directed path from one root to the node.• Data Structure - Subgraph of all reachable nodes• Garbage - Non-reachable nodeSetting up the Playing Field (cont.)RootGarbageData StructureReachable1. Redirect an edge from one reachable node toanotherSetting up the Playing Field (cont.)Root1. Redirect an edge from one reachable node toanotherSetting up the Playing Field (cont.)Root2. Redirect an edge from one reachable node to a non-reachable nodeSetting up the Playing Field (cont.)Root2. Redirect an edge from one reachable node to a non-reachable nodeSetting up the Playing Field (cont.)Root3. Add missing outgoing edge from one reachable nodeto anotherSetting up the Playing Field (cont.)Root3. Add missing outgoing edge from one reachable nodeto anotherSetting up the Playing Field (cont.)Root4. Add missing edge from reachable node to non-reachable nodeSetting up the Playing Field (cont.)Root4. Add missing edge from reachable node to non-reachable nodeSetting up the Playing Field (cont.)Root5. Remove the edge of a reachable nodeSetting up the Playing Field (cont.)Root5. Remove the edge of a reachable nodeSetting up the Playing Field (cont.)Root• The authors set a special root node called NIL whoseoutgoing edges point to itself• The authors also represent a formerly missing edge nowas an edge with NIL as the logic• They say that NIL allows them to view data structuremodifications of types (3) and (5) as special cases of (1).• Why does NIL help with this ???Remember:(1) Redirect an outgoing edge of reachable node to already reachable node(3) Add an edge pointing from reachable node to a reachable node(5) Remove edge of reachable nodeDiscussionRules that make garbage:(1) Redirect edge from one reachable node toward another(2) Redirect edge from reachable node toward a non-reachable node(5) Remove edge of reachable nodeRules that recycle garbage: (2) Redirect edge from reachable node toward a non-reachable node (4) Add missing edge from reachable node to non-reachablenodeSetting up the Playing Field (cont.)• Suppose we have two programs A and B.• In this paper, atomic operations are denoted with angle brackets:• A: <z:=0> and B: <z:=3>• We say that A is coarser-grained than B if B is the result ofreplacing an atomic operation of A by a piece of program containingat least two atomic operations and having the same net effect as theoriginal operation:• A: <z:=0>• B: <z0:= 0> <z1:= 0>• If correctness is proved on finer-grained solution, this implies thatcoarse-grained solution is correct also.Setting up the Playing Field (cont.)• A simplification that the authors made is treating the free list not as a list ofgarbage, but as part of the data structure• Link NIL and free nodes such that they are reachable from special rootnodes.• A modification of (2) is now replaced by a sequence of modifications of type(1).• Why does this simplification allow them to replace (2) with a sequence of (1)modifications ???Remember:(1) Redirect an outgoing edge of reachable node to already reachable node(2) Redirect an outgoing edge of reachable nodes towards a not yet reachable onewith outgoing edgesDiscussion• Now because of NIL and free list being apart of the data structure, mutator andcollector activities are now repeated executions of (1)• Mutator: “redirect an edge of reachable node to already reachable one”• Collector:• Mark Phase: “mark all reachable nodes”• Append Phase: “append all unmarked nodes ot the free list and remove markingsfrom all marked nodes”• Two correctness criteria must be satisfied when mutator and collectorcooperate together• CC1:
View Full Document
Unlocking...