MEMORY MANAGEMENT FOR DYNAMIC OBJECTS (Chapter 7) Languages like Oberon and Java encourage allocating lots of objects, and it is hard to keep track of what is currently referenceable and what is no longer referenceable. Thus it is attractive that these languages do not require programmers to write code that explicitly frees objects no longer in use. However, if objects that are no longer referenceable are not returned to the runtime system, the program could run out of (virtual) memory. Speed of memory allocation and reclamation is an issue. Memory Allocation - Dynamic memory allocation of class objects (Heap Management) + Issues - have big memory space (``dynamic'' memory region) - need to hand out and return in small pieces (size of object) - don't like ``fragmentation'', since they break up memory into pieces that may be too small to satisfy memory requests - allocations and dellocations should be fast: minimize searching + Ideas for approach? - treat dynamic region as array of bytes + hand out chunks of array + store array of free chunk indices w/size + search array for for chunk that is big enough + adjust index and size + problem: we don't know size of free array, but it must be fixed - treat as linked list of byte regions + each region stores its own size, so no free array problem + search down list for region that is big enough + adjust pointer and size or delete region from free list - Example: request for 12 bytes (e.g., p = malloc(12)) + search down list looking for fit + really need 16, since need to know size of region when freed + only second segment will work + pointer returned from malloc points to 12 free bytes, size is stored directly before 12 bytes. BEFORE: free --+ dynamic region +-------- | ---------------------------------------------+ | V | | +----+---+----------+ | | | 10 | : | | | | +----+-|-+----------+ | | | ...allocated... | | V | | +----+---+--------------------+ | | | 20 | : | | | | +----+-|-+--------------------+ | | | | | V | | ... | | ...allocated... +----+---+----+ | | | 4 | 0 | | | | +----+-+-+----+ | | | +--------------------------------------------------------+ AFTER: free --+ dynamic region +-------- | ---------------------------------------------+ | V | | +----+---+----------+ | | | 10 | : | | ...allocated... | | +----+-|-+----------+ | | | +---------------------- pointer | V V | returned | +----+---+----+ +--+-------------+ | | | 4 | : | | |12| allocated | | | +----+-|-+----+ +--+-------------+ | | | | | V | | ... | | ...allocated... +----+---+----+ | | | 4 | 0 | | | | +----+-+-+----+ | | | +--------------------------------------------------------+ - when free(p) called + *(int *)(p - 4) contains (size - 4), + put 16 bytes starting at (p - 4) back on free list - search to stick between two nearest segments - if back-to-back with neighboring segments, merge into single, combined segment + avoid fragmentation + keep search of free list short - problems + fragmentation: - long search for `best fit', take first instead - best-fit empirically worse anyway + exact fits are rare + small fragments are less useful than medium or large + time: - linear search for match is expensive - multiple lists of fixed sizes is a possibility (buddy system) + finding correct-sized segment involves finding list of segments containing that size + when nothing in matching list - steal from larger list - put remainder on appropriate list + very large sizes work by usual method + sizes by powers of 2: log-2 of alloc request indexes region - can implement log-2 as array lookup for small sizes - free segments don't have to store sizes - similar scheme for Fibonacci sizes, other series + for OO, have one region per class (or class size) - guaranteed exact fit, no fragmentation - index region by class identifier (integer) - doesn't work for languages like C, hybrid for C++ Garbage Collection - In OO programs, it is hard to tell when program is ``done'' with an object. Need to keep track of what objects might be pointing at it. - One solution is to just not bother, and then kill off program when run out of memory. Good for prototyping; avoids some bugs - Other solution is ``garbage collection'' + Runtime mechanism (read: fancy functions and data structures) for putting unreachable objects back on ``free list'' + Runs in background with minimal programmer intervention - Issues: + Speed: should not require much time + Pauses: should not cause pauses in interactive programs + Space: should not take up too much space + Simple: if hard to implement, will be source of bugs + Adapting: should adapt itself (or be adaptable) to special apps - Any ideas how we should do this? + Reference counting - put a counter in every object - increment when pointer taken - decrement when pointer dropped - when go to 0, free Object *obj1, *obj2; // reference nothing obj1 = Object("a"); // 1 reference to object a obj2 = Object("b"); // 1 reference to object b ... obj1 = obj2 // now both obj1 and obj2 refer to "b", none to "a" - can implement yourself in OO language + derive class from ``reference count'' class + class adds a private counter + define assignment method or overloaded function: - increments count of object pointed to on RHS - decrements count of object pointed to on LHS - if decrement goes to 0, free - don't forget parameter passing - downsides + size (4 bytes per object) + time (10-20%) + cycles of objects may have positive count but no outside reference + Mark-and-sweep - idea: object is ``garbage'' if nothing in program points to it 1. when memory runs low, traverse all pointers from global and stack region, marking everything reached - unmarked objects are ``garbage'' 2. ``sweep'' dynamic region linearly, object-by-object, returning all unmarked objects to free list - can even compact memory, eliminating fragmentation (tricky) - requirements: + need to know type of every object so can follow all its pointers - basically just an additional ``sweep'' method on object + need to know size of every object so can skip to next object linearly in memory during sweep + need to have a basis set of program variables from which all other reachable data can be reached - globals and locals (stack) - need to know how globals and locals are laid out + ST has all needed global information, put into executable + stack is harder, since changing all the time: each frame needs some indicator (tag) which function call it represents, then can use ST for function (compiled into executable) to visit pointers in frame - performance depends a lot on details + object sizes + what happens when memory is nearly full, fragmented + compacting or not ------------- + + + +-+ + +--+--+-| + global | + +-+ + | +-----------+ | + + text | +-----------+ | + oo + (nothing is referring to "oo" here) | + + +---->oo-->oo + dynamic + + +--------->oo + | +-----------+ | + + | +-----------+ | + + | + +-+ + +--+--+-| + stack + +-+ + +-----------+ STEP 1: All mark bits set to 0 (done on alloc or end of prev pass) dynamic region +--------------------------------------------------------+ | | | +-+----+---+ | | |0| 10 | 0 | | | +-+----+---+ | | | | +-+----+---+ +-+----+---+ | ---------------->|0| 20 | :-|-->|0| 8 | 0 | | | +-+----+---+ +-+----+---+ | | | | | | +-+----+---+ | ----------------------->|0| 4 | 0 | | | +-+----+-+-+ | | | +--------------------------------------------------------+ STEP 2: Trace pointers, starting from globals and stack, marking all found objects +--------------------------------------------------------+ | | | +-+----+---+ | | |0| 10 | 0 | | | +-+----+---+ | | | | +-+----+---+ +-+----+---+ | ---------------->|1| 20 | :-|-->|1| 8 | 0 | | | +-+----+---+ +-+----+---+ | | | | | | +-+----+---+ | ----------------------->|1| 4 | 0 | | | +-+----+-+-+ | | | +--------------------------------------------------------+ STEP 3: Sweep dynamic region from beginning to end, all umarked objects are put on free list (not shown), mark bits are reset +--------------------------------------------------------+ | | | | | | | | | | | +-+----+---+ +-+----+---+ | ---------------->|0| 20 | :-|-->|0| 8 | 0 | | | +-+----+---+ +-+----+---+ | | | | | | +-+----+---+ | ----------------------->|0| 4 | 0 | | | +-+----+-+-+ | | | +--------------------------------------------------------+