Reservation Strategies (First-Fit and Best-Fit)

Key Insight

Reserving 'N' consecutive words requires locating an available block of 'm' words, where 'm' is greater than or equal to 'N', and then reducing its size to 'm - N'. If 'm' equals 'N', the block is completely removed from the available list. Two principal strategies for choosing among suitable available blocks are the best-fit and first-fit methods. The best-fit method selects the smallest available block of size 'm' that satisfies 'm >= N', which might require searching the entire list. The first-fit method, conversely, simply chooses the first encountered area that has 'm >= N' words.

Historically, the best-fit method was widely used, appearing to save larger areas for future needs. However, it is slower due to extensive searching and tends to increase the number of very small, often useless, blocks. The first-fit method frequently demonstrates better performance; for example, if available areas are 1300 and 1200 words, and requests are for 1000, 1100, then 250 words, first-fit successfully allocates all, while best-fit fails at the last request. Given that neither method consistently dominates, the simpler and faster first-fit method is generally recommended.

Algorithm A, a first-fit implementation, traverses a linked list of available blocks pointed to by AVAIL. It searches for a block 'P' where SIZE(P) is greater than or equal to 'N'. If such a block is found, 'K = SIZE(P) - N' is calculated. If 'K = 0', the block is entirely reserved, and removed from the list. Otherwise, SIZE(P) is reduced to 'K', and the reserved area begins at location 'P + K'. A refined step, A4', suggests reserving slightly more than 'N' words (if 'K' is less than a small constant 'c', e.g., 8 or 10) to avoid creating tiny, almost useless, blocks. This refinement implies that a SIZE field is present in the first word of all blocks, whether available or reserved, for proper bookkeeping.