--------------------------------------------------------------------
A Compacting Real-Time Memory Management System
--------------------------------------------------------------------
by Silviu S. Craciunas, Christoph Kirsch, Hannes Payer, 
   Ana Sokolova, Horst Stadler, and Robert Staudinger
-------------------------------------------------------------------- 

Abstract:
--------------------------------------------------------------------

We propose a compacting real-time memory management system for
allocating, deallocating, and accessing memory objects, called
Compact-fit.  The system keeps the memory always compact and
provides constant response times for allocation and access, and
linear response time (in the size of the object) for deallocation
when compaction occurs. Moreover, the system provides fully
predictable memory, in the sense of fragmentation.  In short, it is
a real real-time memory management system.  We present two
implementations of the Compact-fit system and compare them to the
established memory management systems, which all fail to satisfy the
memory predictability requirement.  The experiments confirm our
theoretical complexity bounds and demonstrate competitive
performance.  In addition, we can control the performance vs.
fragmentation trade-off, via our concept of partial compaction. The
system can be parameterized with the needed level of compaction,
leading to constant response times for deallocation as well, while
keeping memory fragmentation bounded and fully predictable.

---------------------------------------------------------------------