TAOCP 2.5 Exercise 6
A simple modification is to remember the position at which the previous successful search ended, and begin the next search there instead of always starting at the front of the `AVAIL` list.
Section 2.5: Dynamic Storage Allocation
Exercise 6. [**] [23] (Next fit.) After Algorithm A has been used repeatedly, there
will be a strong tendency for blocks of small SIZE to remain at the
front of the AVAIL list, so that it will often be necessary to search
quite far into the list before finding a block of length N or more. For
example, notice how the size of the blocks essentially increases in Fig.
42, for both reserved and free blocks, from the beginning of memory to the
end. (The AVAIL list used while Fig. 42 was being prepared was kept
sorted by order of location, as required by Algorithm B.) Can you suggest
a way to modify Algorithm A so that (a) short blocks won't tend to
accumulate in a particular area, and (b) the AVAIL list may still be
kept in order of increasing memory locations, for purposes of algorithms
like Algorithm B?
Verified: yes
Solve time: 1m33s
A simple modification is to remember the position at which the previous successful search ended, and begin the next search there instead of always starting at the front of the AVAIL list. Let ROVER point to the block most recently examined when a reservation succeeded. To satisfy a request for length N, search the circularly linked AVAIL list beginning at ROVER, proceeding through successive links until a block of size at least N is found, or until the search returns to ROVER. After allocation, set ROVER to the predecessor or successor of the block just used, so that later searches continue from approximately the same region of memory.
This "next-fit" method distributes allocations over the entire memory instead of repeatedly examining the smallest free blocks near the front of the list. Hence small blocks do not accumulate in a single area. Since the search order follows the existing circular AVAIL list, the list may still be maintained in increasing order of memory location, exactly as required by Algorithm B. The ordering of free blocks is unchanged; only the point at which each search begins is changed.