A comparison of next-fit, first-fit, and best-fit
- 1 March 1977
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 20 (3) , 191-192
- https://doi.org/10.1145/359436.359453
Abstract
“Next-fit” allocation differs from first-fit in that a first-fit allocator commences its search for free space at a fixed end of memory, whereas a next-fit allocator commences its search wherever it previously stopped searching. This strategy is called “modified first-fit” by Shore [2] and is significantly faster than the first-fit allocator. To evaluate the relative efficiency of next-fit (as well as to confirm Shore's results) a simulation was written in Basic Plus on the PDP-11, using doubly linked lists to emulate the memory structure of the simulated computer. The simulation was designed to perform essentially in the manner described in [2]. The results of the simulation of the three methods show that the efficiency of next-fit is decidedly inferior to first-fit and best-fit when the mean size of the block requested is less than about 1/16 the total memory available. Beyond this point all three allocation schemes have similar efficiencies.Keywords
This publication has 1 reference indexed in Scilit:
- On the external storage fragmentation produced by first-fit and best-fit allocation strategiesCommunications of the ACM, 1975