LRU vs LFU: How Caches Decide What to Evict

Subtitle: Recency and frequency protect different reuse patterns.

Section 1 - Two signals:

LRU: every hit moves an item to newest. LRU: evict the least recent item. LFU: count hits for every item. LFU: evict the smallest count. LFU ties need a named second rule.

Section 2 - Capacity-three trace:

Admit A, B, C; then hit A; admit D. LRU order makes B the victim. LFU counts: A=2, B=1, C=1. B and C tie; LFU alone cannot choose. The tie-breaker is part of the policy.

Section 3 - Where each policy breaks:

A one-pass scan can flush useful LRU data. Old popularity can trap stale LFU data. Age or decay counts when demand shifts. If C=3 and A=E=5, C must be evicted. At C=5, A/C/E need a tie-breaker.

Section 4 - Falsify the universal winner:

Replay one real trace at equal capacity. Count misses under both policies. Test a cycle, one-pass scan, demand shift. Change tie and aging rules explicitly. Reuse shape decides the hit rate.