Notes › Operating Systems
Page Replacement Algorithms
With virtual memory, a process's pages don't all have to be in RAM (Memory Management, Paging and Virtual Memory). When a needed page is missing, a page fault happens: the OS loads it from disk. If RAM (the set of frames) is full, it must evict a page — the page replacement algorithm decides which one.
Goal: as few page faults as possible (disk is ~100,000× slower than RAM).
We use the reference string 7 0 1 2 0 3 0 4 2 3 0 3 2 with 3 frames for every example.
FIFO — evict the oldest page loaded
| Ref | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| F1 | 7 | 7 | 7 | 2 | 2 | 2 | 2 | 4 | 4 | 4 | 0 | 0 | 0 |
| F2 | 0 | 0 | 0 | 0 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | |
| F3 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 3 | 3 | 3 | 3 | ||
| Fault | ✱ | ✱ | ✱ | ✱ | ✱ | ✱ | ✱ | ✱ | ✱ | ✱ | |||
| 10 page faults. Simple, but it can evict a page that is used all the time. |
Belady's anomaly
With FIFO, adding more frames can increase page faults for some reference strings (classic example: 1 2 3 4 1 2 5 1 2 3 4 5 → 9 faults with 3 frames, 10 with 4). LRU and Optimal never show this (they are stack algorithms).
Optimal (OPT / MIN) — evict the page used farthest in the future
| Ref | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| F1 | 7 | 7 | 7 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
| F2 | 0 | 0 | 0 | 0 | 0 | 0 | 4 | 4 | 4 | 0 | 0 | 0 | |
| F3 | 1 | 1 | 1 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | ||
| Fault | ✱ | ✱ | ✱ | ✱ | ✱ | ✱ | ✱ | ||||||
| 7 page faults — the minimum possible. It needs to know the future, so it is not implementable; it is used as a benchmark. |
LRU — evict the least recently used page
| Ref | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| F1 | 7 | 7 | 7 | 2 | 2 | 2 | 2 | 4 | 4 | 4 | 0 | 0 | 0 |
| F2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 3 | 3 | 3 | 3 | |
| F3 | 1 | 1 | 1 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | ||
| Fault | ✱ | ✱ | ✱ | ✱ | ✱ | ✱ | ✱ | ✱ | ✱ | ||||
| 9 page faults. Uses the past to guess the future — usually close to optimal. |
Implementing exact LRU needs a timestamp or a stack on every memory access — too costly in hardware, so OSes use approximations:
- Clock / second chance: a circular list with a reference bit; skip (and clear) pages with bit 1, evict the first with bit 0.
- LFU / MFU: by usage counts (rarely used alone).
(The same LRU idea is the famous LRU cache coding question: hash map + doubly linked list, O(1) get and put.)
Comparison
| Algorithm | Faults (example) | Implementable | Belady's anomaly |
|---|---|---|---|
| FIFO | 10 | ✅ easy | ✅ possible |
| Optimal | 7 | ❌ | ❌ |
| LRU | 9 | ✅ costly (approximated) | ❌ |
Thrashing
When processes don't have enough frames for the pages they actively use, the CPU spends most of its time handling page faults instead of real work. CPU utilisation drops as more processes are added.
Fixes: the working-set model (give each process the frames for the pages it used in the last Δ references), page-fault-frequency control, reduce the number of processes, add RAM.
Formula
Effective access time = (1 − p) × memory access time + p × page-fault service time, where p = page-fault rate. Even p = 0.001 slows memory down massively because a fault costs milliseconds.
Interview one-liners
- Page fault = the page is not in RAM; it is not an error.
- Optimal gives the fewest faults but needs the future.
- FIFO suffers from Belady's anomaly; LRU doesn't.
- Thrashing = too much paging, too little work.