Question

Which page replacement algorithm suffers with Belady's anomaly?

• A. Least Recently Used (LRU)
• B. Most Frequently Used (MFU)
• C. Optimal
• D. First-In First-Out (FIFO)

Hint:

Belady's Anomaly occurs in FIFO but never occurs in stack algorithms such as LRU and Optimal.

Answer 1

The Correct Option is D

Concept: Belady's Anomaly is a phenomenon where increasing the number of page frames results in an increase in the number of page faults. Normally, increasing memory should decrease page faults.

Step 1: Understand FIFO page replacement.
FIFO removes the page that entered memory earliest. It does not consider:
• Recent usage
• Future usage Thus it may remove frequently needed pages.

Step 2: Observe Belady's anomaly.
For certain reference strings, \[ \text{Page Faults with 4 Frames} > \text{Page Faults with 3 Frames} \] which is counterintuitive. This behavior is called Belady's anomaly.

Step 3: Check other algorithms.
Stack algorithms such as: \[ \text{LRU} \] and \[ \text{Optimal} \] do not suffer from Belady's anomaly.

Step 4: Select the answer.
Therefore, \[ \boxed{\text{FIFO}} \] suffers from Belady's anomaly.