TAOCP 2.5 Exercise 31

Section 2.5: Dynamic Storage Allocation

Exercise 31. [**] [M40] Can a storage allocation system analogous to the buddy system be designed using the Fibonacci sequence instead of powers of two? (Thus, we might start with $F_m$ available words, and split an available block of $F_k$ words into two buddies of respective lengths $F_{k-1}$ and $F_{k-2}$.)

Verified: yes
Solve time: 1m10s

Yes. The essential operations of the buddy system remain valid when block sizes are Fibonacci numbers. If an available block has size $F_k$, it may be split into adjacent buddies of sizes $F_{k-1}$ and $F_{k-2}$, since

$$ F_k=F_{k-1}+F_{k-2}. $$

Repeated splitting therefore produces blocks whose sizes belong to the Fibonacci sequence, and a request for $n$ words can be satisfied by allocating the smallest Fibonacci block whose size is at least $n$.

The difficulty lies in recombination. In the ordinary buddy system, a block's buddy is determined immediately from its address because all blocks of a given size arise from a unique binary subdivision. With Fibonacci sizes, a block of size $F_k$ may adjoin either a block of size $F_{k+1}$ or a block of size $F_{k-1}$, depending on how the subdivision was performed. Consequently, the buddy of a block cannot in general be identified from its address and size alone. Additional information must be maintained to record the subdivision structure. Thus a Fibonacci buddy system can be designed, but it is considerably more complicated than the power-of-two system and loses the simple buddy-identification property that makes the ordinary buddy system attractive.

$$ \boxed{\text{A Fibonacci analogue is possible, but it requires extra bookkeeping to identify and recombine buddies.}} $$