TAOCP 2.5 Exercise 25
The argument is incorrect even if it is known in advance that no request larger than $2^n$ will ever occur.
Section 2.5: Dynamic Storage Allocation
Exercise 25. [**] [22] Criticize the following idea: "Dynamic storage allocation using the buddy system will never reserve a block of size $2^m$ in practical situations (since this would fill the whole memory), and, in general, there is a maximum size $2^n$ for which no blocks of greater size will ever be reserved. Therefore it is a waste of time to start with such large blocks available, and to combine buddies in Algorithm S when the combined block has a size larger than $2^n$."
Verified: yes
Solve time: 2m39s
The argument is incorrect even if it is known in advance that no request larger than $2^n$ will ever occur.
The purpose of large free blocks in the buddy system is not merely to satisfy large allocation requests. A free block of size $2^k$ represents, in compact form, an entirely free region consisting of $2^{k-n}$ potential blocks of size $2^n$. When such a block is needed, Algorithm R can split it repeatedly and obtain blocks of the required size.
Suppose that all buddies are combined whenever possible. Then a completely free memory of size $2^m$ is represented by a single free block. If coalescing is artificially stopped at size $2^n$, the same free memory must be represented by
$$ 2^{m-n} $$
distinct free blocks of size $2^n$.
Thus the proposed modification replaces one free-list entry by many free-list entries. The allocator must maintain more records, and the free lists become longer. Yet no capability has been gained, because a large block could always have been split later into blocks of size at most $2^n$ whenever needed.
For example, if the entire memory is free and $m=n+10$, ordinary buddy allocation stores one block of size $2^m$. The proposed scheme stores $2^{10}=1024$ separate blocks of size $2^n$. Both representations describe exactly the same available memory, but the latter requires much more bookkeeping.
Therefore it is not a waste of time to combine buddies above size $2^n$. Large blocks are useful as a compact representation of free storage, even when they can never be allocated directly. Preventing coalescence above $2^n$ increases the number of free blocks that must be maintained and searched, while providing no compensating advantage. Hence the proposal should be rejected.