@INPROCEEDINGS{Altmeyer09,
  author = {Sebastian Altmeyer and Claire Burgui\`ere},
  title = {A New Notion of Useful Cache Block to Improve the Bounds of Cache-
Related Preemption Delay},
  booktitle = {Proceedings of the 21st Euromicro Conference on Real-Time 
Systems (ECRTS '09)},
  year = {2009},
  pages = {109--118},
  month = {July},
  publisher = {IEEE Computer Society},
  doi = {10.1109/ECRTS.2009.21},
  isbn = {978-0-7695-3724-5},
  subproject={R2},
  access={restricted},
  bibtex={New_Notion_of_Useful_Cache_Blocks.bib},
  pdf={New_Notion_of_Useful_Cache_Blocks.pdf},
  abstract={In preemptive real-time systems, scheduling analyses are based on the worst-
case response time of tasks. This response time includes worst-case execution 
time (WCET) and context switch costs. In case of preemption, cache memories 
may suffer interferences between memory accesses of the preempted and of the 
preempting task. These interferences lead to some additional reloads that are 
referred to as cache-related preemption delay (CRPD). This CRPD constitutes a 
large part of the context switch costs. In this article, we focus on the 
computation of upper bounds on the CRPD using the concept of useful cache 
blocks (UCB). These are memory blocks that may be in cache before a program 
point and may be reused after it. When a preemption occurs at that point the 
number of additional cache-misses is bounded by the number of useful cache 
blocks. We tighten the CRPD bound by using a modified notion of UCB: Only 
cache blocks that are definitely cached are considered useful by our approach. 
As we show in this paper, the computed CRPD based on our notion, when used in 
combination with the bound on the WCET, delivers a safe bound on the execution 
time in case of preemption. Furthermore the modified definition simplifies the 
UCB computation for set-associative LRU and data caches. Experimental results 
show that our approach provides up to 90\% tighter CRPD bounds.},
}