ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Buddy systems
Full text PdfPdf (972 KB)
Source
Communications of the ACM archive
Volume 20 ,  Issue 6  (June 1977) table of contents
Pages: 421 - 431  
Year of Publication: 1977
ISSN:0001-0782
Authors
James L. Peterson  Univ. of Texas, Austin
Theodore A. Norman  Brigham Young Univ., Provo, UT
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 9,   Downloads (12 Months): 63,   Citation Count: 30
Additional Information:

abstract   references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/359605.359626
What is a DOI?

ABSTRACT

Two algorithms are presented for implementing any of a class of buddy systems for dynamic storage allocation. Each buddy system corresponds to a set of recurrence relations which relate the block sizes provided to each other. Analyses of the internal fragmentation of the binary buddy system, the Fibonacci buddy system, and the weighted buddy system are given. Comparative simulation results are also presented for internal, external, and total fragmentation.


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
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]
 
2
Ferguson, H.R.P. On a generalization of the Fibonacci numbers useful in memory allocation schema. The Fibonacci Quart., 14, 3 (Oct. 1976), 233-243.
 
3
Harris, V.C., and Styles, C.C. A generalization of Fibonacci numbers. The Fibonacci Quart. 2, 4 (Dec. 1964), 227-289.
4
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]
5
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]
 
6
Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
 
7
Lewis, T.G., Smith, B.J., and Smith, M.Z. Dynamic memory allocation systems for minimizing internal fragmentation. Proc. ACM Annual Conf., Nov. 1974, pp. 725-728.
 
8
Margolin, B.H., Parmelee, R.P., and Schatzoff, M. Analysis of free-storage algorithms. IBM Systems J. 10, 4 (1971), 283-304.
 
9
Norman, T.A. Tailored buddy systems for dynamic storage allocation. Proc. Fourth Texas Conf. Comptg. Systems, Nov. 1975, pp. 2B-3.1-2B-3.5.
10
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]
 
11
Russell, D.L. Internal fragmentation in a class of buddy systems. Tech. Note 54, Digital Systems Lab., Stanford U., Stanford, Calif., Jan. 1975.
12
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]

CITED BY  30
R. P. Brent, Efficient implementation of the first-fit strategy for dynamic storage allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.3, p.388-403, July 1989
R. Barkley , T. Lee, A lazy buddy system bounded by two coalescing delays, ACM SIGOPS Operating Systems Review, v.23 n.5, p.167-176, Dec. 3–6, 1989
Mark S. Johnstone , Paul R. Wilson, The memory fragmentation problem: solved?, ACM SIGPLAN Notices, v.34 n.3, p.26-36, March 1999
Makoto Yoshida , Makoto Kotera , Kyoko Yokoyama , Sadayuki Hikita, Approaches to an integrated office enviroment, Proceedings of 1986 ACM Fall joint computer conference, p.1064-1070, November 1986, Dallas, Texas, United States
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
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
Madhusudhan Talluri , Mark D. Hill, Surpassing the TLB performance of superpages with less operating system support, ACM SIGPLAN Notices, v.29 n.11, p.171-182, Nov. 1994
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
Dominique Decouchant, Design of a distributed object manager for the Smalltalk-80 system, ACM SIGPLAN Notices, v.21 n.11, p.444-452, Nov. 1986
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
Juan Navarro , Sitararn Iyer , Peter Druschel , Alan Cox, Practical, transparent operating system support for superpages, ACM SIGOPS Operating Systems Review, v.36 n.SI, Winter 2002
Dror G. Feitelson, Distributed Hierarchical Control for Parallel Processing, Computer, v.23 n.5, p.65-77, May 1990
J. Morris Chang , Edward F. Gehringer, A High-Performance Memory Allocator for Object-Oriented Systems, IEEE Transactions on Computers, v.45 n.3, p.357-366, March 1996
K. Li , K. H. Cheng, Job Scheduling in a Partitionable Mesh Using a Two-Dimensional Buddy System Partitioning Scheme, IEEE Transactions on Parallel and Distributed Systems, v.2 n.4, p.413-422, October 1991
P. J. Chuang , N. F. Tzeng, Allocating Precise Submeshes in Mesh Connected Systems, IEEE Transactions on Parallel and Distributed Systems, v.5 n.2, p.211-217, February 1994
Carsten Vogt, A Buffer-Based Method for Storage Allocation in an Object-Oriented System, IEEE Transactions on Computers, v.39 n.3, p.375-383, March 1990
Virginia Lo , Kurt J. Windisch , Wanqian Liu , Bill Nitzberg, Noncontiguous Processor Allocation Algorithms for Mesh-Connected Multicomputers, IEEE Transactions on Parallel and Distributed Systems, v.8 n.7, p.712-726, July 1997
Juan Navarro , Sitaram Iyer , Peter Druschel , Alan Cox, Practical, transparent operating system support for superpages, Proceedings of the 5th symposium on Operating systems design and implementation

Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

, December 09-11, 2002, Boston, Massachusetts
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
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
Miguel Masmano , Ismael Ripoll , Alfons Crespo, A comparison of memory allocators for real-time applications, Proceedings of the 4th international workshop on Java technologies for real-time and embedded systems, October 11-13, 2006, Paris, France
An-I Andy Wang , Geoff Kuenning , Peter Reiher , Gerald Popek, The Conquest file system: Better performance through a disk/persistent-RAM hybrid design, ACM Transactions on Storage (TOS), v.2 n.3, p.309-348, August 2006
Hong Min , Sangho Yi , Yookun Cho , Jiman Hong, An efficient dynamic memory allocator for sensor operating systems, Proceedings of the 2007 ACM symposium on Applied computing, March 11-15, 2007, Seoul, Korea
T. J. Lehman , B. G. Lindsay, The Starburst long field manager, Proceedings of the 15th international conference on Very large data bases, p.375-383, July 1989, Amsterdam, The Netherlands
Mel Gorman , Patrick Healy, Supporting superpage allocation without additional hardware support, Proceedings of the 7th international symposium on Memory management, June 07-08, 2008, Tucson, AZ, USA
Siddharth Choudhuri , Tony Givargis, Performance improvement of block based NAND flash translation layer, Proceedings of the 5th IEEE/ACM international conference on Hardware/software codesign and system synthesis, September 30-October 03, 2007, Salzburg, Austria
Miguel Masmano , Ismael Ripoll , Patricia Balbastre , Alfons Crespo, A constant-time dynamic storage allocator for real-time systems, Real-Time Systems, v.40 n.2, p.149-179, November 2008
M. Masmano , I. Ripoll , J. Real , A. Crespo , A. J. Wellings, Implementation of a constant-time dynamic storage allocator, Software—Practice & Experience, v.38 n.10, p.995-1026, August 2008
Mansi Ramakrishnan Thoppian , Ravi Prakash, A Distributed Protocol for Dynamic Address Assignment in Mobile Ad Hoc Networks, IEEE Transactions on Mobile Computing, v.5 n.1, p.4-19, January 2006

INDEX TERMS

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

Collaborative Colleagues:
James L. Peterson: colleagues
Theodore A. Norman: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player