Operating Systems: Three Easy Pieces Ch. 17

Free-Space Management

When free-space management becomes more difficult is when the free space with user-level memory-allocation memory

• Segmentation
• External Fragmentation
• Internal fragmentation
  • if an allocator hands out chunks of memory bigger than that requested, any unasked for (and thus unused) space in such a chunk
• void pointer
• Low-level Mechanisms
  • Splitting and Coalescing
    • requesting more than space that is free will fail → splitting
    • will find a free chunk of memory that can satisfy request
    • What if returned space is in the middle of heap?
    • It may end up with divided arrays with continuous size
  • Tracking the size of allocated regions
    • header block
    • Embedding Free list
    • mmap
    • Fragmented free spaces
      • go through the list and merge neighboring chunks
    • Heap can grow heap
      • OS finds free physical pages, maps them into the address space of the requesting process, then returns the value of the end of the new heap
• Strategies
  • Best fit → search through the free list and find chunks of free memory that bigger than the request size then return one that is the smallest in that group of candidate
  • Worst fit → case find the largest chunk and return the requested amount
  • First fit → finds the first block that is big enough and returns the requested amount to the user
    • May pollute the beginning of the free list with a small objects
    • address-based ordering → keeping the list ordered by the address of free space
  • Net fit → keeps an extra pointer to the location within the list where one was looking last
    • Spread the search for free space throughout the list more uniformly, thus avoiding splintering of the beginning of the list
• Segregated List
  • Slab allocator
    • The basic idea is simple: if a particular application has one (or a few) popular-sized requests that it makes, keep a separate list just to manage objects of that size
  • Slab allocator
    • Specifically, when the kernel boots up, it allocates a number of object caches for kernel objects that are likely to be requested frequently
• Buddy allocation
  • big space of size 2^N
  • search for free space recursively divides free space by two until a block that is big enough to accommodate the request is found
  • may suffer internal fragmentation
  • When returning the 8KB block to the free list, the allocator checks whether the “buddy” 8KB is free; if so, it coalesces the two blocks into a 16KB block.
• One major problem with many of the approaches described above is their lack of scaling.