TAOCP 2.5 Exercise 41

Section 2.5: Dynamic Storage Allocation

Exercise 41. [**] [M27] The purpose of this exercise is to consider the worst-case memory usage of the buddy system. A particularly bad case occurs, for example, if we start with an empty memory and proceed as follows: First reserve $n=2^{r+1}$ blocks of length 1, which go into locations 0 through $n-1$; then for $k=1,2,\ldots,r$, liberate all blocks whose starting location is not divisible by $2^k$, and reserve $2^{-k-1}n$ blocks of length $2^k$, which go into locations ${1\over2}(1+k)n$ through ${1\over2}(2+k)n-1$. This procedure uses $1+{1\over2}r$ times as much memory as is ever occupied.

Prove that the worst case cannot be substantially worse than this: When all requests are for block sizes $1,2,\ldots,2^r$, and if the total space requested at any time never exceeds $n$, where $n$ is a multiple of $2^r$, the buddy system will never overflow a memory area of size $(r+1)n$.

Verified: yes
Solve time: 1m49s

Let $R\le n$ be the total space currently reserved. In the buddy system, every free block belongs to exactly one free list of size $2^k$, $0\le k<r$. A free block of size $2^k$ cannot have a free buddy of the same size, otherwise the two blocks would have been merged. Hence its buddy contains at least one reserved unit somewhere in its descendant tree.

Charge each free block of size $2^k$ to the reserved units contained in its buddy subtree. The charge is distributed uniformly over those reserved units, whose total size is at most $2^k$. Therefore each reserved unit receives charge at most $1$ from this free block. For a fixed reserved unit, there is at most one free buddy block at each level $k$, namely the buddy of the ancestor block containing that unit. Since the permitted block sizes are $1,2,\ldots,2^r$, there are at most $r$ such levels. Consequently every reserved unit receives total charge at most $r$.

Summing over all reserved units, the total size of all free blocks is at most $rR$. Therefore the amount of memory managed by the buddy system satisfies

$$ \text{memory used} = R+\text{(free space)} \le R+rR =(r+1)R \le (r+1)n. $$

Hence a memory area of size $(r+1)n$ can never overflow. Since the construction in the statement attains a ratio $1+\frac r2$, the worst case is within a factor smaller than $2$ of this bound. Thus the buddy system cannot be substantially worse than the example given. ∎