Hard real-time systems must obey strict timing constraints.
Therefore, one needs to derive guarantees on the worst-case execution
times of the systems’ tasks. In this context, predictable behavior of  
system components is crucial for the derivation of tight and thus useful
bounds.
We present results about the predictability of common cache
replacement policies. To this end, we introduce two metrics that capture
aspects of cache-state predictability. A thorough analysis 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.
They support empirical evidence in static cache analysis.