Page Replacement Algorithms: FIFO, Optimal (OPT) & LRU
1. Why Do We Need Page Replacement?
In a Demand Paging system, when a Page Fault occurs, the OS needs to bring the requested page from the Hard Disk into a free Frame in Main Memory (RAM).
What if 100% of the Frames in RAM are already full (Zero Free Frames)? The Operating System must choose one of the existing pages currently in RAM (called the Victim Page), swap it out to the disk (if modified), and load the new page into that freed frame!
Definition of a Page Replacement Algorithm: The algorithm used by the OS to decide which existing page in RAM should be replaced (evicted) when a Page Fault occurs and no free frames are available.
- Primary Goal: Choose the victim page that will result in the minimum number of total Page Faults!
Figure 4.10: The 3 Major Page Replacement Algorithms in Operating Systems
1. FIFO (First-In, First-Out)
Replaces the OLDEST page that was brought into RAM first (Suffers from Belady's Anomaly)
2. Optimal (OPT / MIN)
Replaces the page that will NOT be used for the longest period of time in the FUTURE
3. LRU (Least Recently Used)
Replaces the page that has NOT been used for the longest period of time in the PAST
2. Common Reference String for Solved Examples
To compare all three algorithms fairly, let us use the following Page Reference String (12 page requests) with 3 RAM Frames (F = 3):
Formula: Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3 (Initially all 3 frames in RAM are empty
[ , , ]).
- Page Miss (Page Fault): Requested page is NOT in RAM → Must be loaded from Disk.
- Page Hit: Requested page is ALREADY in RAM → No page fault!
3. Algorithm 1: FIFO (First-In, First-Out) Page Replacement
- How It Works: The simplest page-replacement algorithm. The OS maintains a FIFO queue of all pages currently in memory. When a page must be replaced, the oldest page at the front (head) of the queue—the one that entered RAM first—is chosen as the victim!
Step-by-Step Solved Numerical (FIFO with 3 Frames):
Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3
| Step & Page Requested | Frame 1 | Frame 2 | Frame 3 | Status (Hit / Page Fault) | Explanation |
|---|---|---|---|---|---|
1. Page 7 |
7 | - | - | Fault (1) | Loaded 7 into empty Frame 1 |
2. Page 0 |
7 | 0 | - | Fault (2) | Loaded 0 into empty Frame 2 |
3. Page 1 |
7 | 0 | 1 | Fault (3) | Loaded 1 into empty Frame 3 |
4. Page 2 |
2 | 0 | 1 | Fault (4) | RAM full! 7 is oldest → Replaced 7 with 2 |
5. Page 0 |
2 | 0 | 1 | HIT | 0 is already in Frame 2! |
6. Page 3 |
2 | 3 | 1 | Fault (5) | 0 is oldest → Replaced 0 with 3 |
7. Page 0 |
2 | 3 | 0 | Fault (6) | 1 is oldest → Replaced 1 with 0 |
8. Page 4 |
4 | 3 | 0 | Fault (7) | 2 is oldest → Replaced 2 with 4 |
9. Page 2 |
4 | 2 | 0 | Fault (8) | 3 is oldest → Replaced 3 with 2 |
10. Page 3 |
4 | 2 | 3 | Fault (9) | 0 is oldest → Replaced 0 with 3 |
11. Page 0 |
0 | 2 | 3 | Fault (10) | 4 is oldest → Replaced 4 with 0 |
12. Page 3 |
0 | 2 | 3 | HIT | 3 is already in Frame 3! |
- Total Page Faults in FIFO = 10 (and Total Page Hits = 2).
Major Drawback of FIFO — Belady’s Anomaly:
- Normally, you would expect that giving a process more RAM frames (say 4 frames instead of 3 frames) would reduce the number of page faults.
- However, in FIFO, for certain reference strings (like
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5), increasing the number of RAM frames from 3 to 4 actually INCREASES the number of Page Faults (from 9 faults to 10 faults)! - Definition of Belady’s Anomaly: The phenomenon in which the page-fault rate INCREASES as the number of allocated RAM frames increases. (Only FIFO suffers from Belady’s Anomaly; Optimal and LRU never suffer from it!).
4. Algorithm 2: Optimal (OPT / MIN) Page Replacement
- How It Works: Discovered as a result of Belady’s Anomaly, the Optimal Page Replacement Algorithm looks ahead into the FUTURE of the reference string and replaces the page that will NOT be used for the longest period of time in the future!
- Why is it important? It guarantees the lowest possible page-fault rate for a fixed number of frames and never suffers from Belady’s Anomaly.
- Drawback: Impossible to implement in a real OS because an OS cannot predict the future! It is used as a theoretical benchmark to measure how well other algorithms (like LRU) perform.
Step-by-Step Solved Numerical (Optimal with 3 Frames):
Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3
| Step & Page Requested | Frame 1 | Frame 2 | Frame 3 | Status | Look-Ahead Explanation (Looking into the Future) |
|---|---|---|---|---|---|
1–3. 7, 0, 1 |
7 | 0 | 1 | 3 Faults | First 3 frames filled (7, 0, 1) |
4. Page 2 |
2 | 0 | 1 | Fault (4) | Look ahead: 0 used next, 1 used never, 7 used never → Replace 7 with 2 |
5. Page 0 |
2 | 0 | 1 | HIT | 0 already in RAM |
6. Page 3 |
2 | 0 | 3 | Fault (5) | Between 2, 0, 1: 0 & 2 are needed soon; 1 is never needed again → Replace 1 with 3 |
7. Page 0 |
2 | 0 | 3 | HIT | 0 already in RAM |
8. Page 4 |
2 | 4 | 3 | Fault (6) | Future is 2, 3, 0, 3: 2 & 3 are needed next, 0 is needed furthest in future → Replace 0 with 4 |
9. Page 2 |
2 | 4 | 3 | HIT | 2 already in RAM |
10. Page 3 |
2 | 4 | 3 | HIT | 3 already in RAM |
11. Page 0 |
2 | 0 | 3 | Fault (7) | Replace 4 (never used again) with 0 |
12. Page 3 |
2 | 0 | 3 | HIT | 3 already in RAM |
- Total Page Faults in Optimal = 7 (and Total Page Hits = 5).
5. Algorithm 3: LRU (Least Recently Used) Page Replacement
- How It Works: Since we cannot look into the future (Optimal), LRU uses the recent PAST as an approximation of the near future!
- Golden Rule of LRU: When a page fault occurs, look BACKWARD into the past and replace the page that has NOT been used for the longest period of time (the Least Recently Used page)!
- Why is LRU the most popular algorithm? It is practical, performs almost as well as Optimal, and never suffers from Belady’s Anomaly (because it is a Stack Algorithm).
Step-by-Step Solved Numerical (LRU with 3 Frames):
Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3
| Step & Page Requested | Frame 1 | Frame 2 | Frame 3 | Status | Look-Back Explanation (Looking into the Past) |
|---|---|---|---|---|---|
1–3. 7, 0, 1 |
7 | 0 | 1 | 3 Faults | First 3 frames filled (7, 0, 1) |
4. Page 2 |
2 | 0 | 1 | Fault (4) | Look back at 7, 0, 1: 7 was used longest ago → Replace 7 with 2 |
5. Page 0 |
2 | 0 | 1 | HIT | 0 is hit (now 0 is Most Recently Used!) |
6. Page 3 |
2 | 0 | 3 | Fault (5) | Between 2, 0, 1: 0 used at step 5, 2 at step 4, 1 at step 3 (oldest!) → Replace 1 with 3 |
7. Page 0 |
2 | 0 | 3 | HIT | 0 is hit |
8. Page 4 |
4 | 0 | 3 | Fault (6) | Between 2, 0, 3: 2 was used longest ago (step 4) → Replace 2 with 4 |
9. Page 2 |
4 | 0 | 2 | Fault (7) | Between 4, 0, 3: 3 was used longest ago (step 6) → Replace 3 with 2 |
10. Page 3 |
4 | 3 | 2 | Fault (8) | Between 4, 0, 2: 0 was used longest ago (step 7) → Replace 0 with 3 |
11. Page 0 |
0 | 3 | 2 | Fault (9) | Between 4, 3, 2: 4 was used longest ago (step 8) → Replace 4 with 0 |
12. Page 3 |
0 | 3 | 2 | HIT | 3 is hit! |
- Total Page Faults in LRU = 9 (Better than FIFO’s 10, and close to Optimal’s 7!).
6. Summary Comparison: FIFO vs Optimal vs LRU
| Basis | FIFO | Optimal (OPT) | LRU (Least Recently Used) |
|---|---|---|---|
| 1. Replacement Rule | Replaces the oldest loaded page in RAM. | Replaces the page not needed for the longest time in the FUTURE. | Replaces the page not used for the longest time in the PAST. |
| 2. Belady’s Anomaly? | YES (Suffers from Belady’s Anomaly). | NO (Never suffers). | NO (Never suffers). |
| 3. Practicality | Easy to implement (simple queue), but poor performance. | Impossible to implement in real OS (needs future knowledge). | Highly Practical and widely used in real operating systems. |
| 4. Page Fault Rate | Highest page faults (10 in our example). |
Lowest possible page faults (7 in our example). |
Low page faults (9 in our example). |
💡 Exam Preparation Tips for DAVV BCA
- Page Replacement Algorithms (
FIFO, Optimal, LRU) is the single highest-scoring 8-mark topic in Unit 4! Even if the exam asks a theory question without giving a reference string, write a small 8-number reference string and solve a mini table—examiners award full 8/8 marks for this! - Always define Belady’s Anomaly under FIFO.