Page Replacement
When memory is full and a new page must come in, which page do you throw out? Eight algorithms, from the simple FIFO baseline through the unbeatable Optimal to the LRU approximations real operating systems actually ship.
What is Page Replacement?
The 60-second primer
A page replacement algorithm decides which page to throw out of memory when you need room for a new one. Programs think they have a huge, continuous memory, but physical RAM is much smaller. The operating system keeps the pages a program is actually using in RAM and leaves the rest on disk. When a program touches a page that isn't in RAM — a page fault — the OS must load it. If every RAM frame is already full, something has to go. Choosing what goes is the whole problem.
The choice matters because the page you evict might be needed again in a moment. Guess wrong and you fault it right back in, paying for a slow disk read you could have avoided. Guess well and the pages still in memory are the ones the program keeps using. Every algorithm here is a different rule for making that guess.
The same idea appears in CPU caches, database buffer pools, CDN edge caches, and web caches — anywhere a small fast store fronts a big slow one. The names and units change, but the question never does: the box is full and something new wants in; which old thing do you drop?
Where this shows up
- Virtual memory — the original setting. The OS pages memory in and out of RAM; a bad policy means thrashing, where the machine spends all its time shuffling pages instead of running your program.
- Database buffer pools — PostgreSQL, MySQL/InnoDB, and Oracle all keep hot disk pages in RAM and need a replacement policy (often a Clock or LRU variant) to decide what to drop.
- CPU caches — L1/L2/L3 caches evict cache lines with hardware approximations of LRU; the cost of a miss is a slower memory level, not a disk.
- Web & CDN caches — Varnish, NGINX, and CDN edge nodes evict objects under memory pressure; LRU and LFU variants are everywhere.
- Any tiered storage — the moment a fast tier fills, you need a rule for what falls back to the slow tier. The algorithms are the same.
The metric that matters
Almost every policy is judged by one number: the page-fault rate (equivalently, the hit ratio) for a given amount of memory. Fewer faults means less time waiting on the slow tier. The prototypes here report exactly this so you can race the algorithms against the same reference string.
Side-by-side
How they compare
The same concepts, on the same axes. Use this as a map; the individual pages are the territory.
| Algorithm | Core rule | Fault rate | Cost / metadata | Best known for |
|---|---|---|---|---|
01FIFO | Evict the oldest-loaded page | Poor — ignores usage | A queue; almost nothing | The simplest baseline (and Belady's anomaly) |
02Optimal | Evict the page used furthest in the future | Best possible (lower bound) | Needs the future — unimplementable | The yardstick every real policy is measured against |
03LRU | Evict the least-recently-used page | Excellent in practice | Recency order; expensive to track exactly | The gold-standard practical policy |
04Second Chance | FIFO, but spare a page whose reference bit is set | Better than FIFO | FIFO queue + 1 bit per page | A cheap, easy upgrade over FIFO |
05Clock | Second Chance as a circular buffer with a hand | Same as Second Chance, far cheaper | Ring + 1 bit per page; O(1) work | The LRU approximation real kernels actually ship |
06NRU | Pick from the lowest (R, M) class | Coarse but cheap | 2 bits per page + periodic tick | Respecting dirty pages with minimal bookkeeping |
07Aging | Shift-register counters approximate recency | Very close to LRU | An n-bit counter per page | Software LRU approximation in fixed memory |
08LFU | Evict the least-frequently-used page | Great for stable hot sets, bad for shifting ones | A counter per page | Workloads with a steady, popular core |
- Core rule
- Evict the oldest-loaded page
- Fault rate
- Poor — ignores usage
- Cost / metadata
A queue; almost nothing- Best known for
- The simplest baseline (and Belady's anomaly)
- Core rule
- Evict the page used furthest in the future
- Fault rate
- Best possible (lower bound)
- Cost / metadata
Needs the future — unimplementable- Best known for
- The yardstick every real policy is measured against
- Core rule
- Evict the least-recently-used page
- Fault rate
- Excellent in practice
- Cost / metadata
Recency order; expensive to track exactly- Best known for
- The gold-standard practical policy
- Core rule
- FIFO, but spare a page whose reference bit is set
- Fault rate
- Better than FIFO
- Cost / metadata
FIFO queue + 1 bit per page- Best known for
- A cheap, easy upgrade over FIFO
- Core rule
- Second Chance as a circular buffer with a hand
- Fault rate
- Same as Second Chance, far cheaper
- Cost / metadata
Ring + 1 bit per page; O(1) work- Best known for
- The LRU approximation real kernels actually ship
- Core rule
- Pick from the lowest (R, M) class
- Fault rate
- Coarse but cheap
- Cost / metadata
2 bits per page + periodic tick- Best known for
- Respecting dirty pages with minimal bookkeeping
- Core rule
- Shift-register counters approximate recency
- Fault rate
- Very close to LRU
- Cost / metadata
An n-bit counter per page- Best known for
- Software LRU approximation in fixed memory
- Core rule
- Evict the least-frequently-used page
- Fault rate
- Great for stable hot sets, bad for shifting ones
- Cost / metadata
A counter per page- Best known for
- Workloads with a steady, popular core
Decision guide
Which one should you use?
A practical tour of when each algorithm wins.
How to pick
- Just measuring the best you could do → Optimal. It can't be built (it needs the future), but it tells you how close any real policy gets.
- You want the best realistic quality → LRU. Recency is a strong signal. Exact LRU is costly, which is why the next few exist.
- You need LRU's quality but cheaply → Clock (or Aging in software). Clock is what most operating systems and database buffer pools actually run.
- You're starting from FIFO and want an easy win → Second Chance. One reference bit turns FIFO into something respectable; Clock is the same idea done efficiently.
- Eviction cost depends on whether a page is dirty → NRU. It prefers evicting clean pages so it doesn't have to write them back to disk.
- Your hot set is stable and popularity is the real signal → LFU. But watch for stale, once-popular pages that never leave — frequency without aging gets stuck in the past.
It's one idea, refined
Start at FIFO (age only). Optimal shows the ceiling. LRU uses recency to get near it. Second Chance and Clock approximate LRU with a single bit; NRU adds the dirty bit; Aging adds more bits for finer recency; LFU swaps recency for frequency. Learn them in that order and each one is just the previous with one problem fixed.
Concepts in this track
8 concepts, in order
Each links to a concept page with its own explanation, prototype, and quiz.
FIFO
Evict the oldest-loaded page. The simplest baseline — and the famous home of Belady's anomaly, where more memory can mean more faults.
Optimal (Belady's)
Evict the page used furthest in the future. Unbeatable but unimplementable — it needs to see the future, so it's the yardstick every real policy is measured against.
LRU
Evict the least-recently-used page. Bet the recent past predicts the near future — the practical gold standard that often lands close to Optimal.
Second Chance
FIFO plus one reference bit: spare a page that was used recently by rotating it to the back instead of evicting it. The cheap upgrade over FIFO.
Clock
Second Chance done efficiently: pages stay in a ring and a hand sweeps for a victim. The LRU approximation operating systems and buffer pools really ship.
NRU
Sort pages into four classes by referenced and dirty bits, then evict from the cheapest class — folding writeback cost into the decision.
Aging
Give each page a shift-register counter that ages old use away one bit at a time. Software's close, cheap imitation of LRU.
LFU
Evict the least-frequently-used page. Popularity over recency — great for a stable hot set, but stale-but-popular pages cling forever without decay.
Related tracks
If this one clicks, try these next.
Cache Write Policies
Three ways to handle a write when you have a cache in front of the store. Each policy is a different bet about durability, throughput, and how stale your data is allowed to get.
Cache Eviction
When the cache fills up, something has to go — and which one you pick decides your hit rate. Ten classic policies, side-by-side.
Garbage Collection
How a runtime reclaims memory you stopped using — without you ever calling free(). Eight algorithms, from the counter on every object to the collectors that run alongside your program.