GATE - 2017 | OS | Recall that Belady’s anomaly is that the page-fault rate may increase as

GATE - 2017 [Operating System]

Question:

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?

A	S1 is true, S2 is true
B	S1 is true, S2 is false
C	S1 is false, S2 is true
D	S1 is false, S2 is false

    

Solution:

Option (B) is Correct

FIFO may suffer from Belady's anomaly not always FIFO suffers from Belady's anomaly.
Page replacement algorithm suffers from Belady's anomaly when it is not a stack algorithm.
S1: Random page replacement algorithm is not a stack algorithm. So, S1 is true.
S2: LRU is a stack algorithm. Therefore, it doesn't suffer from Belady's anomaly. S2 is false.

---------------------------------------------

S1: Random page replacement algorithm (where a page chosen at random is replaced)

Suffers from Belady’s anomaly.

A random page replacement algorithm can behave like any replacement algorithm. It may behave as FIFO, LRU, MRU, etc.). When a random page replacement algorithm behaves like a FIFO page replacement algorithm in that case there can be chances of belady’s anamoly.

For this let us consider an example of the FIFO case, if we consider the reference string 3  2 1 0 3 2 4 3 2 1 0 4 and 3 frame slots, in this, we get a 9-page fault but if we increase slots to 4, then we get 10-page faults.

So, page faults are increasing by increasing the number of frame slots. It suffers from belady’s anamoly.

 

S2: LRU page replacement algorithm suffers from Belady’s anomaly

It doesn’t suffer from page replacement algorithm because, in LRU, the page which is least recently used is replaced by the new page. Also, LRU Is a stack algorithm. (A stack algorithm is one that satisfies the inclusion property.) and stack algorithm doesn’t suffer from belady’s anamoly.

 

Thank You