The GATE Grind

GATE 2015 CS – 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

FIFO faults on 3, 8, 2, 9, 1, then 6 (evicting 3), 3 (evicting 8), 8 (evicting 2) and 2 (evicting 9), which is 9 faults. LRU faults on 3, 8, 2, 9, 1, then 6 (evicting 8), 8 (evicting 2), 2 (evicting 1) and 1 (evicting 8), which is also 9 faults. Both policies have the same count.