A class of dynamic memory allocation algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A class of dynamic memory allocation algorithms

Full text

Pdf (336 KB)

Source

Communications of the ACM archive
Volume 16 , Issue 10 (October 1973) table of contents

Pages: 615 - 618

Year of Publication: 1973

ISSN:0001-0782

Author

Daniel S. Hirschberg

Princeton Univ., Princeton, NJ

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 83, Citation Count: 15

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/362375.362392 What is a DOI?

ABSTRACT

A new dynamic memory allocation algorithm, the Fibonacci system, is introduced. This algorithm is similar to, but seems to have certain advantages over, the “buddy” system. A generalization is mentioned which includes both of these systems as special cases.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	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]
	2	Kenneth C. Knowlton, A programmer's description of L6, Communications of the ACM, v.9 n.8, p.616-625, Aug. 1966 [doi>10.1145/365758.365792]
	3	Knuth, D.E. The Art of Computer Programmhtg, Vol. 1 (2nd printing). Addison-Wesley, Reading, Mass., 1968, pp. 435-455.
	4	Minker, J., et al. Analysis of data processing systems. Tech. Rept. 69-99, U. of Maryland, College Park, Md., 1969.
	5	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]

CITED BY 16

	John E. Shore, Anomalous behavior of the fifty-percent rule in dynamic memory allocation, Communications of the ACM, v.20 n.11, p.812-820, Nov. 1977
	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
	Matthew S. Hecht , John D. Gabbe, Shadowed management of free disk pages with a linked list, ACM Transactions on Database Systems (TODS), v.8 n.4, p.503-514, Dec. 1983
	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
	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
	Arie Kaufman, Tailored-List and Recombination-Delaying Buddy Systems, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.1, p.118-125, Jan. 1984
	Arie Kaufman, Variations on the binary buddy system for dynamic memory management, Proceedings of the 18th annual Southeast regional conference, March 24-26, 1980, Tallahassee, Florida
	Warren Burton, A buddy system variation for disk storage allocation, Communications of the ACM, v.19 n.7, p.416-417, July 1976
	Keqin Li , Kam Hoi Cheng, A two dimensional buddy system for dynamic resource allocation in a partitionable mesh connected system, Proceedings of the 1990 ACM annual conference on Cooperation, p.22-27, February 20-22, 1990, Washington, D.C., United States
	James L. Peterson , Theodore A. Norman, Buddy systems, Communications of the ACM, v.20 n.6, p.421-431, June 1977
	Norman R. Nielsen, Dynamic memory allocation in computer simulation, Communications of the ACM, v.20 n.11, p.864-873, Nov. 1977
	Leland L. Beck, A dynamic storage allocation technique based on memory residence time, Communications of the ACM, v.25 n.10, p.714-724, Oct 1982
	Divakar Yadav , A. K. Chaturvedi , Snehil Pansari , Avart Krishnan, Memory management: tertiary buddy system, Proceedings of the 2nd WSEAS International Conference on Computer Engineering and Applications, p.46-49, January 25-27, 2008, Acapulco, Mexico
	Ted G. Lewis , Brian J. Smith , Marilyn Z. Smith, Dynamic memory allocation systems for minimizing internal fragmentation, Proceedings of the 1974 annual ACM conference, January 01-01, 1974
	Alin Jula , Lawrence Rauchwerger, Two memory allocators that use hints to improve locality, Proceedings of the 2009 international symposium on Memory management, June 19-20, 2009, Dublin, Ireland
	R. Trimble, Storage management in IBM APL systems, IBM Systems Journal, v.30 n.4, p.456-468, 1991

INDEX TERMS

Keywords:
Fibonacci, buddy system, dynamic storage allocation, fragmentation, simulation

Collaborative Colleagues:

Daniel S. Hirschberg: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player