Tightening the bounds on feasible preemption points

Caches have become invaluable for higher-end architectures to hide, in part, the increasing gap between processor speed and memory access times. While the effect of caches on timing predictability of single real-time tasks has been the focus of much research, bounding the overhead of cache warm-ups after preemptions remains a challenging problem, particularly for data caches. This paper makes multiple contributions. First, we bound the penalty of cache interference for real-time tasks by providing accurate predictions of the data cache behavior across preemptions, including instruction cache and pipeline effects. For every task, we derive data cache reference patterns for all scalar and non-scalar references. We show that, when considering cache preemption, the critical instance does not occur upon simultaneous release of all tasks. Second, we develop analysis methods to calculate tight upper bounds on the number of possible preemption points for each job of a task and consider the worst-case placement of these preemption points. Partial timing of a job is performed up to a preemption point using the cache reference patterns. The effects of cache interference are then analyzed using a set-theoretic approach, which identifies the number and location of additional misses due to preemption. A feedback mechanism provides the means to interact with the timing analyzer, which subsequently times another interval of a job bounded by the next preemption. Significant improvements in tightening bounds of up to an order of magnitude over two prior methods and up to half a magnitude over a third prior method are obtained by experiments for (a) the number of preemptions, (b) the WCET and (c) the response time of a task. Overall, this work contributes (1) by formulating a new critical instance under cache preemption, (2) by proving a new analysis method to derive bounds on the number of preemptions and (3) by determining actual preemption points when calculating the preemption delay under consideration of data caches. 1