TAOCP 2.5 Exercise 29

Exercise 29. [**] [20] Could the buddy system do without the tag bit in each reserved block?

Verified: no
Solve time: 2m10s

No. When a block of size $2^k$ is returned to the free-storage system, Algorithm R computes the address of its buddy and must determine whether that buddy is currently free. If the buddy is free, the two blocks are merged into a block of size $2^{k+1}$; otherwise the returned block is simply inserted into the free list for size $2^k$.

Without a tag bit in each reserved block, the allocator cannot determine from the buddy's address alone whether the buddy is free or reserved. A search through the free lists would be necessary, or an equivalent external table would have to be maintained. Such a table merely stores the same information elsewhere. Therefore the buddy system cannot dispense with the tag information; it can only relocate it. The tag bit is the mechanism that permits constant-time determination of whether a buddy may be combined. $\boxed{\text{No, not without storing equivalent status information elsewhere.}}$