TAOCP 2.5 Exercise 20
In the buddy system, a block is repeatedly split and recombined with its unique buddy.
Section 2.5: Dynamic Storage Allocation
Exercise 20. [**] [00] Why is it desirable to have the AVAIL[k] lists in the buddy
system doubly linked instead of simply having straight linear lists?
Verified: yes
Solve time: 1m15s
In the buddy system, a block is repeatedly split and recombined with its unique buddy. When a block becomes free, the deallocation algorithm must determine quickly whether its buddy is also free so that the two blocks can be merged into a larger block. If the lists $\text{AVAIL}[k]$ were singly linked, removing the buddy from its free list would require a search for the preceding link, taking time proportional to the length of the list.
With doubly linked lists, each free block contains links in both directions. Once the buddy has been located, it can be removed from $\text{AVAIL}[k]$ immediately, without searching for its predecessor. Since coalescing adjacent buddies is the fundamental operation of the buddy system, doubly linked lists make deallocation and recombination substantially faster and keep these operations independent of the current length of the free lists. $\boxed{\text{Doubly linked lists permit immediate deletion of a buddy from } \text{AVAIL}[k] \text{ during coalescing.}}$