Heap Defragmentation in Bounded Time

Authors

Sharath R. Cholleti, Washington University in St. Louis
Delvin Defoe, Washington University in St. Louis
Ron K. Cytron, Washington University in St. LouisFollow

Document Type

Technical Report

Publication Date

2004-10-07

Filename

wucse-2004-58.pdf

Technical Report Number

WUCSE-2004-58

Abstract

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 efficient than extant defragmentation algorithms.

Comments

Permanent URL: http://dx.doi.org/10.7936/K74X564Z

Recommended Citation

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.
https://openscholarship.wustl.edu/cse_research/1030