CS 208 s21 — Dynamic Memory Allocation: Free Lists

Table of Contents

1 Video

Here is a video lecture for the material outlined below. It covers CSPP section 9.9.6 through 9.9.14 (p. 847–865). It contains sections on

  1. introduction (0:01)
  2. implicit free list concept (2:07)
  3. minimum block size (11:50)
  4. epilogue block (13:18)
  5. basic spreadsheet example (14:27)
  6. placement policy (18:37)
  7. splitting (23:20)
  8. false fragmentation (25:08)
  9. coalescing (26:43)
  10. boundary tags (31:05)
  11. coalescing: four cases (32:51)
  12. when the heap runs out of space (37:35)
  13. explicit free list (39:34)

The Panopto viewer has table of contents entries for these sections. Link to the Panopto viewer: https://carleton.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=4597ad39-7990-43f1-a0bc-ac59010dee45

2 Introduction

Implementation questions:

  • freeing: how much do we free given just a pointer?
  • free block organization: how to keep track of them
  • placement: which free block should we choose to fulfill a request
  • splitting: what do we do with the remainder of a free block after part of it is allocated
  • coalescing: what do we do when a block is freed

3 Implicit Free List

implicitblock.png

implicit-free-list.png

  • since block size will always be a multiple of 16 due to alignment, the four lower order bits of the size will always be 0
  • we can make efficient use of the header by using these four bits to indicate if the block is allocated or free
  • the block size includes the payload and any padding, and is thus an implicit pointer to the start of the next block
  • we will need some special block to mark the end of the free list (e.g, allocated bit, size 0)
  • implicit free list is simple, but operations are linear in the number of blocks since we have to traverse the list
  • alignment combined with block format impose a minimum block size
  • https://docs.google.com/spreadsheets/d/1Tj8LTKBBqLodX5K8GbqCVUSWOFur6KzXZshQhx0bF4E/edit?usp=sharing

3.1 Placing Allocated Blocks

  • an allocator's placement policy determines the choice of free block to fulfill allocation
    • first fit: take the first free block that's big enough
      • end up with lots of small "splinters" near the start of the list, large blocks near the end
    • next fit: like first fit, but start search where the previous one left off
      • unclear if this is better than first fit in practice
    • best fit: choose the smallest free block that fits
      • better memory utilization, but requires exhaustive search
  • if the fit is not good, an allocator might opt to split the free block into two parts
  • if necessary, an allocate will ask the kernel for additional heap memory, inserting a new free block into the list

3.2 Coalescing Free Blocks

  • adjacent free blocks cause false fragmentation—free memory chopped up into many small unusable free blocks
  • to address this an allocator must merge (coalesce) adjacent free blocks
    • immediate coalescing: merge blocks whenever one is freed
      • simple, constant time
      • can lead to a form of thrashing where a block is coaslesced and split repeatedly
    • deferred coalescing: wait and coaslesce at a later time (e.g., scan the hope when a request fails)
      • often the more efficient choice

3.2.1 Boundary Tags

  • with a simple header containing the block size, we can reach the next block, but what about the previous block?
    • we'd have to traverse the free list until we reached the current block
  • instead, add a footer to each block that's the same as the header
    • together, the header and footer form boundary tags
    • if we go back one word from the header, we get to the footer of the previous block

boundary-tags.png

  • four cases for coalescing:
    1. previous and next blocks are both allocated
    2. previous block is allocated, next block is free
    3. previous block is free, next block is allocated
    4. previous and next blocks are both free
  • https://docs.google.com/spreadsheets/d/1Tj8LTKBBqLodX5K8GbqCVUSWOFur6KzXZshQhx0bF4E/edit?usp=sharing
  • boundary tags can introduce significant memory overhead in the case of many small blocks
    • fortunately, we only need to have footers in free blocks, since we only care about the size of the previous block when it is free and we want to merge it
    • we still need a way to tell if the previous block is allocated, so we'll add that information to one of the unused low-order bits of the header

4 Explicit Free Lists

explicit-block.png

explicit-free-list.png

  • organize free list as a doubly-linked list using the payload of free blocks (by definition unused) to store the pointers
    • now placement is linear in the number of free blocks instead of the total number of blocks
    • assuming a first-fit policy:
      • if list uses last-in first-out by inserting new free blocks at the head, freeing a block is constant time
      • better memory utilization can be achieved if free blocks are maintained in address order
  • minimum block size must increase to accomodate list pointers, potentially increasing internal fragmentation
  • splitting, boundary tags, coalescing are general to all allocators
    • free blocks still coalesce with those adjacent in memory
      • remove from list, reinsert at the head
    • list can hold blocks in any order, regardless of memory address