On the effectiveness of cache partitioning in hard real-time systems

Sebastian Altmeyer, Roeland Douma, William Richard Elgon Lunniss, Robert Ian Davis

Research output: Contribution to journalArticlepeer-review


In hard real-time systems, cache partitioning is often suggested as a means of increasing the predictability of caches in pre-emptively scheduled systems: when a task is assigned its own cache partition, inter-task cache eviction is avoided, and timing verification is reduced to the standard worst-case execution time analysis used in non-pre-emptive systems. The downside of cache partitioning is the potential increase in execution times. In this paper, we evaluate cache partitioning for hard real-time systems in terms of overall schedulability. To this end, we examine the sensitivity of (i) task execution times and (ii) pre-emption costs to the size of the cache partition allocated and present a cache partitioning algorithm that is optimal with respect to taskset schedulability. We also devise an alternative algorithm which primarily optimises schedulability but also minimises processor utilization. We evaluate the performance of cache partitioning compared to state-of-the-art pre-emption cost analysis based on benchmark code and on a large number of synthetic tasksets with both fixed priority and EDF scheduling. This allows us to derive general conclusions about the usability of cache partitioning and identify taskset and system parameters that influence the relative effectiveness of cache partitioning. We also examine the improvement in processor utilization obtained using an alternative cache partitioning algorithm, and the tradeoff in terms of increased analysis time.
Original languageEnglish
Pages (from-to)598-643
Number of pages46
JournalReal-Time Systems
Issue number5
Publication statusE-pub ahead of print - 6 Jan 2016

Bibliographical note

© 2015 Authors. This content is made available by the publisher under a Creative Commons CC BY Licence.


  • Cache partitioning
  • Real-time scheduling
  • Timing verification
  • WCET analysis

Cite this