On the External Storage Fragmentation Produced by First-Fit and Best-Fit Allocation Strategies.

Published comparisons of the external fragmentation produced by first-fit and best-fit memory allocation have not been consistent. Through simulation, a series of experiments were performed in order to obtain better data on the relative performance of first-fit and best-fit and a better understanding of the reasons underlying observed differences. The time-memory-product efficiencies of first-fit best-fit were generally within about 1 of each other. Except for small populations, the size of the request population had little effect on allocation efficiency. For exponential distributions of requests, first-fit outperformed best-fit, but for normal and uniform distributions, and for exponential distributions distorted in various ways, best-fit outperformed first-fit. Modified author abstract