6 / 11 Allocators

Buddy Still In Use

A binary buddy allocator manages one 64 KB region. Three operations run in order:

  1. p = alloc(7 KB): the allocator splits 64 to 32, 32 to 16, 16 to 8, and hands back the leftmost 8 KB block.
  2. q = alloc(6 KB)
  3. free(p)

What does the free list hold after step 3?

A

One 8 KB block, one 16 KB block, one 32 KB block, and the 1 KB of internal fragmentation returned as a separate free chunk.

B

One 8 KB block, one 16 KB block, and one 32 KB block. No coalescing happens, because p's buddy is the block still held by q.

C

The freed 8 KB merges with the neighbouring free 16 KB block into a single 24 KB block.

D

The freed 8 KB coalesces all the way back to a single 64 KB block, since coalescing walks up the tree until it reaches the root.