On the external storage fragmentation produced by first-fit and best-fit allocation strategies

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.

REFERENCES

• 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.
• 2: Wald, B. Utilization of a multiprocessor in command control. Proc. IEEE 54, 12 (Dec. 1966), 1885-88.
• 3: Rosen Saul, Programming Systems and Languages., McGraw Hill Text, 1967
• 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.
• 5: Wald, B. Private communication.
• 6: George O. Collins, Jr., Experience in automatic storage allocation, Communications of the ACM, v.4 n.10, p.436-440, Oct. 1961 [doi>10.1145/366786.366802]
• 7: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 8: B. Randell, A note on storage fragmentation and program segmentation, Communications of the ACM, v.12 n.7, p.365-ff., July 1969 [doi>10.1145/363156.363158]
• 9: Alan Batson , Shy-Ming Ju , David C. Wood, Measurements of segment size, Communications of the ACM, v.13 n.3, p.155-159, March 1970 [doi>10.1145/362052.362055]
• 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.
• 11: Margolin, B.H., Parmelee, R.P,, and Schatzoff, M. Analysis of free-storage algorithms. IBM SYST J. 4, (1971).
• 12: Wilson, S. Private communication.
• 13: Fisz, M. Probability Theory and Mathematical Statistics. Wiley, New York, 1963, Chap. 13.
• 14: Loeve, M. Probability Theory. Van Nostrand, New York, 1955, p. 159.
• 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.
• 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.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Design, Performance, Theory

Keywords:
best-fit, dynamic memory allocation, first-fit, storage fragmentation