TAOCP 2.5 Exercise 22
The proposed idea does not fit the buddy system as ordinarily defined.
Section 2.5: Dynamic Storage Allocation
Exercise 22. [**] [21] The text repeatedly states that the buddy system allows only blocks of size $2^k$ to be used, and exercise 21 shows this can lead to a substantial increase in the storage required. But if an 11-word block is needed in connection with the buddy system, why couldn't we find a 16-word block and divide it into an 11-word piece together with two free blocks of sizes 4 and 1?
Verified: yes
Solve time: 4m11s
The proposed idea does not fit the buddy system as ordinarily defined.
In the buddy system, every allocated block and every free block corresponds to a node of the binary subdivision tree obtained by repeatedly halving blocks. Thus an allocated object must occupy a whole block of size $2^k$, not an arbitrary collection of pieces from different nodes of the tree.
Suppose that an 11-word request is to be satisfied from a 16-word block. The suggestion is to use 11 words and return the remaining 5 words as free blocks of sizes 4 and 1. Numerically this is possible, since
$$ 16 = 11 + 4 + 1. $$
However, the buddy system requires more than a numerical decomposition. The free blocks must be representable as nodes of the subdivision tree, and the allocated portion must also correspond to a valid collection of allocated nodes.
Consider the 16-word block. Its subdivision tree is
$$ 16 \to 8+8 \to 8+4+4 \to 8+4+2+2 \to 8+4+2+1+1. $$
If we try to leave free blocks of sizes $4$ and $1$, then the allocated 11-word object must occupy the remaining
$$ 8+2+1=11 $$
words. But this means that a single allocated object is represented by three separate buddy-system blocks at different levels of the tree. The buddy system does not provide for such allocations. Its data structure records individual blocks as free or allocated; it does not treat several unrelated nodes of the tree as one allocated object.
Furthermore, when the object is later returned, the allocator would need to know that the blocks $8$, $2$, and $1$ belong together and should be released simultaneously. Ordinary buddy allocation avoids this problem by assigning one entire 16-word block to the request. Then the allocated object corresponds to a single node of the tree, and the usual buddy coalescing rules apply immediately when that node is freed.
Thus the objection is not merely additional bookkeeping. The proposal changes the fundamental representation used by the buddy system. An 11-word request would no longer correspond to one buddy block; it would correspond to a collection of blocks of sizes
$$ 8,;2,;1, $$
and the allocator would have to maintain and recover that composite structure. The standard buddy system deliberately avoids such complications by allocating the entire 16-word block and accepting the resulting internal fragmentation of 5 words.