A Real-time garbage collector with low overhead and consistent utilizationOutlineMotivationGarbage Collection in Real-time SystemsProblems with Previous WorksSlide 6Slide 7Components and Concepts in Proposed GCSegregated Free List AllocatorLimiting Internal FragmentationDefragmentationRead Barrier: To-space InvariantRead Barrier OptimizationIncremental Mark-SweepPointer Fix-up During MarkArrayletsSlide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Scheduling the CollectorSchedulingSlide 29Pause 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)ConclusionsA REAL-TIME GARBAGE COLLECTOR WITH LOW OVERHEAD AND CONSISTENT UTILIZATIONDavid F. Bacon, Perry Cheng, and V.T. RajanIBM T.J. Watson Research CenterPresented by Srilakshmi Swati PendyalaOutlineMotivationIntroduction & Previous WorksOverview of the Proposed Garbage CollectorExample of the Collection ProcessScheduling – Time-Based Vs. Work-BasedExperimental ResultsConclusionMotivationReal-time systems growing in importanceATMs, PDAs, Web Servers, Points of Sale etc.Constraints for Real-Time Systems:Hard constraints for continuous performance (Low Pause Times)Memory Constraints (less memory in embedded systems)Other Constraints ? Need for a real-time garbage collectorwith low memory usage.Garbage Collection in Real-time SystemsMaximum Pause Time < Required ResponseCPU Utilization sufficient to accomplish taskMeasured with Minimum Mutator UtilizationMemory Requirement < Resource LimitImportant Constraint in Embedded SystemsProblems with Previous WorksFragmentationEarly works (Baker’s Treadmill) handles a single object size Not suitable modern languagesFragmentation not a major problem for a family of C and C++ benchmarks (Johnstone’ Paper)Not valid for long-run programs (web-servers, embedded systems etc.)Use of single (large) block sizeIncrease in memory requirementsLeads to internal fragmentationProblems with Previous WorksHigh Space OverheadCopying algorithms to avoid fragmentation Leads to high space overheadUneven Mutator UtilizationThe fraction of processor devoted to mutator executionSeveral copying algorithms suffer from poor/uneven mutator utilizationLong low-utilization periods render mutator unsuitable for real-time applicationsInability to handle large data structuresWhen collecting a subset of the heap at a time, large structures generated by adversarial mutators force unbounded workOutlineMotivationIntroduction & Previous WorksOverview of the Proposed Garbage CollectorExample of the Collection ProcessScheduling – Time-Based Vs. Work-BasedExperimental ResultsConclusionComponents and Concepts in Proposed GCSegregated free list allocatorGeometric size progression limits internal fragmentationMostly non-copyingObjects are usually not moved.DefragmentationMoves objects to a new page when page is fragmented due to GCRead barrier: to-space invariant [Brooks]New techniques with only 4% overheadIncremental mark-sweep collectorMark phase fixes stale pointersArraylets: bound fragmentation, large object opsTime-based schedulingNewOldSegregated Free List AllocatorHeap divided into fixed-size pagesEach page divided into fixed-size blocksObjects allocated in smallest block that fits241612Limiting Internal FragmentationChoose page size P and block sizes sk such thatsk = sk-1(1+ρ)How do we choose small s0 & ρ ? s0 ~ minimum block size ρ ~ sufficiently small to avoid internal fragmentationToo small a ρ leads to too many pages and hence a wastage of space, but it should be okay for long running processesToo large a ρ leads to internal fragmentationMemory for a page should be allocated only when there is at least one object in that page.DefragmentationWhen do we move objects?At the end of sweep phase, when there are no sufficient free pages for the mutator to execute, that is, when there is fragmentationUsually, program exhibits locality of sizeDead objects are re-used quicklyDefragment either whenDead objects are not re-used for a GC cycleFree pages fall below limit for performing a GCIn practice: we move 2-3% of data tracedMajor improvement over copying collectorRead Barrier: To-space InvariantProblem: Collector moves objects (defragmentation)and mutator is finely interleavedSolution: read barrier ensures consistencyEach object contains a forwarding pointer [Brooks]Read barrier unconditionally forwards all pointersMutator never sees old versions of objectsWill the mutator utilization have any effects because of the read barrier ?From-space To-space A X Y Z A X Y Z A′BEFORE AFTERRead Barrier OptimizationPrevious 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-SweepMark/sweep finely interleaved with mutatorWrite barrier: snapshot-at-the-beginning [Yuasa]Ensures no lost objectsMust treat objects in write buffer as rootsRead barrier ensures consistencyMarker always traces correct objectWith barriers, interleaving is simpleAre the problems inherent to mark sweep, also apply here ?Pointer Fix-up During MarkWhen can a moved object be freed?When there are no more pointers to itMark phase updates pointersRedirects forwarded pointers as it marks themObject moved in collection n can be freed:At the end of mark phase of collection n+1From-space To-space A X Y Z A′ArrayletsLarge arrays create problemsFragment memory spaceCan not be moved in a short, bounded timeSolution: break large arrays into arrayletsAccess via indirection; move one arraylet at a timeA1 A2 A3OutlineMotivationIntroduction & Previous WorksOverview of the Proposed Garbage CollectorExample of the Collection ProcessScheduling – Time-Based Vs. Work-BasedExperimental ResultsConclusionHeap (one size only)StackProgram StartHeapStackfreeallocatedProgram is allocatingHeapStackfreeunmarkedGC startsHeapStackfreeunmarkedmarked orallocatedProgram allocating and
View Full Document
Unlocking...