Question? Leave a message!




Run-Time Environments

Run-Time Environments
RunTime Environments www.ThesisScientist.comOutline  Compiler must do the storage allocation and provide access to variables and data  Memory management  Stack allocation  Heap management  Garbage collection www.ThesisScientist.comStorage Organization www.ThesisScientist.comStatic vs. Dynamic Allocation  Static: Compile time, Dynamic: Runtime allocation  Many compilers use some combination of following  Stack storage: for local variables, parameters and so on  Heap storage: Data that may outlive the call to the procedure that created it  Stack allocation is a valid allocation for procedures since procedure calls are nested www.ThesisScientist.comSketch of a quicksort program www.ThesisScientist.comActivation for Quicksort www.ThesisScientist.comActivation tree representing calls during an execution of quicksort www.ThesisScientist.comActivation records  Procedure calls and returns are usaully managed by a runtime stack called the control stack.  Each live activation has an activation record (sometimes called a frame)  The root of activation tree is at the bottom of the stack  The current execution path specifies the content of the stack with the last activation has record in the top of the stack. www.ThesisScientist.comA General Activation Record www.ThesisScientist.comActivation Record  Temporary values  Local data  A saved machine status  An “access link”  A control link  Space for the return value of the called function  The actual parameters used by the calling procedure www.ThesisScientist.comDownwardgrowing stack of activation records www.ThesisScientist.comDesigning Calling Sequences  Values communicated between caller and callee are generally placed at the beginning of callee’s activation record  Fixedlength items: are generally placed at the middle  Items whose size may not be known early enough: are placed at the end of activation record  We must locate the topofstack pointer judiciously: a common approach is to have it point to the end of fixed length fields. www.ThesisScientist.comDivision of tasks between caller and callee www.ThesisScientist.comcalling sequence  The caller evaluates the actual parameters  The caller stores a return address and the old value of topsp into the callee's activation record.  The callee saves the register values and other status information.  The callee initializes its local data and begins execution. www.ThesisScientist.comcorresponding return sequence  The callee places the return value next to the parameters  Using information in the machinestatus field, the callee restores topsp and other registers, and then branches to the return address that the caller placed in the status field.  Although topsp has been decremented, the caller knows where the return value is, relative to the current value of topsp; the caller therefore may use that value. www.ThesisScientist.comAccess to dynamically allocated arrays www.ThesisScientist.comML  ML is a functional language  Variables are defined, and have their unchangeable values initialized, by a statement of the form: val (name) = (expression)  Functions are defined using the syntax: fun (name) ( (arguments) ) = (body)  For function bodies we shall use letstatements of the form: let (list of definitions) in (statements) end www.ThesisScientist.comA version of quicksort, in ML style, using nested functions www.ThesisScientist.comAccess links for finding nonlocal data www.ThesisScientist.comSketch of ML program that uses function parameters www.ThesisScientist.comActual parameters carry their access link with them www.ThesisScientist.comMaintaining the Display www.ThesisScientist.comMaintaining the Display (Cont.) www.ThesisScientist.comMemory Manager  Two basic functions:  Allocation  Deallocation  Properties of memory managers:  Space efficiency  Program efficiency  Low overhead www.ThesisScientist.comTypical Memory Hierarchy Configurations www.ThesisScientist.comLocality in Programs The conventional wisdom is that programs spend 90 of their time executing 10 of the code:  Programs often contain many instructions that are never executed.  Only a small fraction of the code that could be invoked is actually executed in a typical run of the program.  The typical program spends most of its time executing innermost loops and tight recursive cycles in a program. www.ThesisScientist.comPart of a Heap www.ThesisScientist.comReference Counting MarkandSweep ShortPause Methods www.ThesisScientist.comThe Essence  Programming is easier if the runtime system “garbagecollects” makes space belonging to unusable data available for reuse.  Java does it; C does not.  But stack allocation in C gets some of the advantage. www.ThesisScientist.comDesiderata 1. Speed low overhead for garbage collector. 2. Little program interruption.  Many collectors shut down the program to hunt for garbage. 3. Locality data that is used together is placed together on pages, cachelines. www.ThesisScientist.comThe Model (1)  There is a root set of data that is apriori reachable.  Example: In Java, root set = static class variables plus variables on runtime stack.  Reachable data : root set plus anything referenced by something reachable. www.ThesisScientist.comThe Model (2)  Things requiring space are “objects.”  Available space is in a heap large area managed by the runtime system.  Allocator finds space for new objects.  Space for an object is a chunk.  Garbage collector finds unusable objects, returns their space to the heap, and maybe moves objects around in the heap. www.ThesisScientist.comA Heap Free List . . . Object 2 Object 3 Object 1 www.ThesisScientist.comTaxonomy Garbage Collectors Trace Reference Counters Based www.ThesisScientist.comReference Counting  The simplest (but imperfect) method is to give each object a reference count = number of references to this object.  OK if objects have no internal references.  Initially, object has one reference.  If reference count becomes 0, object is garbage and its space becomes available. www.ThesisScientist.comExamples Integer i = new Integer(10);  Integer object is created with RC = 1. j = k; (j, k are Integer references.)  Object referenced by j has RC.  Object referenced by k has RC++. www.ThesisScientist.comTransitive Effects  If an object reaches RC=0 and is collected, the references within that object disappear.  Follow these references and decrement RC in the objects reached.  That may result in more objects with RC=0, leading to recursive collection. www.ThesisScientist.comExample: Reference Counting Root Object A(1) B(2) C(1) D(2) E(1) www.ThesisScientist.comExample: Reference Counting Root Object A(0) B(2) C(1) D(2) E(1) www.ThesisScientist.comExample: Reference Counting Root Object B(1) C(0) D(2) E(1) www.ThesisScientist.comExample: Reference Counting Root Object B(1) B, D, and E are garbage, but their reference counts are all 0. They D(1) E(1) never get collected. www.ThesisScientist.comTaxonomy Garbage Collectors Reference Trace Counters Based StoptheWorld ShortPause Markand Markand Sweep Compact Basic www.ThesisScientist.comFour States of Memory Chunks 1. Free = not holding an object; available for allocation. 2. Unreached = Holds an object, but has not yet been reached from the root set. 3. Unscanned = Reached from the root set, but its references not yet followed. 4. Scanned = Reached and references followed. www.ThesisScientist.comMarking 1. Assume all objects in Unreached state. 2. Start with the root set. Put them in state Unscanned. 3. while Unscanned objects remain do examine one of these objects; make its state be Scanned; add all referenced objects to Unscanned if they have not been there; end; www.ThesisScientist.comSweeping  Place all objects still in the Unreached state into the Free state.  Place all objects in Scanned state into the Unreached state.  To prepare for the next markandsweep. www.ThesisScientist.comTaxonomy Garbage Collectors Reference Trace Counters Based StoptheWorld ShortPause Markand Markand Sweep Compact BasicBaker’s www.ThesisScientist.comBaker’s Algorithm (1)  Problem: The basic algorithm takes time proportional to the heap size.  Because you must visit all objects to see if they are Unreached.  Baker’s algorithm keeps a list of all allocated chucks of memory, as well as the Free list. www.ThesisScientist.comBaker’s Algorithm (2)  Key change: In the sweep, look only at the list of allocated chunks.  Those that are not marked as Scanned are garbage and are moved to the Free list.  Those in the Scanned state are put in the Unreached state.  For the next collection. www.ThesisScientist.comTaxonomy Garbage Collectors Reference Trace Counters Based StoptheWorld ShortPause Markand Markand Sweep Compact BasicBaker’s Basic www.ThesisScientist.comIssue: Why Compact  Compact = move reachable objects to contiguous memory.  Locality fewer pages or cachelines needed to hold the active data.  Fragmentation available space must be managed so there is space to store large objects. www.ThesisScientist.comMarkandCompact 1. Mark reachable objects as before. 2. Maintain a table (hash) from reached chunks to new locations for the objects in those chunks.  Scan chunks from low end of heap.  Maintain pointer free that counts how much space is used by reached objects so far. www.ThesisScientist.comMarkandCompact (2) 3. Move all reached objects to their new locations, and also retarget all references in those objects to the new locations.  Use the table of new locations. 4. Retarget root references. www.ThesisScientist.comExample: MarkandCompact free www.ThesisScientist.comExample: MarkandCompact free www.ThesisScientist.comExample: MarkandCompact free www.ThesisScientist.comExample: MarkandCompact free www.ThesisScientist.comExample: MarkandCompact free www.ThesisScientist.comExample: MarkandCompact free www.ThesisScientist.comExample: MarkandCompact free www.ThesisScientist.comExample: MarkandCompact free www.ThesisScientist.comExample: MarkandCompact free www.ThesisScientist.comTaxonomy Garbage Collectors Reference Trace Counters Based StoptheWorld ShortPause Markand Markand Sweep Compact BasicBaker’s BasicCheney’s A different Cheney, BTW, so no jokes, please. www.ThesisScientist.comCheney’s Copying Collector  A shotgun approach to GC.  2 heaps: Allocate space in one, copy to second when first is full, then swap roles.  Maintain table of new locations.  As soon as an object is reached, give it the next free chunk in the second heap.  As you scan objects, adjust their references to point to second heap. www.ThesisScientist.comTaxonomy Garbage Collectors Reference Trace Counters Based StoptheWorld ShortPause Markand Markand Incremental Partial Sweep Compact BasicBaker’s BasicCheney’s www.ThesisScientist.comShortPause GarbageCollection 1. Incremental run garbage collection in parallel with mutation (operation of the program). 2. Partial stop the mutation, but only briefly, to garbage collect a part of the heap. www.ThesisScientist.comProblem With Incremental GC  OK to mark garbage as reachable.  Not OK to GC a reachable object.  If a reference r within a Scanned object is mutated to point to an Unreached object, the latter may be garbagecollected anyway.  Subtle point: How do you point to an Unreached object www.ThesisScientist.comOne Solution: Write Barriers  Intercept every write of a reference in a scanned object.  Place the new object referred to on the Unscanned list.  A trick: protect all pages containing Scanned objects.  A hardware interrupt will invoke the fixup. www.ThesisScientist.comTaxonomy Garbage Collectors Reference Trace Counters Based StoptheWorld ShortPause Markand Markand Incremental Partial Sweep Compact BasicBaker’s BasicCheney’s Generational www.ThesisScientist.comThe Object LifeCycle  “Most objects die young.”  But those that survive one GC are likely to survive many.  Tailor GC to spend more time on regions of the heap where objects have just been created.  Gives a better ratio of reclaimed space per unit time. www.ThesisScientist.comPartial Garbage Collection  We collect one part(ition) of the heap.  The target set.  We maintain for each partition a remembered set of those objects outside the partition (the stable set) that refer to objects in the target set.  Write barriers can be used to maintain the remembered set. www.ThesisScientist.comCollecting a Partition  To collect a part of the heap: 1. Add the remembered set for that partition to the root set. 2. Do a reachability analysis as before.  Note the resulting Scanned set may include garbage. www.ThesisScientist.comExample: “Reachable” Garbage In the remembered set The target Not reached from partition the root set Stable set www.ThesisScientist.comGenerational Garbage Collection  Divide the heap into partitions P0, P1,…  Each partition holds older objects than the one before it.  Create new objects in P0, until it fills up.  Garbage collect P0 only, and move the reachable objects to P1. www.ThesisScientist.comGenerational GC (2)  When P1 fills, garbage collect P0 and P1, and put the reachable objects in P2.  In general: When Pi fills, collect P0, P1,…,Pi and put the reachable objects in P(i +1). www.ThesisScientist.comTaxonomy Garbage Collectors Reference Trace Counters Based StoptheWorld ShortPause Markand Markand Incremental Partial Sweep Compact BasicBaker’s BasicCheney’s GenerationalTrain www.ThesisScientist.comThe Train Algorithm  Problem with generational GC: 1. Occasional total collection (last partition). 2. Longlived objects move many times.  Train algorithm useful for longlived objects.  Replaces the highernumbered partitions in generational GC. www.ThesisScientist.comPartitions = “Cars” Car 11 Car 12 Car 13 Train 1 Car 21 Car 22 . . . Car 2k Train 2 . . . Car n1 Car n2 Train n www.ThesisScientist.comOrganization of Heap  There can be any number of trains, and each train can have any number of cars.  You need to decide on a policy that gives a reasonable number of each.  New objects can be placed in last car of last train, or start a new car or even a new train. www.ThesisScientist.comGarbageCollection Steps 1. Collect the first car of the first train. 2. Collect the entire first train if there are no references from the root set or other trains.  Important: this is how we find and eliminate large, cyclic garbage structures. www.ThesisScientist.comRemembered Sets  Each car has a remembered set of references from later trains and later cars of the same train.  Important: since we only collect first cars and trains, we never need to worry about “forward” references (to later trains or later cars of the same train). www.ThesisScientist.comCollecting the First Car of the First Train  Do a partial collection as before, using every other car/train as the stable set.  Move all Reachable objects of the first car somewhere else.  Get rid of the car. www.ThesisScientist.comMoving Reachable Objects  If object o has a reference from another train, pick one such train and move o to that train.  Same car as reference, if possible, else make new car.  If references only from root set or first train, move o to another car of first train, or create new car. www.ThesisScientist.comPanic Mode  The problem: it is possible that when collecting the first car, nothing is garbage.  We then have to create a new car of the first train that is essentially the same as the old first car. www.ThesisScientist.comPanic Mode (2)  If that happens, we go into panic mode, which requires that: 1. If a reference to any object in the first train is rewritten, we make the new reference a “dummy” member of the root set. 2. During GC, if we encounter a reference from the “root set,” we move the referenced object to another train. www.ThesisScientist.comPanic Mode (3)  Subtle point: If references to the first train never mutate, eventually all reachable objects will be sucked out of the first train, leaving cyclic garbage.  But perversely, the last reference to a firsttrain object could move around so it is never to the first car. www.ThesisScientist.com
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.MasonHanks
User Type:
Teacher
Country:
Germany
Uploaded Date:
23-07-2017