Generational CollectionGenerational Collectionldots Generational Collectionldots Generational Collectionldots Generational Collection -- After GC($G_0$)Generational Collectionldots Remembering Back PointersRemembering Back PointersRemembering Back PointersRemembering Back Pointersldots Remembering Back Pointersldots Remembering Back Pointersldots Readings and References520—Spring 2005—41CSc 520Principles of ProgrammingLanguages41: Garbage Collection — GenerationalCollectionChristian [email protected] of Computer ScienceUniversity of ArizonaCopyrightc 2005 Christian Collberg[1]520—Spring 2005—41Generational CollectionWorks best for functional and logic languages (LISP,Prolog, ML, ...) because1. they rarely modify allocated cells2. newly created objects only point to older objects((CONS A B) creates a new two-pointer cell withpointers to old objects),3. new cells are shorter lived than older cells, and oldobjects are unlikely to die anytime soon.[2]520—Spring 2005—41Generational Collection...Generational Collection therefore1. divides the heap intogenerations, G0is theyoungest, Gnthe oldest.2. allocates new objects inG0.3. GC’s only newer generations.We have to keep track of back pointers (from oldgenerations to new).[3]520—Spring 2005—41Generational Collection...Functional Language:(cons ’a ’(b c))mt1: x ← new ’(b c);t2: y ← new ’a;t3: return new cons(x, y)A new object (created at time t3) points to older objects.Object Oriented Language:t1: T ← new Table(0);t2: x ← new Integer(5);t3: T.insert(x);A new object (created at time t2) is inserted into an older object, whichthen points to the news object.[4]520—Spring 2005—41Generational Collection...Remembered Set:Roots:G0G1G2[5]520—Spring 2005—41Generational Collection – After GC(G0)Remembered Set:Roots:G1G2G00[6]520—Spring 2005—41Generational Collection...Since old objects (in Gn· · · G1) are rarely changed (topoint to new objects) they are unlikely to point intoG0.Apply the GC only to the youngest generation (G0),since it is most likely to contain a lot of garbage.Use the stack and globals as roots.There might be some back pointers, pointing from anolder generation intoG0. Maintain a special set of suchpointers, and use them as roots.Occasionally GC older (G1· · · Gk) generations.Use either mark-and-sweep or copying collection to GCG0.[7]520—Spring 2005—41Remembering Back Pointers[8]520—Spring 2005—41Remembering Back PointersRemembered ListAfter each pointer update x.f := · · ·, the compiler addscode to insert x in a list of updated memory locations:x↑.f := · · ·⇓x↑.f := · · ·;insert(UpdatedList, x);[9]520—Spring 2005—41Remembering Back PointersRemembered SetAs above, but set a bit in the updated object so that it isinserted only once in the list:x↑.f := · · ·⇓x↑.f := · · ·;IF NOT x↑.inserted THENinsert(UpdatedList, x);x.↑inserted := TRUE;ENDIF[10]520—Spring 2005—41Remembering Back Pointers...Card markingDivide the heap into “cards” of size 2k.Keep an array dirty of bits, indexed by card number.After a pointer update x↑.f := · · ·, set the dirty bit forcard c that x is on:x↑.f := · · ·⇓x↑.f := · · ·;dirty[x div2k] := TRUE;[11]520—Spring 2005—41Remembering Back Pointers...Page marking ISimilar to Card marking, but let the cards be virtualmemory pages.When x is updated the VM system automatically setsthe dirty bit of the page that x is on.We don’t have to insert any extra code![12]520—Spring 2005—41Remembering Back Pointers...Page marking IIThe OS may not let us read the VM system’s dirty bits.Instead, we write-protect the page x is on.On an update x↑.f := · · · a protection fault isgenerated. We catch this fault and set a dirty bitmanually.We don’t have to insert any extra code![13]520—Spring 2005—41Readings and ReferencesRead Scott, pp.
View Full Document
Unlocking...