Analysis of Preemptively Scheduled Hard Real-time Systems
A static timing analysis derives upper bounds on the execution time of tasks, a scheduling analysis uses these bounds and checks if each task meets its timing constraints.
In preemptively scheduled systems with caches, this interface between timing analysis and scheduling analysis must be considered outdated.
On a context switch, a preempting task may evict cached data of a preempted task that need to be reloaded again after preemption.
The additional execution time due to these reloads, called cache-related preemption delay (CRPD), may substantially prolong a task's execution time and strongly influence the system's performance.
In this thesis, we present a formal definition of the cache-related preemption delay and determine the applicability and the limitations of a separate CRPD computation.
To bound the CRPD based on the analysis of the preempted task, we introduce the concept of definitely cached useful cache blocks.
This new concept eliminates substantial pessimism with respect to former analyses by considering the over-approximation of a preceding timing analysis.
We consider the impact of the preempting task to further refine the CRPD bounds.
To this end, we present the notion of resilience.
The resilience of a cache block is a measure for the amount of disturbance of a preempting task a cache block of the preempted task may survive.
Based on these CRPD bounds, we show how to correctly account for the CRPD in the schedulability analysis for fixed-priority preemptive systems and present new CRPD-aware response time analyses: ECB-Union and Multiset approaches.