15 213 The course that gives CMU its Zip Memory Management II Dynamic Storage Allocation Mar 7 2000 Topics Segregated free lists Buddy system Garbage collection Mark and Sweep Copying Reference counting class15 ppt Basic allocator mechanisms Sequential fits implicit or explicit single free list best fit first fit or next fit placement various splitting and coalescing options splitting thresholds immediate or deferred coalescing Segregated free lists simple segregated storage separate heap for each size class segregated fits separate linked list for each size class buddy systems class15 ppt 2 CS 213 S 00 Segregate Each size class has Storage its own collection of blocks 1 2 3 4 5 8 9 16 Often have separate collection for every small size 2 3 4 For larger sizes typically have a collection for each power of 2 class15 ppt 3 CS 213 S 00 Simple segregated Separate heap and freestorage list for each size class No splitting To allocate a block of size n if free list for size n is not empty allocate first block on list note list can be implicit or explicit if free list is empty get a new page create new free list from all blocks in page allocate first block on list constant time To free a block Add to free list If page is empty return the page for use by another size optional Tradeoffs fast but can fragment badly class15 ppt 4 CS 213 S 00 Segregated fits Array of free lists each one for some size class To allocate a block of size n search appropriate free list for block of size m n if an appropriate block is found split block and place fragment on appropriate list optional if no block is found try next larger class repeat until block is found To free a block coalesce and place on appropriate list optional Tradeoffs faster search than sequential fits i e log time for power of two size classes controls fragmentation of simple segregated storage coalescing can increase search times deferred coalescing can help class15 ppt 5 CS 213 S 00 Buddy systems Special case of segregated fits all blocks are power of two sizes Basic idea Heap is 2m words Maintain separate free lists of each size 2k 0 k m Requested block sizes are rounded up to nearest power of 2 Originally one free block of size 2m class15 ppt 6 CS 213 S 00 Buddy systems cont To allocate a block of size 2k Find first available block of size 2j s t k j m if j k then done otherwise recursively split block until j k Each remaining half is called a buddy and is placed on the appropriate free list 2m buddy buddy buddy class15 ppt 7 CS 213 S 00 Buddy systems cont To free a block of size 2k continue coalescing with buddies while the buddies are free Block to free buddy buddy buddy Not free done Added to appropriate free list class15 ppt 8 CS 213 S 00 Buddy systems cont Key fact about buddy systems given the address and size of a block it is easy to compute the address of its buddy e g block of size 32 with address xxx x00000 has buddy xxx x10000 Tradeoffs fast search and coalesce subject to internal fragmentation class15 ppt 9 CS 213 S 00 Internal fragmentation Internal fragmentation is wasted space inside allocated blocks minimum block size larger than requested amount e g due to minimum free block size free list overhead policy decision not to split blocks e g buddy system Much easier to define and measure than external fragmentation class15 ppt 10 CS 213 S 00 Implicit Memory Management Garbage collector Garbage collection automatic reclamation of heapallocated storage application never has to free void foo int p malloc 128 return p block is now garbage Common in functional languages scripting languages and modern object oriented languages Lisp ML Java Perl Mathematica Variants conservative garbage collectors exist for C and C Cannot collect all garbage class15 ppt 11 CS 213 S 00 Garbage Collection How does the memory manager know when memory can be freed In general we cannot know what is going to be used in the future since it depends on conditionals But we can tell that certain blocks cannot be used if there are no pointers to them Need to make certain assumptions about pointers Memory manager can distinguish pointers from non pointers All pointers point to the start of a block Cannot hide pointers e g by coercing them to an int and then back again class15 ppt 12 CS 213 S 00 Classical GC algorithms Mark and sweep collection McCarthy 1960 Does not move blocks unless you also compact Reference counting Collins 1960 Does not move blocks Copying collection Minsky 1963 Moves blocks For more information see Jones and Lin Garbage Collection Algorithms for Automatic Dynamic Memory John Wiley Sons 1996 class15 ppt 13 CS 213 S 00 Memory as a We view memory as a directed graph graph Each block is a node in the graph Each pointer is an edge in the graph Locations not in the heap that contain pointers into the heap are called root nodes e g registers locations on the stack global variables Root nodes Heap nodes reachable Not reachable garbage A node block is reachable if there is a path from any root to that node Non reachable nodes are garbage never needed by the application class15 ppt 14 CS 213 S 00 Assumptions for this lecture Application new n returns pointer to new block with all locations cleared read b i read location i of block b into register write b i v write v into location i of block b Each block will have a header word addressed as b 1 for a block b Used for different purposes in different collectors Instructions used by the Garbage Collector is ptr p determines whether p is a pointer length b returns the length of block b not including the header get roots returns all the roots class15 ppt 15 CS 213 S 00 Mark and sweep collecting Can build on top of malloc free package Allocate using malloc until you run out of space When out of space Use extra mark bit in the head of each block Mark Start at roots and set mark bit on all reachable memory Sweep Scan all blccks and free blocks that are not marked Mark Bit Set root Before mark After mark After sweep class15 ppt free free 16 CS 213 S 00 Mark and sweep cont Mark using depth first traversal of the memory graph ptr mark ptr p if is ptr p return if markBitSet p return setMarkBit p for i 0 i length p i mark p i return do nothing if not pointer check if already marked set the mark bit mark all children Sweep using lengths to find next block ptr sweep ptr p ptr end while p end if markBitSet p clearMarkBit else if allocateBitSet p free p p length p class15 ppt 17 CS 213 S 00 Mark and sweep in C A
View Full Document
Unlocking...