Replacement Policies Under Workloads
Hit rate vs cache size — no-locality, 80-20, looping sequential, and clock. OPT wins; LRU tanks on loops.
operating-systemsvirtual-memorypage-replacementcachingclock
Workloads
| Workload | Meaning |
|---|---|
| No-locality | Each reference is a random page in the accessed set |
| 80-20 | 80% of refs → 20% hot pages; 20% of refs → 80% cold |
| Looping sequential | Touch X pages in order, loop for Y accesses |
No-locality
OPT climbs toward 100% hit rate. LRU / FIFO / RAND sit together much lower — without locality, the practical policies look the same and lose to OPT.
80-20
Locality helps. Ranking top → bottom:
- OPT
- LRU (close behind)
- FIFO / RAND (clustered below)
Looping sequential
The weird one:
- OPT — steady diagonal climb
- RAND — below OPT, still climbing
- LRU / FIFO — stuck near 0% until the cache can hold the whole loop, then jump to ~100%
They keep evicting the page you're about to need next.
80-20 + Clock
Clock: a hand walks circularly over pages (approximate LRU, cheaper).
Ranking: OPT > LRU > Clock > RND / FIFO.
Summary
Small tweaks to policies buy different tradeoffs — pick by workload, not vibes.