A page-replacement algorithm decides which page to evict from a fixed set of memory frames when a new page must be loaded. A reference not in a frame is a page fault; one already present is a hit.

FIFO

Evict the page loaded earliest, like a queue. Simple, but it ignores usage and can show Bélády's anomaly.

LRU

Evict the least recently used page. It uses recent history as a predictor and is a stack algorithm, so more frames never increase faults.

Clock

A cheap LRU approximation: frames sit on a circle with a reference bit. The hand skips and clears set bits, giving pages a second chance before eviction.

Optimal (Bélády)

Evict the page used furthest in the future. It is the provable minimum-fault policy but needs future knowledge, so it is a benchmark, not a real algorithm.

Bélády's anomaly

For FIFO with the string 1 2 3 4 1 2 5 1 2 3 4 5, going from 3 to 4 frames raises faults from 9 to 10. Load the preset, run with 3 frames, then 4, and watch the fault count rise. LRU and Optimal never do this.