Slide 1Last Time: Dynamic Memory AllocationLast Time: FragmentationTodayKeeping Track of Free BlocksImplicit ListExample (Blackboard?)Implicit List: Finding a Free BlockImplicit List: Finding a Free BlockImplicit List: Allocating in Free BlockImplicit List: Allocating in Free BlockImplicit List: Freeing a BlockImplicit List: CoalescingImplicit List: Bidirectional CoalescingConstant Time CoalescingConstant Time Coalescing (Case 1)Constant Time Coalescing (Case 2)Constant Time Coalescing (Case 3)Constant Time Coalescing (Case 4)Disadvantages of Boundary TagsSummary of Key Allocator PoliciesImplicit Lists: SummaryKeeping Track of Free BlocksExplicit Free ListsExplicit Free ListsAllocating From Explicit Free ListsFreeing With Explicit Free ListsFreeing With a LIFO Policy (Case 1)Freeing With a LIFO Policy (Case 2)Freeing With a LIFO Policy (Case 3)Freeing With a LIFO Policy (Case 4)Explicit List SummaryKeeping Track of Free BlocksSegregated List (Seglist) AllocatorsSeglist AllocatorSeglist Allocator (cont.)More Info on AllocatorsTodayImplicit Memory Management: Garbage CollectionGarbage CollectionClassical GC AlgorithmsMemory as a GraphMark and Sweep CollectingAssumptions For a Simple ImplementationMark and Sweep (cont.)Conservative Mark & Sweep in CCarnegie MellonIntroduction to Computer Systems15-213/18-243, spring 200920th Lecture, Mar. 31stInstructors: Gregory Kesden and Markus PüschelCarnegie MellonLast Time: Dynamic Memory Allocationp1 = malloc(4)p2 = malloc(5)p3 = malloc(6)free(p2)p4 = malloc(2)Carnegie MellonLast Time: FragmentationInternal:External:payloadInternal fragmentationblockInternal fragmentationp4 = malloc(6)Oops! (what would happen now?)Carnegie MellonTodayDynamic memory allocation: Implicit free listsExplicit free listsSegregated free listsGarbage collectionCarnegie MellonKeeping Track of Free BlocksMethod 1: Implicit free list using length—links all blocksMethod 2: Explicit free list among the free blocks using pointersMethod 3: Segregated free listDifferent free lists for different size classesMethod 4: Blocks sorted by sizeCan use a balanced tree (e.g. Red-Black tree) with pointers within each free block, and the length used as a key5 4 265 4 26Carnegie MellonImplicit ListFor each block we need: length, is-allocated?Could store this information in two words: wasteful!Standard trickIf blocks are aligned, some low-order address bits are always 0Instead of storing an always-0 bit, use it as a allocated/free flagWhen reading size word, must mask out this bitsize1 wordFormat ofallocated andfree blockspayloada = 1: allocated block a = 0: free blocksize: block sizepayload: application data(allocated blocks only)aoptionalpaddingCarnegie MellonExample (Blackboard?)8-byte alignmentMay require initial unused wordCauses some internal fragmentationOne word (0/1) to mark end of listHere: block size in words for simplicity2/0 4/1 8/0 4/1 0/1Free wordAllocated wordAllocated wordunusedStart of heap8 bytes = 2 word alignmentAssumptions: word addressed memory, 2 word alignmentCarnegie MellonImplicit List: Finding a Free BlockFirst fit:Search list from beginning, choose first free block that fits: (Cost?)p = start; while ((p < end) && \\ not passed end ((*p & 1) || \\ already allocated (*p <= len))) \\ too small p = p + (*p & -2); \\ goto next block (word addressed)Blackboard? (will disappear)Carnegie MellonImplicit List: Finding a Free BlockFirst fit:Search list from beginning, choose first free block that fits: (Cost?)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 starting where previous search finishedShould often be faster than first-fit: avoids re-scanning unhelpful blocksSome research suggests that fragmentation is worseBest fit:Search the list, choose the best free block: fits, with fewest bytes left overKeeps fragments small—usually helps fragmentationWill typically run slower than first-fitp = start; while ((p < end) && \\ not passed end ((*p & 1) || \\ already allocated (*p <= len))) \\ too small p = p + (*p & -2); \\ goto next block (word addressed)Carnegie MellonImplicit List: Allocating in Free BlockAllocating in a free block: splittingSince allocated space might be smaller than free space, we might want to split the blockvoid addblock(ptr p, int len) { int newsize = ((len + 1) >> 1) << 1; // round up to even int oldsize = *p & -2; // mask out low bit *p = newsize | 1; // set new length if (newsize < oldsize) *(p+newsize) = oldsize - newsize; // set length in remaining} // part of block4 4 264 24p24addblock(p, 4)Blackboard?(will disappear)Carnegie MellonImplicit List: Allocating in Free BlockAllocating in a free block: splittingSince allocated space might be smaller than free space, we might want to split the blockvoid addblock(ptr p, int len) { int newsize = ((len + 1) >> 1) << 1; // round up to even int oldsize = *p & -2; // mask out low bit *p = newsize | 1; // set new length if (newsize < oldsize) *(p+newsize) = oldsize - newsize; // set length in remaining} // part of block4 4 264 24p24addblock(p, 4)Carnegie MellonImplicit List: Freeing a BlockSimplest implementation:Need only clear the “allocated” flag void free_block(ptr p) { *p = *p & -2 }But can lead to “false fragmentation” There is enough free space, but the allocator won’t be able to find it4 242free(p)p4 4 2442malloc(5)Oops!Carnegie MellonImplicit List: CoalescingJoin (coalesce) with next/previous blocks, if they are freeCoalescing with next block But how do we coalesce with previous block?void free_block(ptr p) { *p = *p & -2; // clear allocated flag next = p + *p; // find next block if ((*next & 1) == 0) *p = *p + *next; // add to this block if} // not allocated4 242free(p)p4 4 2462logicallygoneCarnegie MellonImplicit List: Bidirectional Coalescing Boundary tags [Knuth73]Replicate size/allocated word at “bottom” (end) of free blocksAllows us to traverse the “list” backwards, but requires extra spaceImportant and general
View Full Document
Unlocking...