Compact Fit

Abstract

We propose a real real-time memory management system called Compact-fit that offers both time and space predictability. Compact-fit is a compacting memory management system for allocating, deallocating, and accessing memory in real time. The system provides predictable memory fragmentation and guarantees bounded (constant or linear) response times, independently of the global memory state. We present two Compact-fit implementations and compare them to established memory management systems, which all fail to provide predictable memory fragmentation. The experiments confirm our theoretical complexity bounds and demonstrate competitive performance. In addition, we can control the performance versus fragmentation trade-off via our concept of partial compaction. The system can be parameterized with the needed level of compaction, improving the performance while keeping memory fragmentation predictable.

All Compact-fit details can be found in the master thesis and USENIX08 paper.



Figure 1 processor instruction benchmark: Deallocation with compaction of increasing size

Figure 2 processor instruction benchmark: Deallocation with partial compaction of increasing size

Figure 3 fragmentation benchmark: The moving version of CF (partial compaction) vs. TLSF

Publications

Contact: Hannes Payer

Download