1 / 11 Allocators

Seven Kilobyte Request

A binary buddy allocator manages one free 64 KB region. A program calls malloc(7 * 1024).

64 KB
32 KB | 32 KB
16 KB | 16 KB | 32 KB
 8 KB |  8 KB | 16 KB | 32 KB

How many splits does the search perform, and how much of the returned block does the caller not get to use?

A

13 splits, and 1 KB is wasted: the allocator splits down to its 512-byte minimum block before rounding back up.

B

3 splits, and 1 KB of the 8 KB block is unusable internal fragmentation.

C

3 splits, and nothing is wasted: the allocator hands back exactly the 7 KB requested and keeps the tail on a free list.

D

1 split, and 25 KB is wasted: the search stops at the first 32 KB half that is large enough.