Statistical Properties of the Buddy System

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Statistical Properties of the Buddy System

Full text

Pdf (851 KB)

Source

Journal of the ACM (JACM) archive
Volume 17 , Issue 4 (October 1970) table of contents

Pages: 683 - 697

Year of Publication: 1970

ISSN:0004-5411

Authors

Paul W. Purdom, Jr.	Bell Telephone Laboratories, Naperville, Ill and University of Wisconsin, Computer Science Department and Statistics Department, Madison, Wisconsin
Stephen M. Stigler	University of Wisconsin, Computer Science Department and Statistics Department, Madison, Wisconsin

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 25, Citation Count: 13

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/321607.321617 What is a DOI?

ABSTRACT

The utilization of space and the running speed of the buddy system are considered Equations are derived that give various statistical properties of the buddy system. For the bottom level with Poisson requests and exponential service times the expected amount of space wasted by pairing full cells with empty cells is about 0.513 &rgr;1/2 and the mean time between requests from the bottom level to the next level is about 1.880 &rgr;1/2 &lgr;-1, where &rgr; is the mean number of blocks in use on the bottom level and &lgr;-1 is the mean time between requests for blocks on the bottom level. The results of a number of simulations of the buddy system are also given and compared with the analytical studies.

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	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	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]
	3	PURDOM, PAUL W., JR., AND STIGLER, STEPHEN M. Statistical properties of the buddy system. Computer Sciences Tech. Rep. 60, U. of Wisconsin, Madison, Wis., 1969.
	4	KARLIN, SAMUEL. A First Course in Stochastic Processes. Academic Press, New York, 1966, pp. 189-194.

CITED BY 13

	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
	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 B. Morris, Demand paging through utilization of working sets onr the MANIAC II, Communications of the ACM, v.15 n.10, p.867-872, Oct. 1972
	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
	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
	Daniel S. Hirschberg, A class of dynamic memory allocation algorithms, Communications of the ACM, v.16 n.10, p.615-618, Oct. 1973
	Therapon Skotiniotis , Ji-en Morris Chang, Estimating internal memory fragmentation for Java programs, Journal of Systems and Software, v.64 n.3, p.235-246, 15 December 2002
	Shahram Latifi, Task Allocation in the Star Graph, IEEE Transactions on Parallel and Distributed Systems, v.5 n.11, p.1220-1224, November 1994
	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
	Philip D. L. Koch, Disk file allocation based on the buddy system, ACM Transactions on Computer Systems (TOCS), v.5 n.4, p.352-370, Nov. 1987
	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
	Christian Del Rosso, Software performance tuning of software product family architectures: Two case studies in the real-time embedded systems domain, Journal of Systems and Software, v.81 n.1, p.1-19, January, 2008