John E. Shore
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 and best-fit were generally within 1 to 3 percent of each other. Except for small populations, the size of the request population had little effect on allocation efficiency. For exponential and hyperexponential distributions of requests, first-fit outperformed best-fit; but for normal and uniform distributions, and for exponential distributions distorted in various ways, best-fit out-performed first-fit. It is hypothesized that when first-fit outperforms best-fit, it does so because first-fit, by preferentially allocating toward one end of memory, encourages large blocks to grow at the other end. Sufficient contiguous space is thereby more likely to be available for relatively large requests. Results of simulation experiments supported this hypothesis and showed that the relative performance of first-fit and best-fit depends on the frequency of requests that are large compared to the average request. When the coefficient of variation of the request distribution is greater than or approximately equal to unity, first-fit outperformed best-fit.
- 1 Campbell, J.A. A note on an optimal-fit method for dynamic allocation of storage. The Computer J. 14, 1 (Jan. 1971), 7-9.Google Scholar
Cross Ref
- 2 Wald, B. Utilization of a multiprocessor in command control. Proc. IEEE 54, 12 (Dec. 1966), 1885-88.Google ScholarCross Ref
- 3 Thompson, R., and Wilkinson, J. The D825 automatic operating and scheduling program. Proc. AFIPS 1963 SJCC, pp 139-146, May 1963; reprinted in S. Rosen, Programming Systems and Language, McGraw-Hill, New York, 1967. Google ScholarDigital Library
- 4 Anderson, J.P., et al. D825--A multiple-computer system for command and control. Proc. AFIPS 1962 FJCC, pp 86-96, Dec 1962; reprinted in C.G. Bell and A. Newell, Computer Structures-Readings and Examples, McGraw-Hill, New York, 1971.Google ScholarDigital Library
- 5 Wald, B. Private communication.Google Scholar
- 6 Collins, G.O. Experience in automatic storage allocation. Comm. ACM 4, 10 (Oct. 1961), 436-440. Google ScholarDigital Library
- 7 Knuth, D.E. The Art of Computer Programming, Vol I Fundamental Algorithms, Addison-Wesley, Reading, Mass., 1968, pp. 435-452. Google ScholarDigital Library
- 8 Randell, B. A note on storage fragmentation and program segmentation. Comm. ACM 12, 7 (July 1969), 365-372. Google ScholarDigital Library
- 9 Batson, A., Ju, S., and Wood, D.C. Measurements of segment size. Comm. ACM 13, 3 (Mar. 1970), 155-159. Google ScholarDigital Library
- 10 Totschek, R.A. An empirical investigation into the behavior of the SDC timesharing system. Rep. SP2191, AD 622003, System Development Corp., Santa Monica, Calif., 1965.Google Scholar
- 11 Margolin, B.H., Parmelee, R.P,, and Schatzoff, M. Analysis of free-storage algorithms. IBM SYST J. 4, (1971).Google Scholar
- 12 Wilson, S. Private communication.Google Scholar
- 13 Fisz, M. Probability Theory and Mathematical Statistics. Wiley, New York, 1963, Chap. 13.Google Scholar
- 14 Loeve, M. Probability Theory. Van Nostrand, New York, 1955, p. 159.Google Scholar
- 15 Shore, J.E. On the external storage fragmentation produced by first-fit and best-fit allocation strategies. Naval Research Lab. Memo. Rep. 2848, Washington, D.C., July 1974.Google Scholar
- 16 Fenton, J. S. and Payne, D. W. Dynamic storage allocation of arbitrary sized segments. Proc. IFIP 74, North-Holland Pub. Co., Amsterdam, 1974, pp. 344-348.Google Scholar
Index Terms
- On the external storage fragmentation produced by first-fit and best-fit allocation strategies
Recommendations
A comparison of next-fit, first-fit, and best-fit
“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 “...
Parallel bin packing using first fit and k-delayed best-fit heuristics
SPDP '90: Proceedings of the 1990 IEEE Second Symposium on Parallel and Distributed ProcessingThe authors describe the development of parallel implementations for the bin packing problem. Bin packing algorithms are studied to understand various resource allocation issues and the impact of the different packing heuristics on the packing ...
Comparing First-Fit and Next-Fit for Online Edge Coloring
ISAAC '08: Proceedings of the 19th International Symposium on Algorithms and ComputationWe study the performance of the algorithms First-Fit and Next-Fit for two online edge coloring problems. In the min-coloring problem, all edges must be colored using as few colors as possible. In the max-coloring problem, a fixed number of colors is ...
Comments