Question

Which page replacement algorithm suffers from Belady's anomaly?

• A. Optimal
• B. FIFO
• C. LRU
• D. LFU

Hint:

Belady's Anomaly is a key concept to remember about the FIFO page replacement algorithm. It's one of the main reasons why FIFO, despite its simplicity, is rarely used in modern operating systems.

Answer 1

The Correct Option is B

Belady's Anomaly is a phenomenon in virtual memory management where increasing the number of page frames allocated to a process can, counter-intuitively, increase the number of page faults.
This anomaly occurs because the page replacement algorithm evicts a page that will be needed again soon, which a larger memory size might have kept.
Let's analyze the algorithms:
(A) Optimal: This algorithm replaces the page that will not be used for the longest period of time. It is the theoretical best and does not suffer from Belady's anomaly.
(B) FIFO (First-In, First-Out): This algorithm replaces the page that has been in memory the longest. It is the classic example of an algorithm that suffers from Belady's anomaly because the oldest page might be a frequently used page.
(C) LRU (Least Recently Used): This algorithm replaces the page that has not been used for the longest amount of time. It and other stack-based algorithms do not suffer from Belady's anomaly.
(D) LFU (Least Frequently Used): This algorithm replaces the page that has been used the fewest number of times. It also does not suffer from the anomaly.
Therefore, FIFO is the algorithm that suffers from Belady's anomaly.