ACache Related Preemption Delay Analysis for Multi-level Non-inclusive Caches

With the rapid growth of complex hardware features, timing analysis has become an increasingly difficult problem. The key to solving this problem lies in the precise and scalable modeling of performance enhancing processor features (e.g. cache). Moreover, real-time systems are often multi-tasking and use preemptive scheduling, with fixed or dynamic priority assign-ment. For such systems, cache related preemption delay (CRPD) may increase the execution time of a task. Therefore, CRPD may affect the overall schedulability analysis. Existing works propose to bound the value of CRPD in a single-level cache. In this paper, we propose a CRPD analysis framework which can be used for a two-level, non-inclusive cache hierarchy. Besides, our proposed framework is also applicable in the presence of shared caches. We first show that CRPD analysis faces several new challenges in the presence of a multi-level, non-inclusive cache hierarchy. Our proposed framework overcomes all such challenges and we can formally prove the correctness of our framework. We have performed experiments with several subject programs, including an unmanned aerial vehicle (UAV) controller and an in-situ space debris monitoring instrument. Our experimental results suggest that we can provide sound and precise CRPD estimates using our framework. 1