DOC PREVIEW
Princeton COS 217 - Dynamic Memory Management

This preview shows page 1-2-20-21 out of 21 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

Princeton COS 217 - Dynamic Memory Management

Documents in this Course
Summary

Summary

4 pages

Lecture

Lecture

4 pages

Generics

Generics

14 pages

Generics

Generics

16 pages

Lecture

Lecture

20 pages

Debugging

Debugging

35 pages

Types

Types

7 pages

Lecture

Lecture

21 pages

Assembler

Assembler

16 pages

Lecture

Lecture

20 pages

Lecture

Lecture

39 pages

Testing

Testing

44 pages

Pipeline

Pipeline

19 pages

Lecture

Lecture

6 pages

Signals

Signals

67 pages

Building

Building

17 pages

Lecture

Lecture

7 pages

Modules

Modules

12 pages

Generics

Generics

16 pages

Testing

Testing

22 pages

Signals

Signals

34 pages

Lecture

Lecture

19 pages

Load more
Download Dynamic Memory Management
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Dynamic Memory Management and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Dynamic Memory Management 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?