Chapter 3 (Hindi)
5. Page Replacement Algorithm
📌 Page Replacement Algorithm
जब paging system में page fault होता है और कोई free frame available नहीं होता, तब OS को किसी पुराने page को हटाकर नया page लाना पड़ता है। इसे page replacement कहते हैं।
🔹 Virtual Memory Manager क्या करता है
- एक victim page select करता है (algorithm के अनुसार)
- उसकी page table entry को “not present” mark करता है
- अगर page dirty (modified) है → उसे पहले disk में write करता है
👉 Algorithm की efficiency directly page fault rate और system performance को affect करती है।
📌 Common Page Replacement Techniques
- FIFO (First In First Out)
- Optimal Page Replacement
- LRU (Least Recently Used)
- MRU (Most Recently Used)
🔹 1. FIFO (First In First Out)
यह सबसे simple algorithm है।
- Memory में pages को queue में रखा जाता है
- जो page सबसे पहले आया (oldest) → वही सबसे पहले remove होगा
📊 Example (FIFO)
Page Reference String:
1, 3, 0, 3, 5, 6, 3
Frames = 3
| Step | Page | Frame स्थिति | Page Fault |
|---|---|---|---|
| 1 | 1 | 1 _ _ | Yes |
| 2 | 3 | 1 3 _ | Yes |
| 3 | 0 | 1 3 0 | Yes |
| 4 | 3 | 1 3 0 | No |
| 5 | 5 | 5 3 0 | Yes (1 removed) |
| 6 | 6 | 5 6 0 | Yes (3 removed) |
| 7 | 3 | 5 6 3 | Yes (0 removed) |
✅ Total Page Faults = 6
📌 Optimal Page Replacement
Optimal algorithm में वह page replace किया जाता है जो future में सबसे देर से use होगा या बिल्कुल use नहीं होगा।
📊 Given Example
Page Reference String:
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3
Frames = 4
🔹 Step-by-Step Solution
| Step | Page | Frames स्थिति | Page Fault |
|---|---|---|---|
| 1 | 7 | 7 _ _ _ | Yes |
| 2 | 0 | 7 0 _ _ | Yes |
| 3 | 1 | 7 0 1 _ | Yes |
| 4 | 2 | 7 0 1 2 | Yes |
| 5 | 0 | 7 0 1 2 | No |
| 6 | 3 | 3 0 1 2 | Yes (7 replace) |
| 7 | 0 | 3 0 1 2 | No |
| 8 | 4 | 3 0 4 2 | Yes (1 replace) |
| 9 | 2 | 3 0 4 2 | No |
| 10 | 3 | 3 0 4 2 | No |
| 11 | 0 | 3 0 4 2 | No |
| 12 | 3 | 3 0 4 2 | No |
| 13 | 2 | 3 0 4 2 | No |
| 14 | 3 | 3 0 4 2 | No |
✅ Total Page Faults = 6
📌 3. Least Recently Used (LRU) – हिंदी + कुछ English words
LRU (Least Recently Used) algorithm में वह page replace होता है जो सबसे लंबे समय से use नहीं हुआ है।
📊 Given Example
Page Reference String:
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3
Frames = 4
🔹 Step-by-Step Solution
| Step | Page | Frames स्थिति | Page Fault |
|---|---|---|---|
| 1 | 7 | 7 _ _ _ | Yes |
| 2 | 0 | 7 0 _ _ | Yes |
| 3 | 1 | 7 0 1 _ | Yes |
| 4 | 2 | 7 0 1 2 | Yes |
| 5 | 0 | 7 0 1 2 | No |
| 6 | 3 | 3 0 1 2 | Yes (7 replaced) |
| 7 | 0 | 3 0 1 2 | No |
| 8 | 4 | 3 0 4 2 | Yes (1 replaced) |
| 9 | 2 | 3 0 4 2 | No |
| 10 | 3 | 3 0 4 2 | No |
| 11 | 0 | 3 0 4 2 | No |
| 12 | 3 | 3 0 4 2 | No |
| 13 | 2 | 3 0 4 2 | No |
| 14 | 3 | 3 0 4 2 | No |
✅ Total Page Faults = 6
📌 4. Most Recently Used (MRU)
MRU (Most Recently Used) algorithm में वह page replace होता है जो सबसे हाल ही में (recently) use हुआ है।
👉 LRU का उल्टा concept है।
📊 Given Example
Page Reference String:
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3
Frames = 4
🔹 Step-by-Step Solution
| Step | Page | Frames स्थिति | Page Fault |
|---|---|---|---|
| 1 | 7 | 7 _ _ _ | Yes |
| 2 | 0 | 7 0 _ _ | Yes |
| 3 | 1 | 7 0 1 _ | Yes |
| 4 | 2 | 7 0 1 2 | Yes |
| 5 | 0 | 7 0 1 2 | No |
| 6 | 3 | 7 3 1 2 | Yes (0 replaced – MRU) |
| 7 | 0 | 7 3 0 2 | Yes (3 replaced) |
| 8 | 4 | 7 3 0 4 | Yes (2 replaced) |
| 9 | 2 | 7 3 0 2 | Yes (4 replaced) |
| 10 | 3 | 7 3 0 2 | No |
| 11 | 0 | 7 3 0 2 | No |
| 12 | 3 | 7 3 0 2 | No |
| 13 | 2 | 7 3 0 2 | No |
| 14 | 3 | 7 3 0 2 | No |
✅ Total Page Faults = 8
