Memory Management I:Dynamic Storage AllocationMarch 2, 2000Topics• Explicit memory allocation• Data structures• Mechanismsclass14.ppt15-213“The course that gives CMU its Zip!”CS 213 S’00– 2 –class14.pptHarsh Reality #3Memory MattersMemory is not unbounded• It must be allocated and managed• Many applications are memory dominated–Especially those based on complex, graph algorithmsMemory referencing bugs especially pernicious• Effects are distant in both time and spaceMemory performance is not uniform• Cache and virtual memory effects can greatly affect program performance• Adapting program to characteristics of memory system can lead tomajor speed improvementsCS 213 S’00– 3 –class14.pptDynamic Storage AllocationExplicit vs. Implicit Storage Allocator• Explicit: application allocates and frees space –E.g., malloc and free in C• Implicit: application allocates, but does not free space–E.g. garbage collection in Java, ML or LispAllocation• In both cases the storage allocator provides an abstraction of memory as a set of blocks• Doles out free memory blocks to applicationWill discuss explicit storage allocation todayApplicationDynamic Storage AllocatorHeap MemoryCS 213 S’00– 4 –class14.pptProcess memory imagekernel virtual memoryMemory mapped region forshared librariesrun-time heap (via malloc)program text (.text)initialized data (.data)uninitialized data (.bss)stack0%espmemory invisible touser codethe “brk” ptrCS 213 S’00– 5 –class14.pptMalloc packagevoid *malloc(int size)• if successful:–returns a pointer to a memory block of at least size bytes–if size==0, returns NULL• if unsuccessful: returns NULLvoid free(void *p)• returns the block pointed at by p to pool of available memory• p must come from a previous call to malloc().Assumptions made in this lecture• memory is word addressed (each word can hold a pointer)Allocated block(4 words)Free block(3 words)Free wordAllocated wordCS 213 S’00– 6 –class14.pptAllocation examplep1 = malloc(4)p2 = malloc(5)p3 = malloc(6)free(p2)p4 = malloc(2)CS 213 S’00– 7 –class14.pptConstraintsApplications:• Can issue arbitrary sequence of allocation and free requests• Free requests must correspond to an allocated blockAllocators• Can’t control number or size of allocated blocks• Must respond immediately to all allocation requests–i.e., can’t reorder or buffer requests• Must allocate blocks from free memory–i.e., can only place allocated blocks in free memory• Must align blocks so they satisfy all alignment requirements–usually 8 byte alignment• Can only manipulate and modify free memory• Can’t move the allocated blocks once they are allocated–i.e., compaction is not allowedCS 213 S’00– 8 –class14.pptGoals of good malloc/free Primary goals• Good time performance for malloc and free–Ideally should take constant time (not always possible)–Should certainly not take linear time in the number of blocks• Good space usage–User allocated structures should be large fraction of operating-system allocated pages–Need to avoid fragmentationSome other goals• Good locality properties–structures allocated close in time should be close in space–“similar” objects should be allocated close in space• Robust–can check that free(p1) is on a valid allocated object p1–can check that memory references are to allocated spaceCS 213 S’00– 9 –class14.pptFragmentationp1 = malloc(4)p2 = malloc(5)p3 = malloc(6)free(p2)p4 = malloc(6)oops!Tendency for free blocks to become smaller over time leading towasted spaceNo general solution assuming we cannot move blocksWe will consider several heuristicsCS 213 S’00– 10 –class14.pptImplementation issues• How do we know how much memory to free just given a pointer?• How do we keep track of the free blocks?• What do we do with the extra space when allocating a structure that is smaller than the free block it is placed in?• How do we pick a block to use for allocation -- many might fit?• How do we reinsert freed block?p1 = malloc(1)p0free(p0)CS 213 S’00– 11 –class14.pptKnowing how much to freeStandard method• keep the length of a structure in the word preceeding the structure– This word is often called the header field• requires an extra word for every allocated structurefree(p0)p0 = malloc(4) p0Block size data5CS 213 S’00– 12 –class14.pptKeeping track of free blocks• Method 1: implicit list using lengths -- links all blocks• Method 2: explicit list among the free blocks using pointers within the free blocks• Method 3: segregated free lists• Different free lists for different size classes• Method 4: blocks sorted by size• Can use a balanced tree (e.g. Red-Black tree) with pointers within each free block, and the length used as a key54 2654 26CS 213 S’00– 13 –class14.pptMethod 1: implicit listNeed to identify whether each block is free or allocated• Can use extra bit• Bit can be put in the same word as the size if block sizes are always multiples of two (mask out low order bit when reading size).size1 wordFormat ofallocated andfree blocksdataa = 1: allocated block a = 0: free blocksize: block sizedata: application data(allocated blocks only)aCS 213 S’00– 14 –class14.pptImplicit list: finding a free blockFirst fit:• Search list from beginning, choose first free block that fits• Can take linear time in total number of blocks (allocated and free)• In practice it can cause “splinters” at beginning of listNext fit:• Like first-fit, but search list from location of end of previous search• Does a better job of spreading out the free blocks Best fit:• Search the list, choose the free block with the closest size that fits• Keeps fragments small --- usually helps fragmentation• Will typically run slower than first-fitp = start; while ((p < end) || \\ not passed end(*p & 1) || \\ already allocated(*p <= len)); \\ too smallCS 213 S’00– 15 –class14.pptImplicit list: allocating in a free blockAllocating in a free block - splitting• Since allocated space might be smaller than free space, we need to split the blockvoid addblock(ptr p, int l) {int newsize = ((l + 1) >> 1) << 1; // add 1 and round upint oldsize = *p & -2; // mask out low bit*p = newsize | 1; // set new lengthif (newsize < oldsize)*(p+newsize) = oldsize - newsize; // set length in remaining} // part of
View Full Document
Unlocking...