Cache Replacement: FIF vs LRU vs FIFO

Bélády's algorithm (FIF = Furthest-In-Future) is optimal. LRU tracks it well with temporal locality. FIFO can be much worse.

Cache size (k): 4 Stream:

Press "Step" or "Auto" to begin simulation.

Request Stream

FIF

Furthest-In-Future: evict item whose next use is furthest away (Bélády's optimal)

—

0 misses

LRU

Least Recently Used: evict item that was used longest ago

—

0 misses

FIFO

First-In-First-Out: evict item that has been cached the longest

—

0 misses

P1 Verify: Stream [c,d,e,f,a,b] with initial cache [a,b,c,d], k=4 → FIF: 2 misses, FIFO: 4 misses (use preset "P1 Verify").
P2 Adversarial: Cycle of k+1 items → LRU misses every request; FIF achieves minimum (use "Adversarial for LRU").