Document Type

Technical Report

Publication Date

2003-01-31

Filename

wucse-2003-2.pdf

Technical Report Number

WUCSE-2003-2

Abstract

The correctness of a real-time system is very much dependent on the time at which a specific task is completed. Hence, satisfying a storage allocation request within bounded time is important. Fragmentation of the heap after repeated allocations and deallocations is a major issue for real-time systems, as most allocators depend on garbage collection for defragmentation of the heap, which might not finish in time to honor deadlines. We present the storage requirement for a defragmentation-free binary-buddy allocator. We also study a localized defragmentation algorithm to satisfy a single allocation request, within bounded time, instead of requiring defragmentation of the entire heap. We prove that the cost of the algorithm is within twice the optimal cost. Results are presented from applying the defragmentation algorithm, with different heap sizes, on various programs. The amount of storage relocated with our defragmentation algorithm is compared with other compaction algorithms. Also, the amount of storage relocated by selecting a minimally occupied block is compared with the policy of selecting a block randomly.

Comments

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

Download

Share

COinS