The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
1.3k views
does Random page replacement algorithm suffers from belady's anomaly?
asked in Operating System by Veteran (20.5k points) | 1.3k 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 (111 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 (15.2k points)


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

28,946 questions
36,791 answers
91,045 comments
34,687 users