CAMA---A Predictable Cache-Aware Memory Allocator

Joerg Herter and Peter Backes
Saarland University


General purpose dynamic storage allocation (DSA) 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. Predictable cache behavior and still reasonable memory fragmentation is a prerequisite for a subsequent timing analysis to derive tight bounds on a program's execution time. This paper proposes a novel DSA 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. This is necessary to enable a subsequent precise cache analysis.