@INPROCEEDINGS{Burguiere09,
  author = {Claire Burgui\`ere and Jan Reineke and Sebastian Altmeyer},
  title = {Cache-Related Preemption Delay Computation for Set-Associative 
Caches---Pitfalls and Solutions},
  booktitle = {Proceedings of 9th International Workshop on Worst-Case Execution Time ({WCET}) Analysis},
  year = {2009},
  month = {June},
  url = 
{http://drops.dagstuhl.de/opus/volltexte/2009/2285/pdf/Burguiere.2285.pdf},
  subproject={R2},
  access={restricted},
  bibtex={CRPD_for_set_ass_caches_pitfals_and_solutions.bib},
  pdf={CRPD_for_set_ass_caches_pitfals_and_solutions.pdf},
  abstract={In preemptive real-time systems, scheduling analyses need---in addition to the 
worst-case execution time---the context-switch cost. In case of preemption, 
the preempted and the preempting task may interfere on the cache memory.
These interferences lead to additional reloads in the preempted task. The 
delay due to these reloads is referred to as the cache-related preemption
delay (CRPD). The CRPD constitutes a large part of the context-switch cost. 
In this article, we focus on the computation of upper bounds on the CRPD based
on the concepts of useful cache blocks (UCBs) and evicting cache blocks 
(ECBs).  We explain how these concepts can be used to bound the CRPD in case 
of direct-mapped caches.  Then we consider set-associative caches with LRU, 
FIFO, and PLRU replacement. We show potential pitfalls when using UCBs and 
ECBs to bound the CRPD in case of LRU and demonstrate that neither UCBs nor 
ECBs can be used to bound the CRPD in case of FIFO and PLRU. Finally, we 
sketch a new approach to circumvent these limitations by using the concept of 
relative competitiveness.},
}