A Real-Time Garbage Collector with Low Overhead and Consistent UtilizationMotivationProblems with Previous WorksComponents and Concepts in MetronomeSegregated Free List AllocatorLimiting Internal FragmentationDefragmentationRead Barrier: To-space InvariantRead Barrier OptimizationIncremental Mark-SweepPointer Fix-up During MarkArrayletsSlide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Scheduling the CollectorSchedulingExperimental ResultsPause Time Distribution for javac (Time-Based vs. Work-Based)Utilization vs. Time for javac (Time-Based vs. Work-Based)Minimum Mutator Utilization for javac (Time-Based vs. Work-Based)Space Usage for javac (Time-Based vs. Work-Based)ConclusionsDiscussionA Real-Time Garbage Collector with Low Overhead and Consistent UtilizationDavid F. Bacon, Perry Cheng,and V.T. RajanIBM T.J. Watson Research CenterPresented by Jason VanFickellthanks to Srilakshmi Swati Pendyala for 2009 slidesMotivation•Real-time systems growing in importance•Desirability of higher level programming languages•Constraints for Real-Time SystemsoHard constraints for continuous performance (Low Pause Times)oMemory Constraints (less memory in embedded systems)•Maximum Pause Time < Required Response•CPU Utilization sufficient to accomplish taskoMeasured with Minimum Mutator Utilization•Memory Requirement < Resource LimitoImportant Constraint in Embedded SystemsNeed for a real-time garbage collector with low memory usage.Problems with Previous Works•FragmentationoEarly works (Baker’s Treadmill) handles a single object sizeoFragmentation not a major problem for a family of C and C++ benchmarks (Johnstone’ Paper)Unsustainable for long-running programsoUse of single (large) block sizeIncrease in memory requirements and internal fragmentation•High Space OverheadoCopying algorithms to avoid fragmentation increase space overhead•Uneven Mutator UtilizationoFraction of processor devoted to mutator executionoCopying algorithms suffer from uneven mutator utilizationoLong low-utilization periods•Inability to handle large data structuresComponents and Concepts in Metronome•Segregated free list allocatoroGeometric size progression limits internal fragmentation•Mostly non-copyingoObjects are usually not moved.•DefragmentationoMoves objects to a new page when page is fragmented due to GC•Read barrier: to-space invariant [Brooks]oNew techniques with only 4% overhead•Incremental mark-sweep collectoroMark phase fixes stale pointers•Arraylets: bound fragmentation, large object ops•Time-based schedulingNewOldSegregated Free List Allocator•Heap divided into fixed-size pages•Each page divided into fixed-size blocks•Objects allocated in smallest block that fits241612Limiting Internal Fragmentation•Choose page size P and block sizes sk such thatosk = sk-1(1+ρ)•How do we choose small s0 & ρ ? •s0 ~ minimum block size•ρ ~ sufficiently small to avoid internal fragmentationoToo small a ρ leads to too many pages and hence a wastage of space, but it should be okay for long running processesoToo large a ρ leads to internal fragmentation•Memory for a page should be allocated only when there is at least one object in that page.Defragmentation•When do we move objects?oAt the end of sweep phase, when there are no sufficient free pages for the mutator to execute, that is, when there is fragmentation•Usually, program exhibits locality of sizeoDead objects are re-used quickly•Defragment either whenoDead objects are not re-used for a GC cycleoFree pages fall below limit for performing a GC•In practice: we move 2-3% of data tracedoMajor improvement over copying collectorRead Barrier: To-space Invariant•Problem: Collector moves objects (defragmentation)oMutator is finely interleaved•Solution: read barrier ensures consistencyoEach object contains a forwarding pointer [Brooks]oRead barrier unconditionally forwards all pointersoMutator never sees old versions of objects•Will the mutator utilization have any effects because of the read barrier ?From-spaceTo-spaceAXYZAXYZA′BEFOREAFTERRead Barrier Optimization•Previous studies: 20-40% overhead [Zorn, Nielsen]•Several optimizations applied to the read barrier and reduced the cost over-head to <10% using Eager Read Barriers•“Eager” read barrier preferred over “Lazy” read barrier.Incremental Mark-Sweep•Mark/sweep finely interleaved with mutator•Write barrier: snapshot-at-the-beginning [Yuasa]oEnsures no lost objectsoTreats objects in write buffer as roots•Read barrier ensures consistencyoMarker always traces correct objectoSimpler interleavingPointer Fix-up During Mark•When can a moved object be freed?oWhen there are no more pointers to it•Mark phase updates pointersoRedirects forwarded pointers as it marks them•Object moved in collection n can be freed:oAt the end of mark phase of collection n+1From-spaceTo-spaceAXYZA′Arraylets•Large arrays create problemsoFragment memory spaceoCan not be moved in a short, bounded time•Solution: break large arrays into arrayletsoAccess via indirection; move one arraylet at a timeA1 A2 A3Heap (one size only)StackProgram StartHeapStackfreeallocatedProgram is allocatingHeapStackfreeunmarkedGC startsHeapStackfreeunmarkedmarked orallocatedProgram allocating and GC markingHeapStackfreeunmarkedmarked orallocatedSweeping away blocksHeapStackfreeallocatedevacuatedGC moving objects and installing redirectionHeapStackfreeunmarkedevacuatedmarked orallocated2nd GC starts tracing and redirection fixupHeapStackfreeallocated2nd GC completeScheduling the Collector•Scheduling IssuesoPoor CPU utilization and space usageoLoose program and collector coupling•Competing options:oTime-BasedTrigger the collector to run for CT seconds whenever the mutator runs for QT secondsoWork-BasedTrigger the collector to collect CW work whenever the mutator allocate QW bytesScheduling•Very predictable mutator utilization•Memory allocation does not need to be monitored.•Uneven mutator utilization due to bursty allocation•Memory allocation rates need to be monitored to make sure real-time performance is obtainedTime – Based Work – BasedExperimental Results•IBM RS/6000 Enterprise Server F80•AIX 5.1•500 MHz PowerPC RS64 III•4 GB RAM•4 MB of L2 cache•Jikes Research Virtual Machine (RVM) 2.1.1•Adaptive compilation disabled12 sPause Time Distribution for javac (Time-Based vs. Work-Based)Utilization vs. Time for javac (Time-Based vs.
View Full Document
Unlocking...