edited by
15,036 views
46 votes
46 votes

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:

  • $S_1$: Random page replacement algorithm (where a page chosen at random is replaced) suffers from Belady's anomaly.
  • $S_2$: LRU page replacement algorithm suffers from Belady's anomaly.

Which of the following is CORRECT?

  1. $S_1$ is true, $S_2$ is true
  2. $S_1$ is true, $S_2$ is false
  3. $S_1$ is false, $S_2$ is true
  4. $S_1$ is false, $S_2$ is false
edited by

5 Answers

Best answer
70 votes
70 votes

A page replacement algorithm suffers from Belady's anamoly when it is not a stack algorithm.

A stack algorithm is one that satisfies the inclusion property. The inclusion property states that, at a given time, the contents(pages) of a memory of size k page-frames is a subset of the contents of memory of size $k+1$ page-frames, for the same sequence of accesses. The advantage is that running the same algorithm with more pages(i.e. larger memory) will never increase the number of page faults.


Is LRU a stack algorithm?

Yes, LRU is a stack algorithm. Therefore, it doesn't suffer from Belady's anamoly.

Ref : Ref1 and Ref2


Is Random page replacement algorithm a stack algorithm?

No, as it may choose a page to replace in FIFO manner or in a manner which does not satisfy inclusion property. This means it could suffer from Belady's anamoly.

$\therefore$ (B) should be answer.

edited by
33 votes
33 votes


Ans: B
In simple, when we say RANDOM it includes all the possibilities including FIFO.
Now you may have one doubt.
"Random does not act as FIFO always, why will it suffer from Belady's anomaly?"

You should know that FIFO also does not suffer from Belady's anomaly all the time. Only some times it suffers.
But It does not follow stack property only in some cases also means you have to consider it as "suffers from Belady's anomaly."

1 votes
1 votes

I have got the jest of question but there is clearly mentioned “random page replacement algo suffers from Belady’s anomaly”. random algo may/maynot take FIFO pattern. 

Its NOT mentioned  “random page replacement algo may suffer from Belady’s anomaly” 

 

Thus according to me the answer should be option “D” both false.

But if mentioned that Algo may suffer  then option “B” is true.

0 votes
0 votes

In the  Random page replacement algorithm  there is chance of Belady's anomaly my occurs we don't know system may randomly replace those page which is brought in frame  , so that it can Belady's anomaly

and we know that LRU , we replace those page which is least recent page that why's B is correct answer

Answer:

Related questions

24 votes
24 votes
3 answers
2
48 votes
48 votes
7 answers
3
Arjun asked Feb 14, 2017
16,773 views
Threads of a process shareglobal variables but not heapheap but not global variablesneither global variables nor heapboth heap and global variables