Introduction
When a process references a page that is not currently in a physical frame, the OS raises a page fault. If free frames exist, the OS simply loads the page. But once all frames are occupied, the OS must choose a victim page to evict before it can bring in the new one. The strategy used to pick that victim is a page replacement algorithm. A good algorithm minimizes the number of page faults over the lifetime of a program, which directly affects performance because disk I/O is orders of magnitude slower than memory access.
Cricket analogy: When a stadium's practice nets are all occupied and a new team needs one, ground staff must choose which team's session to end early (victim selection) — a good policy minimizes disruptions across the season, since re-booking a session (disk I/O) costs far more time than continuing an existing one.
Algorithm Explanation
FIFO (First-In-First-Out) evicts the page that has been resident the longest, regardless of how often it is used; it is implemented with a simple queue but can behave poorly because an old, frequently used page may still get evicted. LRU (Least Recently Used) evicts the page that has not been referenced for the longest time, approximating the idea that recently used pages are likely to be used again soon; it requires tracking access recency (via a stack, counters, or the hardware reference bit) and is more expensive but usually performs much better than FIFO. Optimal (also called MIN or Belady's algorithm) evicts the page that will not be used for the longest time in the future; it gives the theoretical lower bound on page faults for a given reference string and frame count, but it is not implementable in practice because it requires knowledge of future references — it is used only as a benchmark to evaluate other algorithms. Other practical algorithms include LFU (Least Frequently Used), MFU (Most Frequently Used), and the Clock (Second-Chance) algorithm, which approximates LRU cheaply using a reference bit and a circular list of frames.
Cricket analogy: FIFO drops whichever player joined the squad longest ago regardless of current form, even if they're still your best batsman; LRU drops whoever hasn't scored runs recently, better approximating current value; Optimal (a selector's dream) would drop whoever won't be needed for the longest future stretch, but requires knowing the future fixture list, so it's only used to benchmark real selection policies; other approaches include dropping the least-capped player (LFU) or using a simple rotation flag (Clock) to approximate recency cheaply.
Example
/*
* Reference string (20 references), 3 frames available:
* 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
*
* --- FIFO (evict oldest-loaded page) ---
* Ref: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
* F1 : 7 7 7 2 2 2 2 4 4 4 0 0 0 1 1 1 1 1 1 1
* F2 : 0 0 0 0 0 0 0 2 2 2 2 2 2 2 0 0 0 0 0
* F3 : 1 1 1 3 3 3 3 3 3 3 3 3 3 3 7 7 7 7
* Flt: F F F F . F F F F F F . . F F . . F F F
* Total FIFO faults = 15
*
* --- LRU (evict least-recently-used page) ---
* Ref: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
* F1 : 7 7 7 2 2 2 2 4 4 4 0 0 0 1 1 1 1 1 1 1
* F2 : 0 0 0 0 0 0 0 2 2 2 2 2 2 2 0 0 0 0 0
* F3 : 1 1 1 3 3 3 3 3 3 3 3 3 3 3 7 7 7 7
* Flt: F F F F . F . F F F F . . F . F . F . .
* Total LRU faults = 12
*
* --- Optimal (evict page used farthest in the future) ---
* Ref: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
* F1 : 7 7 7 7 7 7 7 7 2 2 2 2 2 2 2 2 2 2 2 2
* F2 : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 0 0
* F3 : 1 1 1 3 3 4 4 3 3 3 3 1 1 1 1 1 1 1
* Flt: F F F . . F . F . F . . . F . . . F . .
* Total Optimal faults = 9
*/Analysis
For this reference string with 3 frames, FIFO produces 15 faults, LRU produces 12 faults, and Optimal produces 9 faults — confirming the general rule that Optimal <= LRU <= FIFO in fault count, because Optimal has perfect future knowledge and LRU's recency heuristic usually tracks locality of reference better than simple insertion order. A subtle and interview-favorite fact is Belady's Anomaly: for FIFO specifically, increasing the number of frames can sometimes increase the number of page faults, which is counter-intuitive since more memory should only help. Stack algorithms such as LRU and Optimal are provably immune to Belady's Anomaly because the set of pages held with n frames is always a subset of the pages held with n+1 frames at every step, so adding frames can never hurt.
Cricket analogy: With 3 fielding positions to rotate, a rigid seniority-based rotation (FIFO) causes more missed catches than a form-based rotation (LRU), which in turn is beaten by a selector with perfect hindsight (Optimal) — and oddly, adding a 4th rotation slot to the rigid seniority system can sometimes cause even more missed catches, Belady's Anomaly, a quirk that doesn't affect the form-based or hindsight approaches.
Key Takeaways
- A page fault triggers replacement only when all frames are full; otherwise the OS just loads into a free frame.
- FIFO is simple (queue-based) but can evict hot pages and is the only classic algorithm vulnerable to Belady's Anomaly.
- LRU approximates future behavior using past recency and is a 'stack algorithm', so more frames never increase its fault count.
- Optimal (MIN) is the theoretical best-case bound but is unimplementable since it needs future knowledge; it exists only for comparison.
- For the traced 20-reference string with 3 frames: FIFO = 15 faults, LRU = 12 faults, Optimal = 9 faults, i.e. Optimal <= LRU <= FIFO.
- The Clock (Second-Chance) algorithm is the practical, cheap approximation of LRU used in real operating systems.
Practice what you learned
1. Which page replacement algorithm is guaranteed to give the minimum possible number of page faults for a given reference string and frame count, but cannot be implemented in a real OS?
2. Belady's Anomaly — where adding more frames can increase the number of page faults — is specifically associated with which algorithm?
3. For the reference string 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 with 3 frames, how many page faults does LRU produce?
4. Why is LRU immune to Belady's Anomaly while FIFO is not?
5. The Clock (Second-Chance) algorithm is popular in real operating systems mainly because it:
Was this page helpful?
You May Also Like
Virtual Memory Concepts
The abstraction that gives each process its own address space, which can be larger than physical RAM.
Thrashing
The state where a system spends more time page-faulting and swapping than executing, and how the working-set model prevents it.
Demand Paging
Lazy loading of pages into memory only when referenced, and the step-by-step page-fault handling sequence that makes it work.
Paging
Splitting logical and physical memory into fixed-size pages and frames to eliminate external fragmentation.