ContextContextOutlineProblems with concurrent GCObject accessObject creationPointer modificationConcurrent algorithmAssumptionsFlagsGC threadgcmarkgcmark (continued)gcmark (continued)gcmark1munch and unmunchCompaction optionsgcrelocategcupdategcreclaimMutator threadPrimitive operationspush(x)create(nargs)create(nargs) (continued)select(i)clobber(i)QuestionsImplementing the algorithmBackup slidesgcrelocategcrelocate (continued)1 / 33Multiprocessing compactifying garbage collectionGuy SteelePresented by Donald NguyenMarch 23, 2009Context2 / 33■ The year was 1975. . .■ Stop-the-world GC commonplace, but how to reduce pause times forinteractive or real-time applications?◆ Start and stop GC during convenient times for the user◆ Time-share one processor between mutator and a GC thread◆ Use two processors, one for mutator and one for GC■ Description of concurrent mark-sweep-compact algorithm (notimplementated, but some ideas about hardware optimizations)Outline3 / 33ContextProblems with concurrent GCConcurrent algorithmGC threadMutator threadQuestionsProblems with concurrent GCContextProblems withconcurrent GCObject accessObject creationPointer modificationConcurrentalgorithmGC threadMutator threadQuestions4 / 33Object access5 / 33■ Problem: An object may be moved while the mutator is accessing theobject. Mutator may see in consistent state of object.◆ Solution:Object access5 / 33■ Problem: An object may be moved while the mutator is accessing theobject. Mutator may see in consistent state of object.◆ Solution: Use forwarding pointers inside objects if relocated(difficulties?)Object access5 / 33■ Problem: An object may be moved while the mutator is accessing theobject. Mutator may see in consistent state of object.◆ Solution: Use forwarding pointers inside objects if relocated(difficulties?)◆ Mutator must check relocation status during GC phases where anobject could be moved◆ Need to protect flag indicating current GC phase◆ Possible race if GC is relocating an object while the mutator isaccessing it. Protect object access during relocation usingsemaphores. Overhead of acquiring object (“munch”) lock.Object creation6 / 33■ Problem: The mutator may create a new object during GC. Freelistneeds to be synchronized; GC n eeds to know that there is anotheraccessible object.◆ Solution:Object creation6 / 33■ Problem: The mutator may create a new object during GC. Freelistneeds to be synchronized; GC n eeds to know that there is anotheraccessible object.◆ Solution: Protect access to freelists but increase concurrency byhaving GC access the front and the mutator access the back. Modifymutator to signal new objects to GC thread. (difficulties?)Object creation6 / 33■ Problem: The mutator may create a new object during GC. Freelistneeds to be synchronized; GC n eeds to know that there is anotheraccessible object.◆ Solution: Protect access to freelists but increase concurrency byhaving GC access the front and the mutator access the back. Modifymutator to signal new objects to GC thread. (difficulties?)◆ Increased overhead for object creation, potential contention with GCthreadPointer modification7 / 33■ Problem: The mutator may add or remove references from objects. If theobject was marked by GC, the new references may not be traced. If themodification occurs during object relocation, modifications could be lostduring pointer update.◆ Solution:Pointer modification7 / 33■ Problem: The mutator may add or remove references from objects. If theobject was marked by GC, the new references may not be traced. If themodification occurs during object relocation, modifications could be lostduring pointer update.◆ Solution: During mark phase, mutator must notify GC thread w henmodifying a field of a marked object to point to an unmarked object.Protect object access during relocation using semaph ores.(difficulties?)Pointer modification7 / 33■ Problem: The mutator may add or remove references from objects. If theobject was marked by GC, the new references may not be traced. If themodification occurs during object relocation, modifications could be lostduring pointer update.◆ Solution: During mark phase, mutator must notify GC thread w henmodifying a field of a marked object to point to an unmarked object.Protect object access during relocation using semaph ores.(difficulties?)◆ Increased overhead for object modification, overhead of acquiringobject (“munch”) lock.Concurrent algorithmContextProblems withconcurrent GCConcurrentalgorithmAssumptionsFlagsGC threadMutator threadQuestions8 / 33Assumptions9 / 33■ One mutator processor, one GC processor■ Memory is divided into spaces of homogenous cells◆ Single word memory reads and writes are atomic◆ Shared access to global variables, GC stack and mutator stack◆ Synchronization via semaphore (P “try-to-acquire” and V“increment”)■ An object is a sequence of pointers an d has a mark and flag flag■ Coarse gcstate lock■Reasonable? Efficient?Flags10 / 33Mark bitfalse false true trueFlag bitfalse true false trueMeaning Not traced Relocated Accessible On freelistMark phase Cell not yettracedAccessibleRelocate phase Candidatetarget forrelocationRelocated Candidatesource forrelocationUpdate phase Need tonormalizepointersReclaim phase Return tofreelistReturn tofreelistOn freelistGC threadContextProblems withconcurrent GCConcurrentalgorithmGC threadgcmarkgcmark (continued)gcmark (continued)gcmark1munch and unmunchCompaction optionsgcrelocategcupdategcreclaimMutator threadQuestions11 / 33gmark12 / 33■ Recursive marking with an explicit stack■ Minimize contention by keeping critical sections small (see gcmark1())■ Three phases1. Process rootset2. Process mutator stack3. Process additional mutator generated objectssetgcstate(‘‘mark’’)for addr in rootspace: # Process rootsetgcpush(addr)gcmark1()...gmark(continued)13 / 33i = 0while True: # Process mutator stackP(mstack)if (i >= mstack.index)breakgcpush(mstack.cells[i].ptr)mstack.cells[i].mark = TrueV(mstack)gcmark1()i += 1mstack.gcdone = TrueV(mstack)...gmark(continued)14 / 33P(gcstate)while gcstack.index > 0: # Process new objectsV(gcstate)gcmark1()P(gcstate)gcstate = ‘‘relocate’’mstack.gcdone = FalseV(gcstate)gmark115 / 33while gcstack.index != 0:x = gcpop()if x.space == ‘‘mstack’’:contents(x).mark = Truex = contents(x).ptrif not contents(x).mark:munch(x)for addr in
View Full Document
Unlocking...