Paper by Erik D. Demaine
- Erik D. Demaine and J. Ian Munro, “Fast Allocation and Deallocation with an Improved Buddy System”, in Proceedings of the 19th Conference on the Foundations of Software Technology and Theoretical Computer Science (FST & TCS'99), Lecture Notes in Computer Science, volume 1738, Chennai, India, December 13–15, 1999, pages 84–96.
We propose several modifications to the binary buddy system for managing
dynamic allocation of memory blocks whose sizes are powers of two. The
standard buddy system allocates and deallocates blocks in Θ(lg n)
time in the worst case (and on an amortized basis), where n is the size
of the memory. We present two schemes that improve the running time to
O(1) time, where the time bound for deallocation is amortized. The
first scheme uses one word of extra storage compared to the standard buddy
system, but may fragment memory more than necessary. The second scheme has
essentially the same fragmentation as the standard buddy system, and uses
O(2(1 + √lg n) lg lg n) bits of auxiliary
storage, which is ω(lgk n) but
o(nε) for all k ≥ 1 and
ε > 0.
Finally, we present simulation results estimating the effect of the excess
fragmentation in the first scheme.
- This paper is also available from the electronic LNCS volume as http://link.springer.de/link/service/series/0558/papers/1738/17380084.pdf.
- The paper is \copyright Springer-Verlag.
- The paper is 12 pages.
- The paper is available in PostScript (202k) and gzipped PostScript (75k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- Buddy_ActaInf (Fast Allocation and Deallocation with an Improved Buddy System)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated January 8, 2018 by