Summary
The worst-case performance of both binary and Fibonacci buddy systems is analyzed. For both unrestricted and allocation-only request sequences, exact bounds on both the external and total fragmentation are derived.
Similar content being viewed by others
References
Bromley, A.G.: Memory fragmentation in buddy methods for dynamic storage allocation. Acta Inf. 14, 107–118 (1980)
Hirschberg, D.S.: A class of dynamic memory allocation algorithms. Commun. ACM 16, 615–618 (1973)
Knowlton, K.C.: A fast storage allocator. Commun. ACM 8, 623–625 (1965)
Knuth, D.E.: The Art of Computer Programming 1, p. 634. Fundamental Algorithms, 2nd edition. Reading, MA: Addison-Wesley 1973
Krogdahl, S.: A dynamic storage allocation problem. Inf. Process. Letters 2, 96–99 (1973)
Loui, M.C.: Simulations among multidimensional Turing Machines. Theor. Comput. Sci. 21, 145–161 (1982)
Loui, M.C.: Minimizing access pointers into trees and arrays. J. Comput. Syst. Sci. (To appear)
Loui, M.C.: Optimal dynamic embedding of trees into arrays. SIAM J. Comput. 12, 463–472 (1983)
Peterson, D.L., Norman, T.A.: Buddy systems. Commun. ACM 20, 421–431 (1977)
Purdom, P.W., Stigler, S.M.: Statistical properties of the buddy system. J. ACM 17, 683–697 (1970)
Robson, J.M.: An estimate of the store size necessary for dynamic storage allocation. J. ACM 18, 416–423 (1971)
Robson, J.M.: Bounds for some functions concerning dynamic storage allocation. J. ACM 21, 491–499 (1974)
Russell, D.L.: Internal fragmentation in a class of buddy systems. SIAM J. Comput. 6, 607–621 (1977)
Shen, K.K., Peterson, J.L.: A weighted buddy system method for dynamic storage allocation. Commun. ACM 17, 558–562 (1974); 18, 202 (1975)
Author information
Authors and Affiliations
Additional information
Partially supported under NSF Grant MCS-8103713
Partially supported under NSF Grant IST-8012242
Rights and permissions
About this article
Cite this article
Lloyd, E.L., Loui, M.C. On the worst case performance of buddy systems. Acta Informatica 22, 451–473 (1985). https://doi.org/10.1007/BF00288778
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF00288778