Unobrusive Garbage CollectionUnobrusive Garbage CollectionIncremental GCIncremental GCldots Incremental GCldots Exam ProblemExam Problem Ildots Exam Problemldots Readings and ReferencesReadings and Referencesldots520 —Spring 2008 — 12CSc 520Principles of ProgrammingLanguages12 : Garbage Collection — DiscussionChristian [email protected] of Computer ScienceUniversity of ArizonaCopyrightc 2008 Christian Collberg[1]520 —Spring 2008 — 12Unobrusive Garbage Collection[2]520 —Spring 2008 — 12Unobrusive Garbage CollectionGC Requirements:batch programs: We want short total GC time.interactive programs: We want unnoticable GCs.Unobtrusive GC:Incremental CollectionDo a little GC-work every time an object is allocated,or a pointer is changed.Concurrent CollectionRun the collector and the program in differentprocesses, or on different processors.[3]520 —Spring 2008 — 12Incremental GCUse copying collection, but rather than stop when yourun out of memory and then do all the GC work in oneshot, do a little bit whenever a pointer variable isreferenced or when a new object is allocated.We start out by forwarding (copying) the objects pointedto by global variables.Then, instead of continuing forwarding recursively, weresume the program.Every time a pointer is referenced we check to seewhether it is pointing into from-space. If it is, weforward that object too.[4]520 —Spring 2008 — 12Incremental GC...Even objects which are not explicitly referenced have tobe checked, to see if they have become garbage.Therefore, every time we allocate a new object weforward k pointers.A good value for k has to be determined byexperimentation.Eventually scan will catch up with next and we switchfrom-space and to-space and start an new cycle.Baker’s algorithm (on the next slide) is a variant ofcopying collection.[5]520 —Spring 2008 — 12Incremental GC...1. Copy and update objects pointed to by global pointersto to-space.2. Resume program.3. When an object in from-space is referenced, first copyit to to-space.p := x ↑.next;⇓ (implemented as)IF x ∈ from − space THENcopy x to to-space;update x, scan, and next;x := x’s new address in to-space;END;p := x ↑.next;4. Every timeNEW is called, k pointers are forwarded.[6]520 —Spring 2008 — 12Exam Problem1. Why is generational collection more appropriate forfunctional and logic languages (such as LISP andProlog), than for object-oriented languages (such asEiffel and Modula-3)?2. The heap in the figure on the next slide holds 7 objects.All objects have one integer field and one or two pointerfields (black dots). The only roots are the three globalvariables X, Y, and Z. Free space is shaded. Show thestate of To-Space after a copying garbage collectionhas been performed on From-Space. Note that severalanswers are possible, depending on the visit strategy(Depth-First or Breadth-First Search) you chose.[7]520 —Spring 2008 — 12Exam Problem I...6XZRoots:SpaceFrom−57 1310128Y[8]520 —Spring 2008 — 12Exam Problem...1. Name five garbage collection algorithms!2. Describe the Deutsch-Schorr-Waite algorithm! When isit used? Why is it used? How does it work?3. What are the differences betweenstop-and-copy,incremental and concurrent garbage collection? Whenwould we prefer one over the other?[9]520 —Spring 2008 — 12Readings and ReferencesRead Scott, pp. 395–401.Apple’s Tiger book, pp. 257–282Topics in advanced language implementation, Chapter4, Andrew Appel, Garbage Collection. Chapter 5, DavidL. Detlefs, Concurrent Garbage Collection for C++.ISBN 0-262-12151-4.Aho, Hopcroft, Ullman. Data Structures and Algorithms,Chapter 12, Memory Management.[10]520 —Spring 2008 — 12Readings and References...Nandakumar Sankaran, A Bibliography on GarbageCollection and Related Topics, ACM SIGPLAN Notices,Volume 29, No. 9, Sep 1994.J. Cohen. Garbage Collection of Linked DataStructures, Computing Surveys, Vol. 13, No. 3,
View Full Document
Unlocking...