The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+15 votes
990 views

Which of the following page replacement algorithms suffers from Belady’s anamoly?

  1. Optimal replacement

  2. LRU

  3. FIFO

  4. Both (A) and (C)

asked in Operating System by Veteran (59.6k points)
edited by | 990 views
0

Proof that LRU does not incur Belady’s anomaly but that FIFO does incur the anomaly: http://ranger.uta.edu/~weems/NOTES5314/HW/hw3.3.pdf

4 Answers

+15 votes
Best answer

Answer is (C).

FIFO sufferes from Belady's anomaly. Optimal replacement never suffers from Belady's anomaly.

answered by Loyal (8.3k points)
edited by
+7 votes
Answer : C) FIFO

How/Why?
Page Replacement algorithms suffer from Belady’s anamoly if :

  • They do not follow the stack based algorithm.

Reference :-

Since LRU & Optimal Replacement Algo follow Stack Algo, hence they are not affected by Belady's Anamoly.

answered by Active (1.4k points)
edited by
0 votes

Belady’s anomaly occurs in those page replacement algorithm which does not have a Stack Algorithm.

Stack Algorithm: It is observed that on increasing the number of frames, the page fault is going to decrease, But FIFO shows an exceptional behavior. This algorithm says that if some pages are present in a system with n number then they are definitely going to present in a system with the n+1 frame. But FIFO denies this and that is why Only FIFO suffers from Belady's Anomaly 

 

 

 

 

 

answered by (197 points)
0 votes
In case of Optimal or LRU when i increase the no. of frames then the no. of page faults will either decrease or remains same. But in case of FIFO sometimes even if i increase the no. of frames it is not going to decrease the page faults and infact it is going to increase them. That's why FIFO is having Belady's anamoly, as FIFO doesn't have a property called Stack property and it's not a stack algorithm.
answered by (367 points)
edited ago by
0
@punit I think FIFO is having Belady's anomaly because it does not follow the stack algorithm so how we called it as stack algo.
0
@lakshya yeah..i've rectified it!

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,599 questions
48,601 answers
155,674 comments
63,741 users