GATE 2015 CS (CS1) – Question 57
Consider a main memory with five page frames and the following sequence of page references: 3, 8, 2, 3, 9, 1, 6, 3, 8, 9, 3, 6, 2, 1, 3. Which one of the following is true with respect to page replacement policies First In First Out (FIFO) and Least Recently Used (LRU)?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) Both incur the same number of page faults
Explanation
Reference string: 3, 8, 2, 3, 9, 1, 6, 3, 8, 9, 3, 6, 2, 1, 3 with 5 frames.
**FIFO**
- 3, 8, 2: faults. 3: hit. 9, 1: faults. Frames $[3,8,2,9,1]$ (5 faults).
- 6: fault, evict 3. 3: fault, evict 8. 8: fault, evict 2. Frames $[9,1,6,3,8]$ (8 faults).
- 9, 3, 6: hits. 2: fault, evict 9 (9 faults). 1, 3: hits.
FIFO total: **9** faults.
**LRU**
- First 6 references give the same 5 faults; frames $\{3,8,2,9,1\}$.
- 6: fault, evict LRU 8. 3: hit. 8: fault, evict 2 (7 faults).
- 9, 3, 6: hits. 2: fault, evict 1 (8 faults). 1: fault, evict 8 (9 faults). 3: hit.
LRU total: **9** faults.
Both incur the same number of faults: option (A).