Question

'Belady’s Anomaly' refers to the phenomenon where the page fault rate increases as the number of allocated page frames increases. This is observed in which page replacement algorithm?

• A. Optimal (OPT)
• B. Least Recently Used (LRU)
• C. First-In-First-Out (FIFO)
• D. Stack-based algorithms

Hint:

To remember which algorithms are safe: Think of "Stack" algorithms. If an algorithm ranks pages by a fixed priority that doesn't change when frames are added (like time of last use or distance to next use), it is immune to Belady's Anomaly.

Answer 1

The Correct Option is C

Concept:
In virtual memory management, it is logically expected that providing more physical memory (page frames) to a process should reduce the frequency of page faults. However, Laszlo Belady discovered in 1969 that certain page replacement algorithms behave counter-intuitively. This anomaly is specifically tied to the structure of the algorithm. Algorithms that do not possess the "Stack Property" are susceptible to this anomaly.

Step 1: Understanding Stack Algorithms vs. Non-Stack Algorithms.
A "Stack Algorithm" is one where the set of pages in memory for $n$ frames is always a subset of the pages in memory for $n+1$ frames.
• LRU (Least Recently Used): Since it keeps the most recently used pages, the pages in a 3-frame setup will always be present in a 4-frame setup.
• Optimal (OPT): Uses future knowledge; it also obeys the stack property.
• FIFO (First-In-First-Out): It replaces the oldest page regardless of its frequency or recency of use. It does not follow the stack property.

Step 2: Why FIFO fails.
In FIFO, the "oldest" page might be a page that is needed immediately again. When we increase frames, the timing of which page is "oldest" shifts in a way that can cause a previously "safe" page to be evicted just before it is needed.

Step 3: Verification through Example.
Consider the reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.
• With 3 frames: The system results in 9 page faults.
• With 4 frames: The system results in 10 page faults. Since page faults increased (9 to 10) as frames increased (3 to 4), this confirms Belady's Anomaly in FIFO.