@article{DBLP:journals/rts/ReinekeGBW07,
  author    = {Jan Reineke and
               Daniel Grund and
               Christoph Berg and
               Reinhard Wilhelm},
  title     = {Timing predictability of cache replacement policies},
  journal   = {Real-Time Systems},
  volume    = {37},
  number    = {2},
  year      = {2007},
  pages     = {99-122},
  pdf       = {2007/ReinekeGBW07.pdf},
  bibtex    = {2007/ReinekeGBW07.bib},
  ee        = {http://dx.doi.org/10.1007/s11241-007-9032-3},
  springer  = {http://www.springerlink.com/content/l128713825873h30/},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  abstract = {Abstract Hard real-time systems must obey strict timing constraints. Therefore, one
needs to derive guarantees on the worst-case execution times of a system's tasks. In
this context, predictable behavior of system components is crucial for the derivation
of tight and thus useful bounds. This paper presents results about the predictabil-
ity of common cache replacement policies. To this end, we introduce three metrics,
evict, fill, and mls that capture aspects of cache-state predictability. A thorough analy-
sis of the LRU, FIFO, MRU, and PLRU policies yields the respective values under
these metrics. To the best of our knowledge, this work presents the first quantitative,
analytical results for the predictability of replacement policies. Our results support
empirical evidence in static cache analysis.}
}