GATE CSE 2017 Set 1 | Question: 40

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:

• $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?

• A. $S_1$ is true, $S_2$ is true
• B. $S_1$ is true, $S_2$ is false
• C. $S_1$ is false, $S_2$ is true
• D. $S_1$ is false, $S_2$ is false

Comments

LIFO WILL not SUFFER FROM BELADY ANOMLY

---

Hello Sir, i don’t understand that how we can say “fifo suffers belady’s anomaly”

It seems like fifo always suffer belady's anomaly not like fifo may suffer belady’s  anomaly.

Please review.

---

it there is always unique new frame comes as a request and  no of frames are constant then LRU will work like FIFO then Belady anomaly possible here

1,2,3,4,5,6,7,8,9,10

1/4/7

2/5/8

3/6/9

Please correct me if i am wrong. ?

Answer 1

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.

Comments

@shweta

how can u say most people don't know..?

Infact ,everyone knows this, it is quite simple.

---

well explanation @ kanti kumar

---

I think here the answer should be D and not B . Because if there any Random page replacement algo is given then it is not necessary that it point to FIFO it may refer to  LRU algo which not suffers from belady anomaly. kindly check it once.  (as when there is a may be or may not be case then we cannot mark such cases)

Answer 2

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."

Comments

God for a reason.

---

Means if we say that “ Random page algorithm does not suffer Belady’s Anomaly then it will be also true”.  both can be true in some aspect but at a time only one is true. I have some confusion, regrading this statement to be true.

Answer 3

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.

Answer 4

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