Technical Report Number
Knuth’s buddy system is an attractive algorithm for managing storage allocation, and it can be made to operate in real time. However, the is-sue of defragmentation for heaps that are managed by the buddy system has not been studied. In this paper, we present strong bounds on the amount of storage necessary to avoid defragmentation. We then present an algorithm for defragmenting buddy heaps and present experiments from applying that algorithm to real and syn-thetic benchmarks. Our algorithm is within a factor of two of optimal in terms of the time re-quired to defragment the heap so as to respond to a single allocation request. Our experiments show our algorithm to be much more eﬃcient than extant defragmentation algorithms.
Cholleti, Sharath R.; Defoe, Delvin; and Cytron, Ron K., "Heap Defragmentation in Bounded Time" Report Number: WUCSE-2004-58 (2004). All Computer Science and Engineering Research.