TAOCP 2.5 Exercise 26
Write M=\sum_{j=1}^{t}2^{m_j}, \qquad m_1>m_2>\cdots>m_t\ge0,
Section 2.5: Dynamic Storage Allocation
Exercise 26. [**] [21] Explain how the buddy system could be used for dynamic storage
allocation in memory locations 0 through M - 1 even when M does not
have the form $2^m$ as required in the text.
Exercises
Verified: yes
Solve time: 1m23s
Write
$$ M=\sum_{j=1}^{t}2^{m_j}, \qquad m_1>m_2>\cdots>m_t\ge0, $$
the binary expansion of $M$. Partition the memory locations $0,\ldots,M-1$ into consecutive blocks of these sizes:
$$ [0,2^{m_1}-1],; [2^{m_1},2^{m_1}+2^{m_2}-1],; \ldots $$
Each block begins at an address that is a multiple of its size, hence each is a legitimate buddy-system block. Initially place these blocks on the available-space lists corresponding to their sizes.
Allocation and deallocation are then performed exactly as in the ordinary buddy system. A request may split any available block into buddies repeatedly until the desired size is obtained. When a block is returned, it is combined with its buddy whenever that buddy is free; combinations stop when the containing initial block is reached, since no buddy exists across the boundary between two distinct blocks of the binary decomposition of $M$. Thus the memory behaves as a collection of disjoint buddy-system regions whose total size is $M$, allowing dynamic storage allocation for arbitrary $M$.