The GATE Grind

GATE 2015 CS (CS1) – Question 57

Operating System · Memory Management and Virtual Memory · 2 marks · Multiple choice

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)?

  1. Both incur the same number of page faults
  2. FIFO incurs 2 more page faults than LRU
  3. LRU incurs 2 more page faults than FIFO
  4. FIFO incurs 1 more page fault than 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).

More Memory Management and Virtual Memory questions

All Memory Management and Virtual Memory questions →