GATE CSE 2017 Set 1 · Q40
Time
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
Select one answerSingle correct
Solution
Official answer: B) S1 is true, S2 is false
Memory Management and Virtual MemoryBelady's Anomaly occurs when increasing the number of page frames results in an increase in the number of page faults for a given memory access pattern.
Stack Algorithms: A page replacement algorithm is called a *stack algorithm* if the set of pages in memory for frames is always a subset of the set of pages in memory for frames. Stack algorithms are mathematically proven never to suffer from Belady's anomaly. Examples of stack algorithms include LRU (Least Recently Used) and Optimal page replacement.
Therefore, statement S2 is false.
Random Page Replacement: Because replacement choices are made uniformly at random without maintaining the inclusion property of stack algorithms, there exist reference strings and frame allocations where a larger frame allocation can produce more page faults than a smaller one. Hence, Random replacement suffers from Belady's anomaly.
Therefore, statement S1 is true.
Thus, S1 is true, S2 is false, which corresponds to option (B).
Try the question first, then check your work.
Examiner trap
Check whether LRU satisfies the stack inclusion property, and recall which algorithms are immune to Belady's anomaly.
This Memory Management and Virtual Memory previous year question is Q40 of the GATE CSE 2017 Set 1 paper. Find more GATE CSE PYQs on Memory Management and Virtual Memory in Operating Systems, or browse all GATE CSE PYQs.
Free diagnostic
Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Memory Management and Virtual Memory PYQs now with no account.
An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.
Memory Management and Virtual Memory has 32 GATE CSE PYQs across 22 papers from 2011 to 2026. 6 of them are 2-mark MCQs like this one, and it is the only one in GATE CSE 2017 Set 1.
How GATE tests Memory Management and Virtual MemoryIndependent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.