CS 421 Lecture 13: Run-time systems and garbage collection Lecture outline Execution of dynamic languages Sun HotSpot run-time system for Java Tags, JIT compilation, reflection Memory managementMemory layout; definition of “garbage”Memory layout; definition of “garbage” Reference-counting Garbage collection Non-compacting (mark-and-sweep) Compacting6/29/20091Dynamic languages Automatic memory management Tagged values For GC, run-time type-checking, reflection Sometimes: Dynamic type-checking Reflection Usually: Execute virtual machine code Will use Sun HotSpot Java virtual machine as example6/29/20092Java HotSpot run-time system Developed around 1999 – replaced existing widely-used Java VM Described in several places, e.g.: http://java.sun.com/products/hotspot/whitepaper.html HotSpot is VM used in java program, and embedded in many browsersmany browsers(Note re: above document – word “compiler” used to refer to translator from Java bytecode to native machine code, not translator from source code.)6/29/20093Java HotSpot run-time system Garbage collection Two-word object headers Executes .class files (Java VM code) “Just-in-time” compilationMeta-objects represented as objectsMeta-objects represented as objects6/29/20094Meta-objects represented as objects Class and Method are classes Each class corresponds to a Class object Methods of class Class include getDeclaredMethods(), getFields(), … Each method corresponds to a Method objectMethods of class Method include getParameterTypes, Methods of class Method include getParameterTypes, getReturnType, … Can invoke methods that are detected dynamically –e.g., search all objects reachable from one object – and invoke method print on any object whose class contains a print method.6/29/20095Two-word headers Every object in heap is preceded by two words First word is pointer to Class object of this method’s class (which gives layout of object) Second word contains GC info Arrays contain third word giving length6/29/20096Just-in-time compilation Methods obtained in bytecode form (.class files) translated to native machine code on the fly Numerous optimizations employed Very important optimization: inlining Level of optimization determined by monitoring execution Heavily used methods are optimized, and possibly reoptimized more aggressively Because this is the most innovative aspect of HotSpot, it is the main topic of many HotSpot papers.6/29/20097Automatic memory management Memory in heap consists of objects containing pointers to other objects. Objects in heap are accessed in program by using pointers stored in local variables, which are on stack. Therefore, only heap objects that matter are reachableeither directly from stack, or from fields of other either directly from stack, or from fields of other reachable heap objects Objects that are not reachable are called garbage. Automatic memory management attempts to make garbage cells available for allocation.6/29/20098Creation of garbage Example:let f n y = let x = numbers 1 n (* list [1;2;…;n] *)in x@yCreates n“cons cells” of garbage, because x@y makes a Creates n“cons cells” of garbage, because x@y makes a copy of x.6/29/20099Representing free memory Alternatives: free list or free area Free list: Free memory is placed on a linked list. Request for memory iterates over list looking for big enough memory area. Free area: Unused area of memory reserved for allocation. Memory allocated from bottom of this area.Will discuss free list representation firstWill discuss free list representation first6/29/200910History of heap object, using “free list” system Heap contains: Data that have been allocated Data on free listin usefree6/29/200911(Pointers from stack, and between reachable cells are not shown.)free list pointerHistory of heap object, using “free list” system Program executes: x = new C(); or x = malloc(); or x = a::b(x a local variable of function f)6/29/200912free list pointerHistory of heap object, using “free list” system Return from f. Assume no other objects point to the new object. New object no longer reachablefrom stacklonger reachable (but not allocatable either)6/29/200913free list pointerstackHistory of heap object, using “free list” systemEventually, object is returned to free list6/29/200914free list pointerThree types of memory cellsAllocatable – i.e., on free list Initially contains all cellsReachable Obtained by request for heap memory Still reachable from stack (possibly via other heap objects)NeitherNeither Once reachable, now not –e.g., was reachable from a local variable of function f, but have returned from f Was not returned to free list “Neither” category is most interesting – memory could be made allocatable.6/29/200915Reference counting Use free list Track number of pointers to every object Adjust count each time a pointer is copied/assigned“p = q”: Increment refcnt(*q)Decrement refcnt(*p)Decrement refcnt(*p)if refcnt(*p)=0 then return *p to free listand decrement refcnt of allobjects that *p points toAll objects go to free list as soon as they are non-reachable – no “neither” category6/29/200916Reference counting (cont.) Advantages Cost spread out over computation Disadvantages Cannot easily handle cycles among objects (which occur a lot)216/29/2009172111remove pointerGarbage collection Two methods Non-copying (mark-and-sweep) Uses free list representation Copying Uses free area representationUnlike reference-counting:Unlike reference-counting: Cells go into “neither” category temporarily Are recovered all at once Costs vary according to method, but happen all at once – “GC pause” – and are not amortized6/29/200918Non-copying garbage collection Use free list Reserve one bit in each object header, called the “reachable” bit Start with reachable bit zero in every headerTraverse reachable data, setting reachable bitTraverse reachable data, setting reachable bit Iterate over entire heap. If reachable bit is 1, reset it; if it is zero, place that memory chunk on free listObservations Reachable data is not moved Reachable data remains spread across memory
View Full Document
Unlocking...