PI-1568: Performance analysis of static cache locking in multitasking
hard real-time systems
Isabelle Puaut, Alexis Arnaud, David Decotigny
http://www.irisa.fr/bibli/publi/pi/2003/1568/1568.html
31 pages - octobre 2003

Abstract
Cache memories raise predictability issues in hard real-time systems
because of their dynamic and adaptive behavior, and thus need special
attention to be used in hard real-time systems. While a lot of progress
has been achieved to statically predict worst-case execution times
(WCETs) of tasks on architectures with caches, cache-aware WCET analysis
techniques may not always be applicable or may be too pessimistic. An
alternative approach allowing to use caches in real-time systems is to
lock their contents such that memory access times and cache-related
preemption times are predictable. This paper describes a simple and easy
to implement method for static locking of instruction and data caches,
ensuring by construction that cache access times are predictable. The
method can be applied to any cache provided that its size and
associativity degree are known; no knowledge of its replacement policy
is required. The method can be applied even if the tasks contain
statically unknown memory references. Furthermore, it requires neither
modifications of the task codes nor compiler support. Experimental
results show that the use of locked caches enhances the system
performance compared to a system without a cache. However, such a scheme
may result in performance loss as compared to a system with a dynamic
(unlocked) cache. We then identify the threshold under which this
performance loss is acceptable and above which more efficient but more
complex locking schemes have to be devised.

Résumé
Les mémoires caches sont sources de problèmes de déterminisme dans les
systèmes temps-réel strict, du fait de leur comportement dynamique et
adaptatif. Ainsi, leur utilisation dans les systèmes temps-réel strict
doit faire l'objet d'une attention particulière. Bien que de gros
progrès aient été réalisés dans les dix dernières années pour analyser
statiquement les pires temps d'exécution (WCET, pour Worst-Case
Execution Times) de logiciels pour des processeurs dotés de mémoires
caches, de telles méthodes d'analyse ne sont pas toujours applicables ou
peuvent être excessivement pessimistes. Une approche alternative pour
utiliser des mémoires caches dans les systèmes temps-réel strict est de
verrouiller (geler) leur contenu, de telle sorte que les temps d'accès
mémoire et les délais de préemption causés par les caches soient
déterministes. Cet article décrit une méthode simple et facile à mettre
en oeuvre de verrouillage statique de caches, rendant par construction
les latences d'accès à la mémoire complètement prévisibles. La méthode
peut être appliquée à tout cache dont la taille et le degré
d'associativité sont connus (aucune connaissance de la politique de
remplacement de cache n'est nécessaire). La méthode proposée peut être
utilisée même sur des tâches contenant des accès mémoire inconnus
statiquement. De plus, elle ne requiert pas de modification du
compilateur ou du code des tâches. Les résultats expérimentaux présentés
dans l'article montrent que l'utilisation de caches verrouillés
statiquement améliore les performances du système en comparaison avec un
système dans lequel aucun cache n'est employé. Toutefois, les
performances sont moins bonnes qu'en utilisant un cache dynamique (non
verrouillé). Nous identifions alors un seuil au dessous duquel la baisse
de performance est acceptable, et au dessus duquel des méthodes de
verrouillage plus efficaces (mais aussi plus complexes) doivent être
conçues.

Keywords: Hard real-time systems, cache memories, cache locking,
worst-case execution times, performance evaluation

Mots clefs: Systèmes temps-réel strict, mémoires cache, verrouillage de
caches, pires temps d'exécution, évaluation de performances