A Real-Time Garbage Collector Based on the Lifetimes of ObjectsMotivation: Internal ThinkingMotivation: Reference CountingMotivation: Ref Counting w/ CyclesMotivation: Cycles Are NeededReal Time GC [Baker’s Algorithm]What’s Wrong With Baker?Generational HypothesisModify Baker’s AlgorithmIn ActionSlide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Varying GC RatesScavanging is Expensive!Entry TablesWeak PointersSome Bad NewsAn Optimization? -Value Cells & StacksAn Optimization?-Flavors of newAspects of Program BehaviorPowerPoint PresentationA Real-Time Garbage Collector Based on the Lifetimes of ObjectsHenry Lieberman and Carl Hewitt(CACM, June 1983)Rudy Kaplan DepenaCS395T: Memory ManagementFebruary 2, 2009Motivation: Internal Thinking“Programs Do A Lot of Internal Thinking”- Lieberman and Hewittpublic void printAll(ArrayList list){Iterator it = new list.iterator();Object temp;while( it.hasNext() ){temp = it.next();System.out.println( temp );}}Code snippet from Mike Scott’s lecture on Iterators[http://www.cs.utexas.edu/~scottm/cs307/handouts/Slides/Topic15Iterators.pdf]Motivation: Reference CountingReference Counting claims young objects quicklyhead Node Node NodenextnextnextrefCount = 2 refCount = 1refCount = 1Example from “Data Structures and Algorithms with Object-Oriented Design Patterns in Java”[http://www.brpreiss.com/books/opus5/html/page423.html]Motivation: Ref Counting w/ CyclesHouston We Have A Problem!head Node Node NodenextnextnextrefCount = 1 refCount = 1refCount = 1Example from “Data Structures and Algorithms with Object-Oriented Design Patterns in Java”[http://www.brpreiss.com/books/opus5/html/page423.html]Motivation: Cycles Are NeededBut Circular Structures are important programming technique for ….GraphicsCompilersOther Problem SpacesSo What Do We Do???Real Time GC [Baker’s Algorithm]QuickTime™ and a decompressorare needed to see this picture.Graphics from Lieberman and Hewitt[“A Real-Time Garbage Collector Based on the Lifetimes of Objects” - CACM June 1983]What’s Wrong With Baker?Perhaps Too Slow?Total Garbage Collection Time?Not Space Efficient?Generational Hypothesis“Recently created regions contain high % of garbage” while older regions do not- Lieberman and HewittImprove Baker’s AlgorithmOptimize for scavenging short lived objectsScavenge long-lived objects less frequentlyRental CostStorage management cost of an object is proportional to the time during which the object is usedInspired by Maria Jump’s Presentation in Fall 2003 on Generational GC[http://www.cs.utexas.edu/users/mckinley/395Tmm-2003/talks/LH83.pdf]Modify Baker’s AlgorithmAddress space broken up into generationsSmall set of pages (relative to address space)Parallels between Baker Algo and Generational GCEvacuating <=> Condemning Regionfromspace <=> Obsolete Regiontospace <=> Non-Obsolete RegionEvacuating objects the same wayInspired by Maria Jump’s Presentation in Fall 2003 on Generational GC[http://www.cs.utexas.edu/users/mckinley/395Tmm-2003/talks/LH83.pdf]In Action1960.0Regions are tagged with generation and version numberFrom Maria Jump’s Presentation in Fall 2003 on Generational GC[http://www.cs.utexas.edu/users/mckinley/395Tmm-2003/talks/LH83.pdf]In Action1960.0Allocation occurs in creation regionFrom Maria Jump’s Presentation in Fall 2003 on Generational GC[http://www.cs.utexas.edu/users/mckinley/395Tmm-2003/talks/LH83.pdf]In Action1960.0… until the creation region is fullFrom Maria Jump’s Presentation in Fall 2003 on Generational GC[http://www.cs.utexas.edu/users/mckinley/395Tmm-2003/talks/LH83.pdf]In Action1960.0… the new creation region is createdFrom Maria Jump’s Presentation in Fall 2003 on Generational GC[http://www.cs.utexas.edu/users/mckinley/395Tmm-2003/talks/LH83.pdf]1970.0• CONS composes existing components into objects• creates a backward pointerIn Action1960.0… and so onFrom Maria Jump’s Presentation in Fall 2003 on Generational GC[http://www.cs.utexas.edu/users/mckinley/395Tmm-2003/talks/LH83.pdf]1970.0In Action1960.0… and so onFrom Maria Jump’s Presentation in Fall 2003 on Generational GC[http://www.cs.utexas.edu/users/mckinley/395Tmm-2003/talks/LH83.pdf]1970.0 1980.0In Action1960.0GC is initiated by condemning a region (making it obsolete) and creating an evacuation regionFrom Maria Jump’s Presentation in Fall 2003 on Generational GC[http://www.cs.utexas.edu/users/mckinley/395Tmm-2003/talks/LH83.pdf]1970.0 1980.01970.1In Action1960.0This requires that younger generations also be condemnedWHY ?????Modified from Maria Jump’s Presentation in Fall 2003 on Generational GC[http://www.cs.utexas.edu/users/mckinley/395Tmm-2003/talks/LH83.pdf]1970.0 1980.01970.1 1980.1In Action1960.0Accessibile objects in condemned region(s) are incrementally evacuated using Baker’s AlgorithmFrom Maria Jump’s Presentation in Fall 2003 on Generational GC[http://www.cs.utexas.edu/users/mckinley/395Tmm-2003/talks/LH83.pdf]1970.0 1980.01970.1 1980.1In Action1960.0… and the memory is recycled!From Maria Jump’s Presentation in Fall 2003 on Generational GC[http://www.cs.utexas.edu/users/mckinley/395Tmm-2003/talks/LH83.pdf]1970.1 1980.1Varying GC RatesYounger generations contain high percentages of garbageThey should be collected frequentlyOlder generation contains relatively permanent dataOlder objects collected seldomlyGetting the most “Bang for your Buck”Scavange where there is high proportion of inaccessible objectsMinimize amount of scavenging needed per inaccessible objectWhy is this important?Modified from Maria Jump’s Presentation in Fall 2003 on Generational GC[http://www.cs.utexas.edu/users/mckinley/395Tmm-2003/talks/LH83.pdf]Scavanging is Expensive!We must restrict the storage that has to be scanned to find and update obsolete referencesWe restrict pointers from older generations to newer generationsThis means it will be faster to reclaim regions in recent generations since little storage needs to be scavengedWhat happens when an attempt is made to create a pointer from older to younger generation????Entry Tables1960.01970.0 1980.0 In Lisp, RPLACA can assign a new pointer as a component to an older object creates a forward pointer Add entry table to record forward pointers Adds a level of indirection for some pointers Won’t have to scan entire heap GC uses entry table entries as roots to the
View Full Document