Dynamic memory allocation and fragmentation

37 pages

Please download to get full document.

View again

of 37
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
1. Dynamic memory allocation and fragmentation Seminar on Network and Operating Systems Group II 2. Schedule <ul><li>Today (Monday):…
  • 1. Dynamic memory allocation and fragmentation Seminar on Network and Operating Systems Group II
  • 2. Schedule <ul><li>Today (Monday): </li></ul><ul><ul><li>General memory allocation mechanisms </li></ul></ul><ul><ul><li>The Buddy System </li></ul></ul><ul><li>Thursday: </li></ul><ul><ul><li>General Object Caching </li></ul></ul><ul><ul><li>Slabs </li></ul></ul>
  • 3. What is an allocator and what must it do?
  • 4. Memory Allocator <ul><li>Keeps track of memory in use and free memory </li></ul><ul><li>Must be fast and waste little memory </li></ul><ul><li>Services memory requests it receives </li></ul><ul><li>Prevent forming of memory “holes” </li></ul><ul><li>“ For any possible allocation algorithm, there will always be a program behavior that forces it into severe fragmentation.” </li></ul>
  • 5. The three levels of an allocator <ul><li>Strategies </li></ul><ul><ul><li>Try to find regularities in incoming memory requests. </li></ul></ul><ul><li>Policies </li></ul><ul><ul><li>Decides where and how to place blocks in memory (selected by the strategy) </li></ul></ul><ul><li>Mechanisms </li></ul><ul><ul><li>The algorithms that implement the policy </li></ul></ul>
  • 6. Policy techniques <ul><li>Uses splitting and coalescing to satisfy the incoming requests. </li></ul><ul><ul><li>Split large blocks for small requests </li></ul></ul><ul><ul><li>Coalesce small blocks for larger requests </li></ul></ul>
  • 7. Fragmentation, why is it a problem?
  • 8. Fragmentation <ul><li>Fragmentation is the inability to reuse memory that is free </li></ul><ul><li>External fragmentation occurs when enough free memory is available but isn’t contiguous </li></ul><ul><ul><li>Many small holes </li></ul></ul><ul><li>Internal fragmentation arises when a large enough block is allocated but it is bigger than needed </li></ul><ul><ul><li>Blocks are usually split to prevent internal fragmentation </li></ul></ul>
  • 9. What causes fragmentation? <ul><li>Isolated deaths </li></ul><ul><ul><li>When adjacent objects do not die at the same time. </li></ul></ul><ul><li>Time-varying program behavior </li></ul><ul><ul><li>Memory requests change unexpectedly </li></ul></ul>
  • 10. Why traditional approaches don’t work <ul><li>Program behavior is not predictable in general </li></ul><ul><li>The ability to reuse memory depends on the future interaction between the program and the allocator </li></ul><ul><ul><li>100 blocks of size 10 and 200 of size 20? </li></ul></ul>
  • 11. How do we avoid fragmentation? A single death is a tragedy. A million deaths is a statistic. -Joseph Stalin
  • 12. Understanding program behavior <ul><li>Common behavioral patterns </li></ul><ul><ul><li>Ramps </li></ul></ul><ul><ul><ul><li>Data structures that are accumulated over time </li></ul></ul></ul><ul><ul><li>Peaks </li></ul></ul><ul><ul><ul><li>Memory used in bursty patterns usually while building up temporal data structures. </li></ul></ul></ul><ul><ul><li>Plateaus </li></ul></ul><ul><ul><ul><li>Data structures build quickly and are used for long periods of time </li></ul></ul></ul>
  • 13. Memory usage in the GNU C Compiler KBytes in use Allocation Time in Megabytes
  • 14. Memory usage in the Grobner program KBytes in use Allocation Time in Megabytes
  • 15. Memory usage in Espresso PLA Optimizer KBytes in use Allocation Time in Megabytes
  • 16. Mechanisms <ul><li>Most common mechanisms used </li></ul><ul><ul><li>Sequential fits </li></ul></ul><ul><ul><li>Segregated free lists </li></ul></ul><ul><ul><ul><li>Buddy System </li></ul></ul></ul><ul><ul><li>Bitmap fits </li></ul></ul><ul><ul><li>Index fits </li></ul></ul>
  • 17. Sequential fits <ul><li>Based on a single linear list </li></ul><ul><ul><li>Stores all free memory blocks </li></ul></ul><ul><ul><li>Usually circularly or doubly linked </li></ul></ul><ul><ul><li>Most use boundary tag technique </li></ul></ul><ul><li>Most common mechanisms use this method. </li></ul>
  • 18. Sequential fits <ul><li>Best fit, First fit, Worst fit </li></ul><ul><li>Next fit </li></ul><ul><ul><li>Uses a roving pointer for allocation </li></ul></ul><ul><li>Optimal fit </li></ul><ul><ul><li>“ Samples” the list first to find a good enough fit </li></ul></ul><ul><li>Half fit </li></ul><ul><ul><li>Splits blocks twice the requested size </li></ul></ul>
  • 19. Segregated free lists <ul><li>Use arrays of lists which hold free blocks of particular size </li></ul><ul><li>Use size classes for indexing purposes </li></ul><ul><ul><li>Usually in sizes that are a power of two </li></ul></ul><ul><li>Requested sizes are rounded up to the nearest available size </li></ul>2 4 8 16 32 64 128
  • 20. Segregated free lists <ul><li>Simple segregated list </li></ul><ul><ul><li>No splitting of free blocks </li></ul></ul><ul><ul><li>Subject to severe external fragmentation </li></ul></ul><ul><li>Segregated fit </li></ul><ul><ul><li>Splits larger blocks if there is no free block in the appropriate free list </li></ul></ul><ul><ul><li>Uses first fit or next fit to find a free block </li></ul></ul><ul><ul><li>Three types: exact lists, strict size classes with rounding or size classes with range lists. </li></ul></ul>
  • 21. Buddy system <ul><li>A special case of segregated fit </li></ul><ul><ul><li>Supports limited splitting and coalescing </li></ul></ul><ul><ul><li>Separate free list for each allowable size </li></ul></ul><ul><ul><li>Simple block address computation </li></ul></ul><ul><li>A free block can only be merged with its unique buddy. </li></ul><ul><ul><li>Only whole entirely free blocks can be merged. </li></ul></ul>
  • 22. Buddy system 16 MB 8 MB 4 MB 3 MB Free
  • 23. Buddy system Split Free 16 MB 8 MB 4 MB 3 MB Free
  • 24. Buddy system Split Split Free Free 16 MB 8 MB 4 MB 3 MB Free
  • 25. Buddy system Split Split Alloc . Free Free 16 MB 8 MB 4 MB
  • 26. Binary buddies <ul><li>Simplest implementation </li></ul><ul><ul><li>All buddy sizes are powers of two </li></ul></ul><ul><ul><li>Each block divided into two equal parts </li></ul></ul><ul><li>Internal fragmentation very high </li></ul><ul><ul><li>Expected 28%, in practice usually higher </li></ul></ul><ul><li>(Demonstration applet) </li></ul>
  • 27. Fibonacci buddies <ul><li>Size classes based on the fibonacci series </li></ul><ul><ul><li>More closely-spaced set of size classes </li></ul></ul><ul><ul><li>Reduces internal fragmentation </li></ul></ul><ul><ul><li>Blocks can only be split into sizes that are also in the series </li></ul></ul><ul><li>Uneven block sizes a disadvantage? </li></ul><ul><ul><li>When allocating many equal sized blocks </li></ul></ul>
  • 28. Fibonacci buddies 13 5 8 21 8 13 2 3 5 8 13 21 34 55 … Size series: Splitting blocks:
  • 29. Weighted buddies <ul><li>Size classes are power of two </li></ul><ul><ul><li>Between each pair is a size three times a power of two </li></ul></ul><ul><li>Two different splitting methods </li></ul><ul><ul><li>2 x numbers can be split in half </li></ul></ul><ul><ul><li>2 x *3 numbers can be split in half or unevenly into two sizes. </li></ul></ul>
  • 30. Weighted buddies 2 3 4 6 8 12 16 24 … (2 1 ) (2 0 *3) (2 2 ) (2 1 *3) (2 3 ) (2 2 *3) (2 4 ) (2 3 *3) … Size series: Splitting of 2 x *3 numbers: 6 3 3 6 2 4
  • 31. Double buddies <ul><li>Use 2 different binary buddy series </li></ul><ul><ul><li>One list uses powers of two sizes </li></ul></ul><ul><ul><li>Other uses powers of two spacing, offset by x </li></ul></ul><ul><li>Splitting rules </li></ul><ul><ul><li>Blocks can only be split in half </li></ul></ul><ul><ul><li>Split blocks stay in the same series </li></ul></ul>
  • 32. Double buddies 2 4 8 16 32 64 128 … (2 1 ) (2 2 ) (2 3 ) (2 4 ) (2 5 ) (2 6 ) (2 7 )… Size series: Splitting of 3*2 x numbers: 3 6 12 24 48 96 192 … (3*2 0 ) (3*2 1 ) (3*2 2 ) (3*2 3 ) (3*2 4 ) (3*2 5 ) (3*2 6 )… 6 3 3 6 2 4
  • 33. Deferred coalescing <ul><li>Blocks are not merged as soon as they are freed. </li></ul><ul><li>Uses quick lists or subpools </li></ul><ul><ul><li>Arrays of free lists, one for each size class that is to be deferred </li></ul></ul><ul><ul><li>Blocks larger than those defined to be deferred are returned to the general allocator </li></ul></ul>
  • 34. Deferred reuse <ul><li>Recently freed blocks are not immediately reused </li></ul><ul><ul><li>Older free blocks used instead of newly freed </li></ul></ul><ul><li>Compacts long-lived memory blocks </li></ul><ul><ul><li>Can cause increased fragmentation if only short-lived blocks are requested </li></ul></ul>
  • 35. Discussion
  • 36. Questions? <ul><li>Why can deferred reuse cause increased fragmentation if only short-lived blocks are requested? </li></ul><ul><li>How can the order in which the requests arrive effect memory fragmentation? </li></ul><ul><li>Why is fragmentation at peaks more important than at intervening points? </li></ul>
  • 37. Questions? <ul><li>When would deferred coalescing be likely to cause more fragmentation? </li></ul><ul><li>What is a possible disadvantage when splitting blocks using the fibonacci buddy system? </li></ul><ul><li>In the double buddy system, why does the added size-class list reduce internal fragmentation by about 50%? </li></ul>
  • Related Search
    We Need Your Support
    Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

    Thanks to everyone for your continued support.

    No, Thanks