Improving CRPD Analysis for EDF Scheduling: Trading Speed for Precision

Giuseppe Lipari (1, 2) , Fabien Bouquillon (2, 1, 3) , Smail Niar (3)

1 CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
2 SYCOMORES - Analyse symbolique et conception orientée composants pour des systèmes embarqués temps-réel modulaires
3 LAMIH - Laboratoire d'Automatique, de Mécanique et d'Informatique industrielles et Humaines - UMR 8201

Cache Related Preemption Delay (CRPD) analysis is a methodology for bounding the cost of cache reloads due to preemptions. Many techniques have been proposed to estimate upper bounds to the CRPD for Fixed Priority (FP) and Earliest Deadline First (EDF) scheduling. Given the complexity of the problem, existing methods make simplifying assumptions to speed up the analysis, but they also introduce large amounts of pessimism. In this paper we present two contributions for reducing the pessimism in the CRPD analysis of real-time systems that use setassociative cache memories. First, we present a new way to compute a bound on the number of preemptions on a task under EDF scheduling. Second, we propose a novel algorithm that trades off speed for precision in state-of-the-art analysis in the literature. We show improvements in the schedulability ratio on classical benchmarks in comparison with the state-of-the-art.

Mots clés: CRPD; Cache analysis; Real-Time scheduling analysis

Domaines: Systèmes embarqués; Système d'exploitation [cs.OS]

Giuseppe Lipari, Fabien Bouquillon, Smail Niar. Improving CRPD Analysis for EDF Scheduling: Trading Speed for Precision. The 37th ACM/SIGAPP Symposium On Applied Computing, Apr 2022, Brno, Czech Republic. ⟨10.1145/3477314.3507027⟩. ⟨hal-03531143⟩