A comparison of next-fit, first-fit, and best-fit

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.

REFERENCES

• 1: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 2: John E. Shore, On the external storage fragmentation produced by first-fit and best-fit allocation strategies, Communications of the ACM, v.18 n.8, p.433-440, Aug. 1975 [doi>10.1145/360933.360949]

INDEX TERMS

Keywords:
best-fit, first-fit, memory allocation, next-fit