TAOCP 2.5 Exercise 9
The essential idea is to organize the free blocks by size instead of by location.
Section 2.5: Dynamic Storage Allocation
Exercise 9. [**] [26] In what ways could a reservation algorithm be designed to use the
best-fit method, without searching through the whole AVAIL list? (Try
to think of ways that cut down the necessary search as much as possible.)
Verified: no
Solve time: -
The essential idea is to organize the free blocks by size instead of by location. If the blocks are kept in a search structure whose key is SIZE, for example a balanced tree, then a request for a block of length N can be satisfied by finding the smallest available key that is $\ge N$. This yields the best-fit block directly, without examining every element of the AVAIL list. When a block is split or returned to free storage, the corresponding size records are updated in the tree.
The search can be reduced even further by maintaining separate lists for size classes. For example, all blocks of a given size, or of sizes in a prescribed range, may be linked together. A request for size N first examines the class containing N; if no suitable block is present, the search proceeds to the next larger class. With sufficiently fine size classes, especially for small blocks, the best-fit block is usually found after inspecting only a few candidates. Exact-fit lists for frequently occurring sizes provide the extreme case, where many requests are satisfied with essentially no search at all.