CMSC 433 – Programming LanguageTechnologies and ParadigmsFall 2006Memory Management2Memory Management in Java• Local variables live on the stack– Allocated at method invocation time– Deallocated when method returns• Other data lives on the heap– Memory is allocated with new– But never explicitly deallocated• Java uses automatic memory management3Memory Mgmt and the JVM• The JVM Specification doesn’t say how tomanage the heap• Simplest valid memory managementstrategy: never delete any objects– Not such a bad idea in some circumstances(when?)– Need to consider relevant performance criteria4Performance Criteria• Throughput– How much work does my application complete?• Latency (promptness)– How long might my application pause (due to amemory management)?• Memory footprint– How much memory is required by theapplication above what’s needed for its work?5Garbage Collection (GC)• At any point during execution, can dividethe objects in the heap into two classes:– Live objects will be used later– Dead objects will never be used again• They are garbage• Idea: Can reuse memory from dead objects6Many GC Techniques• We can’t know for sure which objects arereally live or dead– Undecidable, like solving the halting problem• Thus we need to make an approximation– OK if we decide something is live when it’s not– But we’d better not deallocate an object thatwill be used later on7Reachability• An object is reachable if it can be accessed bychasing pointers from live data• Safe policy: delete unreachable objects– An unreachable object can never be accessed again bythe program (the object is definitely garbage).– A reachable object may be accessed in the future (theobject could be garbage but will be retained anyway).• Could lead to memory leaks• How to implement reachability?– What data is live?– How to perform pointer chasing?8Roots• At a given program point, we define liveness asbeing data reachable from the root set:– Global variables (i.e., static fields)– Local variables of all live method activations (i.e., thestack)• At the machine level, we also consider the registerset (usually stores local or global variables)• Next: techniques for pointer chasing9Reference Counting• Old technique (1960)• Each object tracks the number of pointers to itfrom other objects and from the roots.– When count reaches 0, object can be deallocated• Counts incremented/decremented by the compiler(auto) or by hand (manual) when programstatements create or remove aliases.10Reference Counting Examplestack11211Reference Counting Examplestack1121112Reference Counting Examplestack1121113Reference Counting Examplestack11211014Reference Counting Examplestack1 21115Reference Counting Examplestack1 211 016Reference Counting Examplestack117Tradeoffs with Ref Counting• Advantage: Incremental technique– Small amount of work per memory write– With more effort, can bound running time• Useful for real-time systems• Problems:– Data on cycles can’t be collected; counts never go to 0– Cascading decrements can be expensive• E.g., when an aggregate data structure that is dropped18Mark and Sweep GC• Idea: Only objects reachable from stackcould possibly be live– Every so often, stop the world and do GC:• Mark all objects on stack as live• Until no more reachable objects,– Mark object reachable from live object as live• Deallocate any non-reachable objects• This is a tracing garbage collector19Mark and Sweep Examplestack20Mark and Sweep Examplestack21Mark and Sweep Examplestack22Mark and Sweep Examplestack23Mark and Sweep Examplestack24Mark and Sweep Examplestack25Mark and Sweep Examplestack26Tradeoffs with Mark and Sweep• Pros:– No problem with cycles– Memory writes/dropped aliases have no cost• Cons:– Fragmentation– Cost proportional to heap size• Sweep phase needs to traverse whole heap27Copying GC• Like mark and sweep, but only touches liveobjects– Divide heap into two equal parts (semispaces)– Only one semispace active at a time– GC copies data from one to the other• Trace the live data starting from the stack• Copy live data into other semispace• Declare everything in current semispace dead;switch to other semispace28Copying GC Examplestack29Copying GC Examplestack①①30Copying GC Examplestack①①②②31Copying GC Examplestack①①②②③③32Copying GC Tradeoffs• Pros:– Only touches live data– No fragmentation; automatically compacts• Will probably increase locality• Cons:– Requires twice the memory space– Like mark and sweep, need to stop the world33The Generational PrincipleObject lifetime increases ⇒More objects live ⇒“Youngobjectsdie quickly;old objectskeep living”34Generational Collection• Divide heap into generations• Objects that survive many collections getpushed into older generations– Older generations collected less often– Need to track pointers from old to younggenerations to use as roots for young generationcollection• Usually implemented with a “write barrier”35HotSpot SDK 1.4.2 Collector• Multi-generational, hybrid collector– Young gen : stop and copy collector– Tenured gen : mark and sweep collector– Permanent gen : no collection• Why does using a copy collector for theyoungest generation make sense?• What apps will be penalized by this setup?36Stopping the World• What if the program (the “mutator”) ismodifying the heap while the GC isrunning?• Simplest thing: stop the world during a GC• Problem: big performance impact forparallel programs.37Scaling up GC• Incremental collection– GC runs in mutator thread, but runs only for a shorttime and then resumes• Concurrent collection– GC thread runs in parallel with the mutator• Parallel collection– Many GC threads, all running in parallel• All techniques require read/write barriers, whichcan be expensive38HotSpot VM• Parallel collection of young space– Easy: each thread has its own young generation• Concurrent collection of tenured space• Incremental collection of tenured space– Does a little work with each minor collection• All enabled by separate flags39Metronome• GC developed by IBM research, targettingreal-time systems.• Uses parallel, concurrent collection• Can provide strong guarantees of pause timeand throughput.40What Does GC Mean to You?• Ideally, nothing– It should make your life easier– And
View Full Document
Unlocking...