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

Belady's anomaly definition : Increasing the number of page frames may increase the number of page faults.

Thus we say FIFO suffers from Belady's anomaly. Stack based algo such as LRU and Optimal need not.

Random Page Replacement Algorithm : It may suffer from Belady's anomaly if it behaves as FIFO. For example, Let us consider a reference string in FIFO which leads to belady's anomaly. The same input is provided to Random Page Replacement algorithm and it decides to behave as LRU which will not lead to increase in page faults. Thus according to my thought process "may" word is important which is missing. Similar to the State halting problem of TOC. Will the machine reach state q on some input w?

Let page numbers be 1,2,3, 4 be equivalent to symbols in our Alphabet. Set of all string possible over an Alphabet will be nothing but our reference string for page access.

Let us design a Turing Machine FIFO which will produce two output 

- YES for all the strings which suffer from Belady's anomaly on increase in no of frames

- NO for all the strings which does not suffer from Belady's anomaly on increase in no of frames

The above two ans are possible since Set of all strings over an alphabet are countable.

Now Lets provide those strings as input to a Random Replacement Page Algorithm on which FIFO machine says YES and ask the question Will there be a string on which the machine will work as FIFO? Reducible to State visiting problem and hence Undecidable..

NOTE: The may word included in definition of Belady's anomaly is bounded with the phrase for some strings may increase. Just like the concept of first oder logic.

Option D) Should be correct.

Comments

I think "may" word is included in belody's anamoly definition itself, if we see its definition as given above also.  Definition itself means page fault may increase but not everytime.

So i think b is the correct answer

---

@harkirat31 that is where I want to draw everyone's attention. The may word included in the definition of Belady's anomaly is bounded with the increase in the number of frames.

---

@Arjun Sir, Please check my solution once.

---

May is already included in definition. So i think there is no need to say again explicitly that may suffer from belody's anamoly .

As belody anomaly itself say page fault may increase . 

If we use may before belody's anamoly, it will be like saying that there may be chance that page fault may increase with increse in page frames. Using may two times 

---

@harkirat31 think over this - How did we know that  FIFO suffers from Belady's anomaly? We took a string and observed the beahviour. A string to conclude. It is decidable. For YES case it says YES and for no case it says NO. Can u do the same with Random Replacement Algo?

---

way too much deep..thinking..i can assure you this much analysis will not be pit up by professors! so simply random can be fifo so can be belady so answer will be B(though i want it to be D)