Topic: Operating Systems
Consider the following reference strings and assume 3 frames are available, then the number of page faults that occur using Optimal page replacement algorithm is
6, 0, 5, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 5, 2
- A. 15 Page Faults
- B. 9 Page Faults
- C. 12 Page Faults
- D. 8 Page Faults
Answer: D. 8 Page Faults
Explanation: Using Optimal replacement (replace page not used for the longest time in the future):
1. '6' -> Miss (Frames: 6)
2. '0' -> Miss (Frames: 6, 0)
3. '5' -> Miss (Frames: 6, 0, 5)
4. '2' -> Miss. Look ahead: 0 used next, 5 used at end, 6 never. Replace 6. (Frames: 2, 0, 5)
5. '0' -> Hit.
6. '3' -> Miss. Look ahead: 0, 4, 2, 3... 5 is furthest. Replace 5. (Frames: 2, 0, 3)
7. '0' -> Hit.
8. '4' -> Miss. Look ahead: 2, 3, 0. Replace 0 (used furthest away). (Frames: 2, 4, 3)
9. '2' -> Hit.
10. '3' -> Hit.
11. '0' -> Miss. Look ahead: 3, 2, 5. Replace 4. (Frames: 2, 0, 3)
12. '3' -> Hit.
13. '2' -> Hit.
14. '5' -> Miss. Replace 0 or 3. (Frames: 2, 5, 3)
15. '2' -> Hit.
Total Page Faults = 3 (initial) + 5 (replacements) = 8.