GATE CSE
First time here? Checkout the FAQ!
x
0 votes
1.2k views
does Random page replacement algorithm suffers from belady's anomaly?
asked in Operating System by Veteran (18.5k points)   | 1.2k views

No. Only FIFO page replacement suffers from Belady's anomaly.

http://www.cs.cornell.edu/courses/cs4410/2015su/lectures/lec15-replacement.html

Bro any non stack based algorithm suffers from Belady's. What if Random selection in FIFO manner ? Fearful now. -_-
Random Selction can't be FIFO all the time, right? Or am I missing something?
I think even if it happened for 1 time it is Belady's anomaly. Right?  -_-
i too think so .....question it was mentioned that beladys anomaly means : page faults MAY INCREASE when number of frames increased.....in random isnt there a chance of getting fifo sequence ..and there by chance of same problem
I think both of you are right. Random has Belady's anomaly.

3 Answers

+1 vote
Best answer

Any page replacement policy/algo. suffers from Belady's Anomaly's iff its does not follow "STACK ALGORITHM" . LRU and Optimal always follow the stack algorithm property. So they never suffers from Belady's Anamoly.

You have to understand Stack Algorithm first. 

As far as you question is concerned ,Answer is "YES,Random page replacement algorithm may suffers from Belady's Anomaly".

 

answered by (101 points)  
selected by
+5 votes
i think random replacement can suffer from belady anomaly coz there can be a case when page selected to be replaced is by fifo policy.I think that case might count.
answered by Active (1.4k points)  
in FIFO also, not all the time it behave belady anomoly, it happen only sometime. if we consider random page replacement will behave sometime like FIFO but it does not mean whenever it will behave as FIFO ,belady anomoly will be there.??
0 votes
The main reason for belady anomaly is the stack property. Means the pages when frames were less should be a subset of pages when pages are more. On increasing page frames the page which were earlier there should always be there. If we randomly remove any element then it may be case that we inocuur palenty for pages that were earlier there but now after increasing page fault they may be removed.
answered by Veteran (14.1k points)  


Top Users Sep 2017
  1. Habibkhan

    7166 Points

  2. Warrior

    2640 Points

  3. Arjun

    2574 Points

  4. rishu_darkshadow

    2520 Points

  5. A_i_$_h

    2280 Points

  6. nikunj

    1980 Points

  7. manu00x

    1846 Points

  8. makhdoom ghaya

    1770 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points


26,144 questions
33,727 answers
79,957 comments
31,116 users