The GATE Grind

GATE 2017 CS – Question 50

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

Recall that Belady's anomaly is that the page-fault rate may *increase* as the number of allocated frames increases. Now, consider the following statements:

S1: *Random page replacement* algorithm (where a page chosen at random is replaced) suffers from Belady's anomaly

S2: *LRU page replacement* algorithm suffers from Belady's anomaly

Which of the following is CORRECT?

  1. S1 is true, S2 is true
  2. S1 is true, S2 is false
  3. S1 is false, S2 is true
  4. S1 is false, S2 is false

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) S1 is true, S2 is false

Explanation

A random choice of victim has no guarantee that more frames means fewer faults, so it can show the anomaly. LRU is a stack algorithm, so the set of pages held with $k$ frames is always contained in the set held with $k + 1$ frames, and it never suffers from the anomaly.