TAOCP 2.5 Exercise 8
To obtain the best-fit method, modify Algorithm A so that it does not stop when the first block with `SIZE(P) \ge N` is found.
Section 2.5: Dynamic Storage Allocation
Exercise 8. [**] [21] Show how to modify Algorithm A in a simple way to obtain an algorithm for the best-fit method, instead of first-fit.
Verified: no
Solve time: -
To obtain the best-fit method, modify Algorithm A so that it does not stop when the first block with SIZE(P) \ge N is found. Instead, search the entire AVAIL list and keep track of the smallest block whose size is at least N.
During the search, whenever a block P satisfies SIZE(P) \ge N, compare its size with the size of the best candidate found so far. If no candidate has yet been found, or if SIZE(P) is smaller than the current candidate's size, record P as the new candidate. After the entire list has been examined, allocate storage from the recorded candidate exactly as in Algorithm A. If no candidate exists, invoke the overflow procedure.
Since every available block is inspected and the admissible block of minimum size is selected, the resulting algorithm implements the best-fit policy instead of first-fit. The remainder of the allocation procedure is unchanged.