Which page-replacement algorithms should you know, and what is Belady's anomaly?
Interview preparation resource from Gate Smashers.
Know OPT (MIN), FIFO, LRU, Clock/Second-Chance, NRU, aging, and frequency-based policies such as LFU; Random is also a useful baseline. Be able to explain the trade-off between fault behavior and implementation cost. Belady’s anomaly is the case where increasing the number of page frames increases the number of page faults. FIFO is the classic example. It cannot occur in stack algorithms such as OPT and LRU, because their resident sets satisfy the inclusion property as frame count increases.
Core algorithms to know
For an interview, start with the ideal policy, the basic policies, and practical approximations. OPT provides the theoretical minimum number of faults but is not implementable in a normal online system because it requires knowledge of future references.
bullets
- OPT (MIN): Evicts the page whose next use is farthest in the future. It is used as a theoretical benchmark.
- FIFO: Evicts the page that has been resident the longest. It is simple, but arrival order does not necessarily reflect future usefulness.
- LRU: Evicts the page that has not been referenced for the longest time. It exploits temporal locality, but exact LRU can be costly to maintain.
- Clock / Second-Chance: Uses a circular scan and reference bits to approximate recency with lower overhead than exact LRU.
- NRU and aging: Use reference information, and often modification information or aging counters, to make inexpensive approximations to recency.
- LFU, MFU, and Random: Frequency-based policies use reference counts, while Random chooses a victim without recency or frequency information. Frequency policies must account for old history becoming stale.
Stack algorithms and the inclusion property
A stack algorithm has the inclusion property: for a given reference string, the pages resident with m frames are always a subset of those resident with m+1 frames. Therefore, adding a frame cannot increase its number of page faults.
OPT and LRU are stack algorithms. FIFO is not. This distinction is important because stack algorithms cannot exhibit Belady’s anomaly; a non-stack algorithm can, although it does not necessarily do so for every reference string.
Belady’s anomaly
Belady’s anomaly is the counterintuitive result that giving a page-replacement policy more frames can produce more page faults. It is most commonly demonstrated with FIFO.
For the reference string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5, FIFO produces 9 page faults with 3 frames and 10 page faults with 4 frames. The additional frame changes FIFO’s eviction order in an unfavorable way.
The key lesson is that more memory does not automatically imply fewer faults for every replacement policy. It does imply no increase in faults for stack algorithms such as OPT and LRU.
Practical perspective
Real operating systems generally use policies that approximate recency rather than exact OPT or exact LRU. The appropriate choice depends on available hardware reference information, implementation overhead, and workload locality.
Working-set concepts are also important to know: they describe a process’s recent locality and can guide resident-set and replacement decisions, rather than being a single replacement algorithm in the same sense as FIFO or LRU.