Dynamic memory allocation in computer simulation

ABSTRACT

e of 35 dynamic memory allocation algorithms when used to service simulation programs as represented by 18 test cases. Algorithm performance was measured in terms of processing time, memory usage, and external memory fragmentation. Algorithms maintaining separate free space lists for each size of memory block used tended to perform quite well compared with other algorithms. Simple algorithms operating on memory ordered lists (without any free list) performed surprisingly well. Algorithms employing power-of-two block sizes had favorable processing requirements but generally unfavorable memory usage. Algorithms employing LIFO, FIFO, or memory ordered free lists generally performed poorly compared with others.

REFERENCES

• 1: M. J. Bailey , M. P. Barnett , P. B. Burleson, Symbol manipulation in FORTRAN: SASP I subroutines, Communications of the ACM, v.7 n.6, June 1964 [doi>10.1145/512274.512282]
• 2: A. T. Berztiss, A note on storage of strings, Communications of the ACM, v.8 n.8, p.512, Aug. 1965 [doi>10.1145/365474.365525]
• 3: Campbell, J.A. A note on an optimal fit method for dynamic allocation of storage. Computer J. 14, 1 (Feb. 1971), 7-9.
• 4: W. T. Comfort, Multiword list items, Communications of the ACM, v.7 n.6, June 1964 [doi>10.1145/512274.512288]
• 5: Ben Cranston , Rick Thomas, A simplified recombination scheme for the Fibonacci buddy system, Communications of the ACM, v.18 n.6, p.331-332, June 1975 [doi>10.1145/360825.360854]
• 6: Fenton, J.S., and Payne, D.W. Dynamic storage allocation of arbitrary sized segments. Information Processing 74, North-Holland Pub. Co., Amsterdam, 1974, pp. 344-348.
• 7: James A. Hinds, An algorithm for locating adjacent storage blocks in the buddy system, Communications of the ACM, v.18 n.4, p.221-222, April 1975 [doi>10.1145/360715.360752]
• 8: Daniel S. Hirschberg, A class of dynamic memory allocation algorithms, Communications of the ACM, v.16 n.10, p.615-618, Oct. 1973 [doi>10.1145/362375.362392]
• 9: Iliffe, J.K., and Jodeit, J.G. A dynamic storage allocation scheme. ComputerJ. 5, 3 (Oct. 1962), 200-209.
• 10: IBM System 360/Model 65 Functional Characteristics. Form A22-6884-0, IBM, White Plains, N.Y., pp. 19-29.
• 11: Sadahiro Isoda , Eiichi Goto , Izumi Kimura, A efficient bit table technique for dynamic storage allocation of 2"-word blocks, Communications of the ACM, v.14 n.9, p.589-592, Sept. 1971 [doi>10.1145/362663.362731]
• 12: Kiviat, P.J., Villanueva, R., and Markowitz, H.M. The SIM- SCRIPT H Programming Language. Prentice-Hall, Englewood Cliffs, N.J., 1968.
• 13: Kenneth C. Knowlton, A fast storage allocator, Communications of the ACM, v.8 n.10, p.623-624, Oct. 1965 [doi>10.1145/365628.365655]
• 14: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 15: Lewis, P.A.W., Goodman, A.S., and Miller, J.M. A pseudorandom number generator for the System/360. IBM Systems J. 8, 2 (1969), 136-146.
• 16: Margolin, B.H., Parmelee, R.P., and Schatzoff, M. Analysis of free storage algorithms. IBM Systems J. 10, 4 (1971), 283-304.
• 17: Markowitz, H.M., Hausner, B., and Karr, H.W. SIMSCRIPT- A Simulation Programming Language. Prentice-Hall, Englewood Cliffs, N.J., 1963.
• 18: Nielsen, N.R. Dynamic memory allocation in a simulation environment. Res. Paper 181, Stanford GSB, Stanford Res. Inst., Menlo Park, Calif., Aug. 1973.
• 19: PritskereA.A.B., and Kiviat, P.J. Simulation with GASP H. Prentice-Hall, Englewood Cliffs, N.J., 1969.
• 20: Paul W. Purdom, Jr. , Stephen M. Stigler, Statistical Properties of the Buddy System, Journal of the ACM (JACM), v.17 n.4, p.683-697, Oct. 1970 [doi>10.1145/321607.321617]
• 21: 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]
• 22: Douglas T. Ross, The AED free storage package, Communications of the ACM, v.10 n.8, p.481-492, Aug. 1967 [doi>10.1145/363534.363546]
• 23: Kenneth K. Shen , James L. Peterson, A weighted buddy method for dynamic storage allocation, Communications of the ACM, v.17 n.10, p.558-562, Oct. 1974 [doi>10.1145/355620.361164]
• 24: 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:
algorithm performance, dynamic memory allocation, dynamic memory management, dynamic storage allocation, garbage collection, list processing, memory allocation, memory management, programming techniques, simulation, simulation memory management, simulation techniques, space allocation, storage allocation