Dynamic Memory Allocation IIKeeping Track of Free BlocksExplicit Free ListsAllocating From Explicit Free ListsFreeing With Explicit Free ListsFreeing With a LIFO PolicyFreeing With a LIFO Policy (cont)Summary of Explicit ListsSlide 9Segregated StorageSimple Segregated StorageSegregated FitsBuddy AllocatorsFor More Info on AllocatorsImplicit Memory Management: Garbage CollectionGarbage CollectionClassical GC algorithmsMemory as a GraphAssumptions For This LectureMark-and-Sweep CollectingMark-and-Sweep (cont.)Conservative Mark-and-Sweep in CMemory-Related BugsDereferencing Bad PointersReading Uninitialized MemoryOverwriting MemorySlide 27Slide 28Slide 30Referencing Nonexistent VariablesFreeing Blocks Multiple TimesReferencing Freed BlocksFailing to Free Blocks (Memory Leaks)Slide 35Dealing With Memory BugsDealing With Memory Bugs (cont.)Dynamic Memory Allocation IIDynamic Memory Allocation IITopicsTopicsExplicit doubly-linked free listsSegregated free listsGarbage collectionMemory-related perils and pitfallsCS 105Tour of the Black Holes of Computing– 2 –CS 105Keeping Track of Free BlocksKeeping Track of Free BlocksMethod 1Method 1: : Implicit listImplicit list using lengths -- links all blocks using lengths -- links all blocksMethod 2Method 2: : Explicit listExplicit list among the free blocks using among the free blocks using pointers within the free blockspointers within the free blocksMethod 3Method 3: : Segregated free listSegregated free listDifferent free lists for different size classesMethod 4Method 4: : Blocks sorted by size (not discussed)Blocks sorted by size (not discussed)For example balanced tree (Red-Black?) with pointers inside each free block, block length used as key20 16 82420 16 824– 3 –CS 105Explicit Free ListsExplicit Free ListsUse data space for link pointersUse data space for link pointersTypically doubly linkedStill need boundary tags for coalescingLinks aren’t necessarily in same order as blocks!A B C16 16 16 16 2424 1616 16 16Forward linksBack linksABC– 4 –CS 105Allocating From Explicit Free ListsAllocating From Explicit Free Listsfree blockpred succfree blockpred succBefore:After:(with splitting)– 5 –CS 105Freeing With Explicit Free ListsFreeing With Explicit Free ListsInsertion policyInsertion policy: Where in free list to put newly freed : Where in free list to put newly freed block?block?LIFO (last-in-first-out) policyInsert freed block at beginning of free listPro: simple, and constant-timeCon: studies suggest fragmentation is worse than address-orderedAddress-ordered policyInsert freed blocks so list is always in address order»i.e. addr(pred) < addr(curr) < addr(succ) Con: requires search (using boundary tags) Pro: studies suggest fragmentation is better than LIFO– 6 –CS 105Freeing With a LIFO PolicyFreeing With a LIFO PolicyCase 1: a-a-aCase 1: a-a-aInsert self at beginning of free listCase 2: a-a-fCase 2: a-a-fRemove next from free list, coalesce self and next, and add to beginning of free listpred (p) succ (s)selfa ap sselfa fbefore:p sfaafter:– 7 –CS 105Freeing With a LIFO Policy (cont)Freeing With a LIFO Policy (cont)Case 3: f-a-aCase 3: f-a-aRemove prev from free list, coalesce with self, and add to beginning of free listCase 4: f-a-fCase 4: f-a-fRemove prev and next from free list, coalesce with self, and add to beginning of listp sselff abefore:p sf aafter:p1 s1selff fbefore:fafter:p2 s2p1 s1 p2 s2– 8 –CS 105Summary of Explicit ListsSummary of Explicit ListsComparison to implicit lists:Comparison to implicit lists:Allocate is linear-time in number of free blocks instead of total blocks—much faster when most of memory full Slightly more complicated allocate and free since needs to splice blocks in and out of free listSome extra space for links (2 extra words per block)Main use of linked lists is in conjunction with segregated Main use of linked lists is in conjunction with segregated free listsfree listsKeep multiple linked lists of different size classes, or possibly for different types of objects– 9 –CS 105Keeping Track of Free BlocksKeeping Track of Free BlocksMethod 1Method 1: : Implicit listImplicit list using lengths -- links all blocks using lengths -- links all blocksMethod 2Method 2: : Explicit listExplicit list among the free blocks using among the free blocks using pointers within the free blockspointers within the free blocksMethod 3Method 3: : Segregated free listSegregated free listDifferent free lists for different size classesMethod 4Method 4: : Blocks sorted by size (not discussed)Blocks sorted by size (not discussed)For example balanced tree (Red-Black?) with pointers inside each free block, block length used as key20 16 82420 16 824– 10 –CS 105Segregated StorageSegregated StorageEach Each size classsize class has its own collection of blocks has its own collection of blocks4-8121620-3236-64Often separate size class for every small size (8, 12, 16, …)For larger, typically have size class for each power of 2– 11 –CS 105Simple Segregated StorageSimple Segregated StorageSeparate heap and free list for each size classSeparate heap and free list for each size classNo splittingNo splittingTo allocate block of size n:To allocate block of size n:If free list for size n is not empty,Allocate first block on list (can be implicit or explicit)If free list is empty, Get new page Create new free list from all blocks in pageAllocate first block on listConstant timeTo free block:To free block:Add to free listIf page empty, return it for use by another size (optional)Tradeoffs:Tradeoffs:Fast, but can fragment badly– 12 –CS 105Segregated FitsSegregated FitsArray of free lists, one for each size classArray of free lists, one for each size classTo allocate block of size n:To allocate block of size n:Search appropriate list for block of size m > nIf block found, split and put fragment on smaller list (optional)If no block found, try next larger class and repeatIf largest class empty, allocate page(s) big enough to hold desired block, put remainder on appropriate listTo free a block:To free a block:Coalesce and put on appropriate listTradeoffsTradeoffsFaster search than sequential fits (log time for power-of-two size classes)Controls fragmentation of simple segregated storageCoalescing can increase search timesDeferred coalescing can help– 13 –CS
View Full Document
Unlocking...