Counting FIFO page faults — Aptitude Question
Counting FIFO page faults: A process references the pages 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. Answer and worked solution on CodeKairo.
- Topic: OS, DBMS & Networks
- Section: Programming MCQs
- Difficulty: Medium
- Time target: 180 seconds
Question
A process references the pages 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. With three frames and FIFO replacement, how many page faults occur? Count the initial loads as faults.
Options
- 7
- 8
- 9
- 10
Show the answer and the worked solution
Correct answer: C. 9
Worked solution
- Pages 1, 2 and 3 fault into the empty frames, leaving [1, 2, 3].
- 4 faults and evicts the oldest page 1, giving [2, 3, 4]; 1 faults and evicts 2, giving [3, 4, 1]; 2 faults and evicts 3, giving [4, 1, 2].
- 5 faults and evicts 4, giving [1, 2, 5]; the following references to 1 and to 2 are both hits.
- 3 faults and evicts 1, giving [2, 5, 3]; 4 faults and evicts 2, giving [5, 3, 4]; the last reference to 5 is a hit.
- The faults are on 1, 2, 3, 4, 1, 2, 5, 3 and 4 — 9 faults in total, with only three hits.
Answer: 9.
The idea
Write the frame contents after every reference rather than trying to hold them in your head. FIFO's queue order is what makes it cheap to implement and poor at keeping hot pages resident.
Shortcut. Count the hits instead: only the 1 and 2 straight after the 5, and the final 5, find their page resident, so 12 − 3 = 9 faults.
Common trap. 10 is what LRU gives on this string with three frames, and FIFO with four; mixing up the policy or remembering Belady's larger figure lands on it.