GATE CS 2016 Set 2 Q.30 (CS Q.20): Memory Management and Virtual Memory

In which one of the following page replacement algorithms it is possible for the page fault rate to increase even when the number of allocated frames increases?

LRU (Least Recently Used)

OPT (Optimal Page Replacement)

MRU (Most Recently Used)

FIFO (First In First Out)

Official answer and solution

Official answer: D
From: Official GATE 2016 answer key

Solution

Identify the page replacement algorithm susceptible to Belady's Anomaly.

Belady's Anomaly is the counterintuitive phenomenon where increasing the number of allocated physical frames results in an increase in the number of page faults for a given reference string.

Stack algorithms are page replacement algorithms where the set of pages resident in an $n$ -frame memory is always a subset of the pages resident in an $(n+1)$ -frame memory ( $M(n) \subseteq M(n+1)$ ). Stack algorithms are mathematically proven never to suffer from Belady's Anomaly.

LRU and OPT are stack algorithms, so they never experience Belady's anomaly.

First-In-First-Out (FIFO) is not a stack algorithm. A classic counterexample on reference string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 results in 9 page faults with 3 frames, but 10 page faults with 4 frames.

Therefore, FIFO can exhibit an increased page fault rate.

Final answer

Common trap

Assuming all standard page replacement algorithms improve monotonically with additional frames.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2016 Computer Science and Information Technology (CS) Session 2
Question: 30 of 65, printed as CS Q.20
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source