Cache-related preemption delay via useful cache blocks: Survey and redefinition

Tasks in an embedded system are scheduled either preemptively or non-preemptively. In case of preemptive scheduling, interferences on the cache of the preempted and preempting task may extend the execution times. The corresponding delay is referred to as cache-related preemption delay (CRPD). Lee et al. [6] presented a CRPD analysis using the concept of useful cache block (UCB): a cache block is useful if it may be in the cache before a program point and may be reused after this point. If a preemption occurs at that point, the number of additional cache misses is bounded by the number of UCBs. An upper bound on the CRPD of the whole task is thus given by the program point with the largest set of UCBs. In this article, we provide a survey of the state of the art techniques to bound the CRPD, based on, but not limited to UCBs. Based on this survey we present an alternative definition of UCBs to improve the CRPD bounds substantially.