- Asked 2/13
- 2070 Magh · 2+8 marks
Page faults: FIFO, Optimal, LFU, LRU
Short answer
A page fault occurs when a process accesses a page not in main memory. With 5 frames, FIFO results in 10 faults, Optimal 7, LFU 8, and LRU 8.
What is page fault? Consider the following page reference string: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6. How many page faults would occur for the FIFO, Optimal, LFU and LRU replacement algorithms having five frames? Remember all frames are initially empty, so your first unique page will cost one fault each.
Page fault
A page fault occurs when a process accesses a page that is not currently in main memory (its page-table entry is invalid). The OS brings the page from disk into a frame, replacing a page if no frame is free.
Simulation (5 frames, initially empty)
Reference string: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6 (20 references). * = page fault.
FIFO
ref 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
F1 1 1 1 1 1 1 1 6 6 6 6 6 6 6 6 6 6 6 6 6
F2 - 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1
F3 - - 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2
F4 - - - 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3
F5 - - - - - - 5 5 5 5 5 5 7 7 7 7 7 7 7 7
* * * * * * * * * *
Faults = 10.
Optimal
ref 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
F1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
F2 - 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
F3 - - 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
F4 - - - 4 4 4 4 6 6 6 6 6 6 6 6 6 6 6 6 6
F5 - - - - - - 5 5 5 5 5 5 7 7 7 7 7 7 7 7
* * * * * * *
Faults = 7.
LFU (replace the page with the smallest reference count; ties broken by FIFO, the oldest page goes first)
ref 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
F1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
F2 - 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
F3 - - 3 3 3 3 3 6 6 6 6 6 6 6 6 6 6 6 6 6
F4 - - - 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3
F5 - - - - - - 5 5 5 5 5 5 7 7 7 7 7 7 7 7
* * * * * * * *
Faults = 8. At the reference 6, counts are 1:2, 2:2, 3:1, 4:1, 5:1; the oldest of the lowest count is 3, so 3 is replaced. At the reference 3 (position 12), pages 4, 5 and 6 all have count 1; the oldest, 4, is replaced.
LRU
ref 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
F1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
F2 - 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
F3 - - 3 3 3 3 3 6 6 6 6 6 6 6 6 6 6 6 6 6
F4 - - - 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3
F5 - - - - - - 5 5 5 5 5 5 7 7 7 7 7 7 7 7
* * * * * * * *
Faults = 8.
Result
| Algorithm | Page faults |
|---|---|
| FIFO | 10 |
| Optimal | 7 |
| LFU | 8 |
| LRU | 8 |
Answer: FIFO = 10, Optimal = 7, LFU = 8, LRU = 8 page faults. There are 7 distinct pages (1 to 7), so 7 faults is the minimum possible, and Optimal achieves it.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Page faults with 3 frames: LRU, FIFO, OPT · Operating System, chapter 4 · asked 2×
- Thrashing; page faults on 3 frames · Operating System, chapter 4
- Page faults: LRU, FIFO, Optimum · Operating System, chapter 4
- LRU algorithm; page faults on string · Operating System, chapter 4
- Hits and faults: FIFO, LRU, Optimal · Operating System, chapter 4