Scope-Aware Useful Cache Block Calculation for Cache-Related Preemption Delay Analysis with Set-Associative Data Caches

Timing analysis of real-time systems must consider cache-related preemption delay (CRPD) costs when preemptive scheduling is used. While most previous work on CRPD analysis only considers instruction caches, the CRPD incurred on data caches is actually more significant. The state-of-the-art CRPD analysis methods are based on useful cache block (UCB) calculation. Unfortunately, as shown in this paper, directly extending the existing UCB calculation techniques from instruction caches to data caches will lead to both unsoundness and significant imprecision. To solve these problems, we develop a new UCB calculation technique for data caches, which redefines the analysis unit (to address the unsoundness in the existing method) and precisely captures the dynamic cache access behavior by taking the temporal scopes of memory blocks into consideration. Experimental results show that our new technique yields substantially tighter CRPD estimations comparing with the state-of-the-art.