What are page replacement algorithms (FIFO, LRU, Clock), and what is Belady's anomaly?
Short answer: When physical memory is full and a new page is needed, the OS must choose a victim page to evict. FIFO evicts the oldest page; Optimal evicts the page used furthest in the future (impossible in practice, used as a benchmark); LRU evicts the page unused for the longest time; Clock (second chance) approximates LRU cheaply with a reference bit. Belady's anomaly is FIFO's surprising behaviour of sometimes causing more faults with more frames.
Worked example: reference string 7 0 1 2 0 3 0 4, 3 frames.
| Algorithm | Frames after each reference (miss = *) | Faults |
|---|---|---|
| FIFO | 7* 70* 701* 201* 201 231* 230* 430* | 7 |
| LRU | 7* 70* 701* 201* 201 203* 203 403* | 6 |
| Optimal | 7* 70* 701* 201* 201 203* 203 403* | 6 |
At reference 3, FIFO evicts 0 (the oldest) even though 0 is used next; LRU evicts 1, which was least recently used.
Clock algorithm (what real kernels approximate): pages are arranged in a circle with a hand. Each page has a hardware "accessed" bit set on use. To evict, look at the page under the hand: if its bit is 1, clear it and move on (second chance); if it is 0, evict it. Pages in active use keep getting their bit set and survive.
Linux: uses active and inactive LRU lists (and the newer multi-generational LRU, MGLRU), driven by the accessed bits in page table entries. Clean file pages are cheap to drop (re-read from the file later); dirty or anonymous pages must be written to the file or swap first.
Belady's anomaly: with FIFO and the string 1 2 3 4 1 2 5 1 2 3 4 5, 3 frames give 9 faults but 4 frames give 10. LRU and Optimal are "stack algorithms" and never show this anomaly.
Related: thrashing happens when the working set does not fit no matter which algorithm you use.