Accurate Estimation of Cache-Related Preemption Delay

Multitasked real-time systems often employ caches to boost performance. However the unpredictable dynamic behav-ior of caches makes schedulability analysis of such systems difficult. In particular, the effect of caches needs to be con-sidered for estimating the inter-task interference. As the memory blocks of different tasks can map to the same cache blocks, preemption of a task may introduce additional cache misses. The time penalty introduced by these misses is called the Cache-Related Preemption Delay (CRPD). In this paper, we provide a program path analysis tech-nique to estimate CRPD. Our technique performs path anal-ysis of both the preempted and the preempting tasks. Fur-thermore, we improve the accuracy of the analysis by esti-mating the possible states of the entire cache at each possible preemption point rather than estimating the states of each cache block independently. To avoid incurring high space requirements, the cache states can be maintained symboli-cally as a Binary Decision Diagram. Experimental results indicate that we obtain tight CRPD estimates for realistic benchmarks