TAOCP 2.5 Exercise 24
No.
Section 2.5: Dynamic Storage Allocation
Exercise 24. [**] [20] According to the algorithm in the text, the largest block (of size $2^m$) has no buddy, since it represents all of storage. Would it be correct to define $buddy_m(0)=0$ (namely, to make this block its own buddy), and then to avoid testing $k=m$ in step S1?
Verified: yes
Solve time: 1m12s
No. The test for $k=m$ in step S1 is necessary.
In the buddy system, when a block of size $2^k$ is returned, step S1 examines its buddy. If the buddy is free, the two blocks are merged into a block of size $2^{k+1}$ and the process continues. When $k=m$, the block under consideration already represents all of storage. There is no larger block into which it can be merged.
If we define $buddy_m(0)=0$, then the unique block of size $2^m$ would always be considered to have a free buddy whenever it is free itself. Step S1 would therefore attempt to merge the block with itself, producing a nonexistent block of size $2^{m+1}$. Repeating the algorithm would lead to further meaningless mergers. The largest block is not one member of a buddy pair; it is the result obtained when all possible buddy combinations have already been performed.
Therefore the definition $buddy_m(0)=0$ is incompatible with the logic of step S1. The special test for $k=m$ cannot be eliminated in this way. $\boxed{\text{The proposed modification is not correct.}}$