FIFO, LRU, and Optimal: Three Different Bets on the Future
When physical memory frames are full and a new page needs to be loaded, an operating system must evict something — page replacement algorithms are really different strategies for guessing which page is safest to remove. FIFO evicts whichever page has been in memory longest, regardless of how recently or often it's been used — simple to implement, but can evict a heavily-used page purely because it happened to load first.
LRU (Least Recently Used) evicts the page that hasn't been accessed in the longest time, on the reasonable assumption that recent access predicts near-future access — this generally performs better than FIFO but requires tracking access recency, which has real implementation overhead. Optimal evicts whichever page won't be needed again for the longest time in the future — provably the best possible strategy, but requires knowing the future reference sequence in advance, making it purely a theoretical benchmark other algorithms are measured against, not something implementable in a real running system.
Comparing hit/miss counts across all three on the identical reference string is exactly how operating systems courses illustrate why LRU's added complexity is usually worth it over FIFO's simplicity.
Worked example
The classic reference string 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 with 3 frames gives:
- FIFO: 15 page faults and 5 hits (25% hit ratio)
- LRU: 12 page faults and 8 hits (40% hit ratio)
- Optimal: 9 page faults and 11 hits (55% hit ratio)
Optimal is the lower bound that no real algorithm can beat, and LRU lands between it and FIFO.
Belady's anomaly
With the reference string 1 2 3 4 1 2 5 1 2 3 4 5, FIFO makes 9 faults with 3 frames but 10 faults with 4 frames: more memory, more faults. LRU and Optimal are stack algorithms, so adding frames never increases their faults (LRU goes from 10 faults to 8 on the same string). Load the Belady example to see it in the faults-vs-frames row.