article

Free access

A simplified recombination scheme for the Fibonacci buddy system

Authors:

Ben Cranston,

Rick ThomasAuthors Info & Claims

Communications of the ACM, Volume 18, Issue 6

Pages 331 - 332

https://doi.org/10.1145/360825.360854

Published: 01 June 1975 Publication History

PDF eReader

Abstract

A simplified recombination scheme for the Fibonacci buddy system which requires neither tables nor repetitive calculations and uses only two additional bits per buffer is presented.

References

[1]

Hirschberg, D.A class of dytnamic memory allocation algorithms. Comm. ACM16, 10 (Oct. 1973), 615-618.

Digital Library

Google Scholar

[2]

Hinds, James A. An algorithm for locating adjacent storage blocks in the buddy system (in preparation).

Google Scholar

[3]

Knuth, D. The Art of Computer Programming, Vol. 1. Addi- Wesley, Reading, Mass., 1968, pp. 443-444.

Digital Library

Google Scholar

[4]

Basili, V., and Turner, J. SIMPL-T, a structured programming language. CN-14, U. of Maryland, College Park, Md.

Google Scholar

Cited By

View all

Lu YLiu WWu CWang JGao XLi JGuo M(2021)Spring Buddy: A Self-Adaptive Elastic Memory Management Scheme for Efficient Concurrent Allocation/Deallocation in Cloud Computing Systems2021 IEEE 27th International Conference on Parallel and Distributed Systems (ICPADS)10.1109/ICPADS53394.2021.00056(402-409)Online publication date: Dec-2021
https://doi.org/10.1109/ICPADS53394.2021.00056
Liang YLi JAusavarungnirun RPan RShi LKuo TXue CGavrilovska AZadok E(2020)AcclaimProceedings of the 2020 USENIX Conference on Usenix Annual Technical Conference10.5555/3489146.3489208(897-910)Online publication date: 15-Jul-2020
https://dl.acm.org/doi/10.5555/3489146.3489208
Liang YLi QXue CYadgar GNoh S(2019)Mismatched memory management of Android smartphonesProceedings of the 11th USENIX Conference on Hot Topics in Storage and File Systems10.5555/3357062.3357072(7-7)Online publication date: 8-Jul-2019
https://dl.acm.org/doi/10.5555/3357062.3357072
Show More Cited By

Index Terms

A simplified recombination scheme for the Fibonacci buddy system
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Number-theoretic computations
2. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Allocation / deallocation strategies

Recommendations

Buddy systems

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 ...
A class of dynamic memory allocation algorithms

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 ...
A weighted buddy method for dynamic storage allocation

An extension of the buddy method, called the weighted buddy method, for dynamic storage allocation is presented. The weighted buddy method allows block sizes of 2^k and 3·2^k, whereas the original buddy method allowed only block sizes of 2^k. This ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Communications of the ACM Volume 18, Issue 6

June 1975

51 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/360825

Editor:
Robert L. Ashenhurst
Univ. of Chicago, IL

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1975

Published in CACM Volume 18, Issue 6

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
711
Total Downloads

Downloads (Last 12 months)125
Downloads (Last 6 weeks)12

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Lu YLiu WWu CWang JGao XLi JGuo M(2021)Spring Buddy: A Self-Adaptive Elastic Memory Management Scheme for Efficient Concurrent Allocation/Deallocation in Cloud Computing Systems2021 IEEE 27th International Conference on Parallel and Distributed Systems (ICPADS)10.1109/ICPADS53394.2021.00056(402-409)Online publication date: Dec-2021
https://doi.org/10.1109/ICPADS53394.2021.00056
Liang YLi JAusavarungnirun RPan RShi LKuo TXue CGavrilovska AZadok E(2020)AcclaimProceedings of the 2020 USENIX Conference on Usenix Annual Technical Conference10.5555/3489146.3489208(897-910)Online publication date: 15-Jul-2020
https://dl.acm.org/doi/10.5555/3489146.3489208
Liang YLi QXue CYadgar GNoh S(2019)Mismatched memory management of Android smartphonesProceedings of the 11th USENIX Conference on Hot Topics in Storage and File Systems10.5555/3357062.3357072(7-7)Online publication date: 8-Jul-2019
https://dl.acm.org/doi/10.5555/3357062.3357072
Park HChoi JLee DNoh S(2015)iBuddy: Inverse Buddy for Enhancing Memory Allocation/Deallocation Performanceon Multi-Core SystemsIEEE Transactions on Computers10.1109/TC.2013.229604964:3(720-732)Online publication date: 1-Mar-2015
https://dl.acm.org/doi/10.1109/TC.2013.2296049
Yadav DSharma A(2010)Tertiary buddy system for efficient dynamic memory allocationProceedings of the 9th WSEAS international conference on Software engineering, parallel and distributed systems10.5555/1807733.1807742(61-66)Online publication date: 20-Feb-2010
https://dl.acm.org/doi/10.5555/1807733.1807742
Brodal GDemaine EMunro J(2005)Fast allocation and deallocation with an improved buddy systemActa Informatica10.5555/2697438.269765641:4-5(273-291)Online publication date: 1-Mar-2005
https://dl.acm.org/doi/10.5555/2697438.2697656
Brodal GDemaine EMunro J(2005)Fast allocation and deallocation with an improved buddy systemActa Informatica10.1007/s00236-004-0159-641:4-5(273-291)Online publication date: Mar-2005
https://doi.org/10.1007/s00236-004-0159-6
Wilson PJohnstone MNeely MBoles D(2005)Dynamic storage allocation: A survey and critical reviewMemory Management10.1007/3-540-60368-9_19(1-116)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-60368-9_19
Demaine EMunro I(2000)Fast Allocation and Deallocation with an Improved Buddy SystemFoundations of Software Technology and Theoretical Computer Science10.1007/3-540-46691-6_7(84-96)Online publication date: 9-Jun-2000
https://doi.org/10.1007/3-540-46691-6_7
Trimble R(1991)Storage management in IBM APL systemsIBM Systems Journal10.1147/sj.304.045630:4(456-468)Online publication date: 1-Oct-1991
https://dl.acm.org/doi/10.1147/sj.304.0456
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Buddy systems

A class of dynamic memory allocation algorithms

A weighted buddy method for dynamic storage allocation

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations