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.