ContextContextPlayersVirtual MemoryReference countingTracing AlgorithmsDesignStraw ManDesign SpaceGenerational ScavengingGenerational ScavengingResultsResultsQuestionsIs This Still Relevant Now?Breaking or Enforcing Abstractions1 / 13Generation scavenging: A non-disruptive high-performancestorage reclamation algorithmBy David UngarPresented by Donald NguyenFebruary 9, 2009Context2 / 13■ The year was 1984. . .◆ Microcomputers, interactive programming environments■ Design interactive Smalltalk-80 system for Sun workstation◆ Main technical hurdles:■ Limit pause times■ Play well with virtual memoryPlayers3 / 13■ Virtual memory◆ Segmentation◆ Paging■ Popular GC algorithms◆ Reference counting◆ Mark-sweep [MKSMW]◆ Copy-collector [Baker-78]◆ Generational collection [Lieberman-Hewitt-83]Virtual Memory4 / 13■ Segmentation◆ Main memory divided into blocks of potentially unequal lengths◆ Typically typed into program and data segments◆ When a segment is swapped in, it can only replace a segment of thesame size or larger (fragmentation)■ Paging◆ Fixed-size blocksReference counting5 / 13■ High overhead because additional action must be done for all objects■ Immediate reference counting■ Deferred reference counting [Deutsch-Bobrow ]◆ Ignore references from local variables◆ Precludes reclamation during execution■Question: Reference counting today?◆ Different overheads today?◆ What about William’s anecdote about only using reference countabledata structures?Tracing Algorithms6 / 13■ Mark-sweep◆ Mark phase inspects all live objects, sweep phase mod ifies all deadobjects◆ Large pause times■ Scavenging algorithms◆ Psuedo real-time; overhead to install and check forwarding pointers,maintain remembered set◆ Baker’s semispace algorithm◆ Ballard’s modification of Baker’s algorithm■ Create separate area for old objects■ 600 KB for old objects, 512 KB object table, 2 x 1 MB semispaces◆ Lieberman-Hewitt’s generational algorithm, not implementedStraw Man7 / 13■ OS already has virtual memory, leverage abstraction of “infinite memory”◆ One object per segment/page◆ Use VM to keep live objects in main memory◆ Dead objects will be moved to secondary storage■ Problems?Straw Man7 / 13■ OS already has virtual memory, leverage abstraction of “infinite memory”◆ One object per segment/page◆ Use VM to keep live objects in main memory◆ Dead objects will be moved to secondary storage■ Problems?◆ For segmentation, object variance: [24, 128,000] bytes (mean: 50)and number: 32,000–64,000 objects◆ Object fragmentationStraw Man7 / 13■ OS already has virtual memory, leverage abstraction of “infinite memory”◆ One object per segment/page◆ Use VM to keep live objects in main memory◆ Dead objects will be moved to secondary storage■ Problems?◆ For segmentation, object variance: [24, 128,000] bytes (mean: 50)and number: 32,000–64,000 objects◆ Object fragmentation◆ Allocation rates:70 bytes1 object×1 object80 instructions1×9000 bytecodessecond=7800 bytessecondBS-II second7800 bytes×Dorado second13 BS-II seconds×100 MBdisk≈20 minutesdisk1Appel reports 1 object every 30 instructionsDesign Space8 / 13■ Keep main memory footprint low: 1.5–3 MB■ Low pause time, but not necessarily real-time■ Reduce page faults■ Reduce CPU overheadGenerational Scavenging9 / 13Generational Scavenging10 / 13■ Novelties:◆ Regions of different sizes: NewSpace (140 KB), *SurvivorSpace(28 KB each)◆ OldSpace not resident in main memory◆ Tenuring: after a while a surviving object is promoted to OldSpace.■ Similarities with Ballard’s algorithm:◆ Young and old generations◆ Copies live objects◆ Reclaims old objects offline■ Differences with other generational algorithms:◆ Divides new space into three regions instead of two◆ Not incremental, no checks needed on loadsResults11 / 13CPUTime(%)MainMemory(KB)PagingI/OPausetime (s)Pauseinterval(s)page it ? 15 ≈ 50/simm. ref. count 15–20 15 ? 0 ∞compaction1.3 60–1200def. ref. count11 40 ? 0.030 0.30compaction1.3 60–1200mark-sweep 25–40 1900 90/gc 4.5 74Ballard7 2000 0 0 ∞Gen. Scavenge 1.5–2.5 200 1.2/s 0.38 30Table 1: Summary of reclamation strategiesIs This Still Relevant Now?12 / 13■ Revisiting the claims:◆ Limit pause times to a fraction of a second◆ Requires no hardware support◆ Meshes well with virtual memory◆ Reclaims circular structures◆ Uses less than 2% of the CPU time■ Is the experimental methodology still sound?■ Should old objects be kept in secondary storage?Breaking or Enforcing Abstractions13 / 13■ If computer science is generally about making abstractions and extractingperformance about breaking them, how should we view Ungar’s work?◆ A case for a wider interface between runtime system and OS?◆ An isolated issue related to implementing a managed memory system?■ What memory management techniques can help or hinder virtual memorysystems and vice versa?◆ E.g., Appel recommends mapping the memory just before the freespace (assuming allocation goes from high to low) to an inaccessiblepage so that the out of memory test can be converted to a page
View Full Document
Unlocking...