TAOCP 2.5 Exercise 7
Consider an `AVAIL` list whose first two free blocks have sizes $25$ and $12$, in that order.
Section 2.5: Dynamic Storage Allocation
Exercise 7. [**] [10] The example (1) shows that first-fit can sometimes be definitely superior to best-fit. Give a similar example that shows a case where best-fit is superior to first-fit.
Verified: no
Solve time: -
Consider an AVAIL list whose first two free blocks have sizes $25$ and $12$, in that order. Suppose two allocation requests arrive consecutively, first for $N=12$ words and then for $N=25$ words.
With first-fit, the request for $12$ words is satisfied from the first block of size $25$, leaving a free block of size $13$. The free blocks are then of sizes $13$ and $12$. The subsequent request for $25$ words cannot be satisfied, although the original configuration contained a block of exactly that size.
With best-fit, the request for $12$ words is satisfied from the block of size $12$, leaving the block of size $25$ unchanged. The subsequent request for $25$ words is then satisfied exactly.
Thus best-fit succeeds in satisfying both requests, whereas first-fit fails on the second. This example shows that best-fit can be definitely superior to first-fit.