</>EmbeddedInterview

What are page replacement algorithms (FIFO, LRU, Clock), and what is Belady's anomaly?

MediumOperating System Concepts

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.