1 1 Optimizing Dynamic Memory Management!2 Goals of this Lecture!• Help you learn about:"• Details of K&R heap mgr"• Heap mgr optimizations related to Assignment #6"• Faster free() via doubly-linked list, redundant sizes, and status bits"• Faster malloc() via binning"• Other heap mgr optimizations"• Best/good fit block selection"• Selective splitting"• Deferred coalescing"• Segregated data"• Segregated meta-data"• Memory mapping"2 3 Part 1:"Details of the K&R Heap Manager"4 An Implementation Challenge!Problem:"• Need information about each free block"• Starting address of the block of memory"• Size of the free block"• Pointer to the next block in the free list"• Where should this information be stored?"• Number of free blocks is not known in advance"• So, need to store the information on the heap!• But, wait, this code is what implements the management of the heap (malloc and free)"• Canʼt call malloc() to allocate storage for these data"• Canʼt call free() to deallocate the storage either"3 5 Store Information in the Free Block!Solution:"• Store the information directly in the block"• Since the memory isnʼt being used for anything anyway"• And allows data structure to grow and shrink as needed"6 Block Headers!• Every free block has a header, containing:"• Pointer to (i.e., address of) the next free block"• Size of the free block"size user data p (address returned to the user) header4 7 Free List: Circular Linked List!• Free blocks, linked together"• Example: circular linked list"• Keep list in order of increasing addresses"• Makes it easier to coalesce adjacent free blocks"In use In use In use Free list 8 Malloc: First-Fit Algorithm!• Start at the beginning of the list"• Sequence through the list"• Keep a pointer to the previous element"• Stop when reaching first block that is big enough"• Patch up the list"• Return a pointer to the user"p p prev p prev5 9 Malloc: First Case: Perfect Fit!• Suppose the first fit is a perfect fit"• Remove the block from the list"• Link the previous free block with the next free block"• Return the current to the user (skipping header)"p prev p+1 10 Malloc: Second Case: Big Block!• Suppose the block is bigger than requested"• Divide the free block into two blocks"• Keep first (now smaller) block in the free list"• Allocate the second block to the user"• Bonus: No need to manipulate links"p p6 11 Free!• User passes a pointer to the memory block "• void free(void *ap); • free() function inserts block into the list"• Identify the start of entry "• Find the location in the free list"• Add to the list, coalescing entries, if needed"ap bp 12 Free: Finding Location to Insert!• Start at the beginning!• Sequence through the list!• Stop at last entry before the to-be-freed element"In use FREE ME In use Free list bp p7 13 Free: Handling Corner Cases!• Check for wrap-around in memory"• To-be-freed block is before first entry in the free list, or"• To-be-freed block is after the last entry in the free list"In use FREE ME In use Free list bp p 14 Free: Inserting Into Free List!• New element to add to free list • Insert in between previous and next entries • But, there may be opportunities to coalesce"bp p p->s.ptr8 15 Coalescing With Neighbors!• Scanning the list finds the location for inserting"• Pointer to to-be-freed element: bp • Pointer to previous element in free list: p • Coalescing into larger free blocks"• Check if contiguous to upper and lower neighbors"In use FREE ME In use Free list bp p lower upper 16 Coalesce With Upper Neighbor!• Check if next part of memory is in the free list"• If so, make into one bigger block • Else, simply point to the next free element bp upper p p->s.ptr p p->s.ptr9 17 Coalesce With Lower Neighbor!• Check if previous part of memory is in the free list"• If so, make into one bigger block bp p lower p->s.ptr p p->s.ptr 18 Strengths of K&R Approach!• Advantages"• Simplicity of the code"• Optimizations to malloc() • Splitting large free block to avoid wasting space"• Optimization to free() • Roving free-list pointer is left at the last place a block was allocated"• Coalescing contiguous free blocks to reduce fragmentation"p bp upper p p->s.ptr10 19 Weaknesses of K&R Approach!• Inefficient use of memory: fragmentation"• First-fit policy can leave lots of “holes” of free blocks in memory"• Long execution times: linear-time overhead"• malloc() scans the free list to find a big-enough block"• free() scans the free list to find where to insert a block"• Accessing a wide range of memory addresses in free list"• Can lead to large amount of paging to/from the disk"In use In use In use Free list 20 8 50 20 Part 2:"Optimizations Related to Assignment 6"11 21 Faster Free!• Performance problems with K&R free() • Scanning the free list to know where to insert"• Keeping track of the “previous” node to do the insertion"• Doubly-linked, non-circular list "• Header"• Size of the block (in # of units)"• Flag indicating whether the block is free or in use"• If free, a pointer to the next free block"• Footer"• Size of the block (in # of units)"• If free, a pointer to the previous free block"h e a d f o o t 22 Size: Finding Next Block!• Go quickly to next block in memory"• Start with the userʼs data portion of the block"• Go backwards to the head of the block"• Easy, since you know the size of the header"• Go forward to the head of the next block"• Easy, since you know the size of the current block"12 23 Size: Finding Previous Block!• Go quickly to previous chunk in memory"• Start with the userʼs data portion of the block"• Go backwards to the head of the block"• Easy, since you know the size of the header"• Go backwards to the footer of the previous block"• Easy, since you know the size of the footer"• Go backwards to the header of the previous block"• Easy, since you know the size from the footer"24 Pointers: Next Free Block!• Go quickly to next free block in
View Full Document