1Definition
Page Replacement Algorithms are OS kernel strategies used during a Page Fault to decide which physical frame's page to swap out when all physical RAM frames are occupied. Common algorithms include FIFO (First-In, First-Out), Optimal Page Replacement, LRU (Least Recently Used), LFU (Least Frequently Used), and MFU (Most Frequently Used). Belady's Anomaly is a counter-intuitive phenomenon in FIFO where increasing the number of physical frames increases the total number of page faults.
2Simple Explanation
When a Page Fault occurs and RAM is completely full, the OS must evict an old page to make room for the new page.
- FIFO: Evicts the oldest page brought into RAM. (Easy, but suffers from Belady's Anomaly).
- Optimal: Evicts the page that will not be used for the longest time in the future. (Mathematically perfect, but impossible to implement in real life because the OS cannot predict the future!).
- LRU: Evicts the page that has not been used for the longest period in the recent past. (Uses recent past as an approximation of the future; best practical algorithm!).
- LFU / MFU: Evicts pages based on how few or many times they have been referenced.
3Real-Life Example / Analogy
Managing a Small Desk Workspace: Your desk fits 3 books. You need a 4th book.
- FIFO: Putting away the book you placed on the desk first, even if you are currently using it.
- Optimal: Predicting the future perfectly and putting away the book you won't open for the rest of the week.
- LRU: Checking the clock and putting away the book you haven't opened in the last 3 hours.
4Diagram / Visual Representation
5Working / How It Works
- LRU Implementation Techniques:
- Counter Approach: Every Page Table entry has a
Time-of-Usecounter field. When a page is referenced, copy the CPU clock counter into its entry. During replacement, search for the page with the smallest counter value. - Stack Approach: Maintain a doubly linked list stack of page numbers. When a page is referenced, remove it from the middle of the stack and push it to the top. The bottom of the stack is always the LRU page!
- Counter Approach: Every Page Table entry has a
6Types / Components / Characteristics
- Page Replacement Algorithms Comparison:
| Algorithm | Replacement Criteria | Belady's Anomaly? | Implementation Feasibility | Performance |
|---|---|---|---|---|
| FIFO | Replaces oldest page in RAM | YES (Faults can increase with more frames) | Extremely Easy (Queue) | Poor / Unpredictable |
| Optimal | Replaces page referenced farthest in future | No | Impossible (Requires future reference knowledge) | Theoretical Best (Minimum Faults) |
| LRU | Replaces page unused for longest recent time | No | Complex (Requires Hardware Counters / Stack) | Excellent (Best practical algorithm) |
| LFU | Replaces page with smallest reference count | No | Moderate (Reference Counters) | Moderate / Rarely used |
| MFU | Replaces page with largest reference count | No | Moderate (Reference Counters) | Moderate / Rarely used |
7Solved Examples / Problems
Problem: Given the Page Reference String: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5, trace FIFO with 3 Frames vs 4 Frames to demonstrate Belady's Anomaly.
Solution:
Execution with 3 Frames (FIFO):
1: [1, -, -] (Fault 1)2: [1, 2, -] (Fault 2)3: [1, 2, 3] (Fault 3)4: Replaces 1 -> [4, 2, 3] (Fault 4)1: Replaces 2 -> [4, 1, 3] (Fault 5)2: Replaces 3 -> [4, 1, 2] (Fault 6)5: Replaces 4 -> [5, 1, 2] (Fault 7)1: Hit! [5, 1, 2]2: Hit! [5, 1, 2]3: Replaces 1 -> [5, 3, 2] (Fault 8)4: Replaces 2 -> [5, 3, 4] (Fault 9)5: Hit! [5, 3, 4]- Total Page Faults (3 Frames) = 9 Faults.
Execution with 4 Frames (FIFO):
1: [1, -, -, -] (Fault 1)2: [1, 2, -, -] (Fault 2)3: [1, 2, 3, -] (Fault 3)4: [1, 2, 3, 4] (Fault 4)1: Hit! [1, 2, 3, 4]2: Hit! [1, 2, 3, 4]5: Replaces 1 -> [5, 2, 3, 4] (Fault 5)1: Replaces 2 -> [5, 1, 3, 4] (Fault 6)2: Replaces 3 -> [5, 1, 2, 4] (Fault 7)3: Replaces 4 -> [5, 1, 2, 3] (Fault 8)4: Replaces 5 -> [4, 1, 2, 3] (Fault 9)5: Replaces 1 -> [4, 5, 2, 3] (Fault 10)- Total Page Faults (4 Frames) = 10 Faults!
Conclusion: Increasing frames from 3 to 4 increased page faults from 9 to 10! This proves Belady's Anomaly in FIFO.
8Advantages, Disadvantages & Applications
- LRU Advantages: Zero Belady's Anomaly, near-optimal performance in practice.
- LRU Disadvantages: Requires hardware support (counters or doubly linked stacks) to update on every memory reference.
9Important Points to Remember
- Belady's Anomaly occurs in FIFO, but NEVER occurs in LRU or Optimal algorithms (Stack Algorithms).
- Optimal algorithm gives the theoretical minimum page fault rate.
10Test Your Understanding
- MCQ: Belady's Anomaly is a phenomenon where the number of page faults increases as the number of allocated physical frames increases. Which algorithm exhibits this anomaly?
- A) Least Recently Used (LRU)
- B) Optimal Page Replacement
- C) First-In, First-Out (FIFO)
- D) Working Set Model
Show answer
C. - Conceptual Question: Explain the Stack Approach used to implement LRU page replacement.
- Application Question: Trace the LRU page replacement algorithm for reference string
7, 0, 1, 2, 0, 3, 0, 4with 3 frames.
