GATE CS 2017 Set 1 Q40 — Memory Management and Virtual Memory

To determine which statements are correct, let us analyze the properties of the page replacement algorithms with respect to Belady's anomaly.

1. Stack Algorithms and Belady's Anomaly

A page replacement algorithm is called a stack algorithm if the set of pages in memory for $n$ frames is always a subset of the set of pages in memory for $n+1$ frames, for any given page reference string. Stack algorithms never suffer from Belady's anomaly.

2. Analyzing Statement $S_2$ (LRU)

• Least Recently Used (LRU) is a well-known stack algorithm.
• At any point in time, the $n$ pages in memory for an $n$-frame system are the $n$ most recently referenced pages, which is always a subset of the $n+1$ most recently referenced pages in an $(n+1)$-frame system.
• Since LRU is a stack algorithm, it does not suffer from Belady's anomaly. Thus, $S_2$ is false.

3. Analyzing Statement $S_1$ (Random)

• The Random page replacement algorithm selects a page to evict uniformly at random.
• Because the replacement decisions are non-deterministic and do not depend on the recency or frequency of access, it does not satisfy the stack property.
• Since it is not a stack algorithm, there exist reference strings and sequences of random choices where increasing the number of frames leads to more page faults. Thus, Random page replacement suffers from Belady's anomaly. Therefore, $S_1$ is true.

Hence, $S_1$ is true and $S_2$ is false, which corresponds to Option B.