Info & Theory
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 that is 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.
Frequently asked questions
What is a page-replacement algorithm?
A page-replacement algorithm decides which page to evict from physical memory frames when a new page must be loaded and all frames are full. Good choices minimise page faults.
What is a page fault?
A page fault occurs when a referenced page is not currently in a memory frame, so it must be fetched from disk. The fault count is the primary metric for comparing page-replacement policies.
How does FIFO page replacement work?
FIFO (First-In, First-Out) evicts the page that has been in memory the longest, regardless of how often it is used. It is simple but can perform poorly and famously exhibits Bélády's anomaly.
How does LRU page replacement work?
LRU (Least Recently Used) evicts the page that has not been accessed for the longest time, approximating the idea that recently used pages will be used again. It never suffers Bélády's anomaly.
What is the Optimal (Bélády) algorithm?
The Optimal algorithm evicts the page that will not be used for the longest time in the future. It gives the provably minimum number of faults but is unimplementable in practice because it needs to know future references.
What is the Clock algorithm?
Clock (the second-chance algorithm) arranges frames in a circle with a reference bit per page. On a fault the hand advances, clearing reference bits and giving recently used pages a second chance, approximating LRU at lower cost.
What is Bélády's anomaly?
Bélády's anomaly is the surprising case where increasing the number of frames causes FIFO to produce more page faults, not fewer. It violates the intuitive expectation that more memory is always better.
Which algorithms avoid Bélády's anomaly?
Stack algorithms such as LRU and Optimal never suffer Bélády's anomaly, because the set of pages held with n frames is always a subset of the set held with n+1 frames. FIFO and Clock are not stack algorithms.
What is the hit ratio?
The hit ratio is the fraction of references that are already in memory (hits) out of all references. It equals one minus the fault ratio and is a convenient way to compare policy effectiveness.
What is a reference string?
A reference string is the sequence of page numbers a process accesses over time. Page-replacement algorithms are evaluated by running them against the same reference string and counting faults.