Loading...
Please wait, while we are loading the content...
Similar Documents
Number : WUCSE-2004-58 2004-1007 Heap Defragmentation in Bounded Time
| Content Provider | Semantic Scholar |
|---|---|
| Author | Cholleti, Sharath R. Defoe, Delvin C. Cytron, Ron |
| Copyright Year | 2016 |
| 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 issue 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 synthetic benchmarks. Our algorithm is within a factor of two of optimal in terms of the time required 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. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://openscholarship.wustl.edu/cgi/viewcontent.cgi?article=2031&context=cse_research |
| Alternate Webpage(s) | https://openscholarship.wustl.edu/cgi/viewcontent.cgi?article=2031&context=cse_research&httpsredir=1&referer= |
| Alternate Webpage(s) | http://openscholarship.wustl.edu/cgi/viewcontent.cgi?article=2031&context=cse_research |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
