CAMA: A Predictable Cache-Aware Memory Allocator
Jörg Herter, Peter Backes, Florian Haupenthal, Jan Reineke · 2011
General-purpose dynamic memory allocation algorithms strive for small memory fragmentation and good average-case response times. Hard real-time settings, in contrast, place different demands on dynamic memory allocators: worst-case response times are more important than average-case response times. Furthermore, predictable cache behavior is a prerequisite for timing analysis to derive tight bounds on a program's execution time. This paper proposes a novel algorithm that meets these demands. It guarantees constant response times, does not cause unpredictable cache pollution, and allocations are cache-set directed, i.e., allocated memory is guaranteed to be mapped to a given cache set. The latter two are necessary to enable a subsequent precise static cache analysis.