Accession Number : AD0786694

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

Descriptive Note : Interim rept.,

Corporate Author : NAVAL RESEARCH LAB WASHINGTON D C

Personal Author(s) : Shore,John E.

Report Date : JUL 1974

Pagination or Media Count : 32

Abstract : 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)

Descriptors :   *Memory devices, *Allocations, Statistical analysis, Computer programming

Subject Categories : Computer Programming and Software
      Computer Hardware
      Computer Systems Management and Standards

Distribution Statement : APPROVED FOR PUBLIC RELEASE