What is Belady’s Anomaly?
Learn what Belady’s Anomaly is, why FIFO paging can get worse with more frames, and how the stack property prevents it.
Expected Interview Answer
Belady’s Anomaly is the counter-intuitive situation where increasing the number of page frames available to a process actually increases the number of page faults it experiences, instead of reducing them, under certain page replacement algorithms such as FIFO.
Under most replacement policies, giving a process more physical frames should never make things worse, since more resident pages means fewer evictions. FIFO breaks this expectation because it evicts strictly by arrival time, ignoring how recently or frequently a page is actually used, so adding a frame can shift which pages get evicted in a way that causes a previously cached page to be thrown out earlier and re-faulted later. Belady proved that algorithms possessing the stack property — meaning the set of pages resident with k frames is always a subset of the set resident with k+1 frames — are immune to this anomaly, and LRU and Optimal both satisfy the stack property while FIFO does not. This is why interviewers use it to test whether a candidate actually understands that intuitive resource scaling can fail for algorithms that lack a formal stack property, not just as a FIFO trivia fact.
- Exposes why FIFO is a weak page replacement choice in practice
- Introduces the stack property that guarantees monotonic behavior
- Explains why LRU and Optimal never suffer this anomaly
- Sharpens reasoning about resource scaling assumptions in systems design
AI Mentor Explanation
Belady’s Anomaly is like a team adding an extra reserve slot to its matchday squad using strict arrival-order rules for who gets dropped: a player who joined the squad list early gets dropped to make room for the new slot’s arrival pattern, even though that player was about to bat well. Later the team needs that dropped player back and has to recall them at cost, meaning more squad changes happened with the extra slot than without it. A selection rule based on actual recent batting form, not arrival order, would never cause this backwards result.
Step-by-Step Explanation
Step 1
Baseline run
Run a reference string against FIFO with k frames and record the page fault count.
Step 2
Increase frames
Run the identical reference string against FIFO with k+1 frames.
Step 3
Compare fault counts
Observe that the k+1 run can produce MORE faults than the k run, violating the intuitive expectation.
Step 4
Diagnose the cause
Trace it to FIFO lacking the stack property — its resident set at k is not always a subset of its resident set at k+1.
What Interviewer Expects
- A precise definition: more frames can increase faults under FIFO
- Knowledge that LRU and Optimal are immune to the anomaly
- Understanding of the stack property as the underlying reason
- Ability to walk through a small reference string demonstrating it
Common Mistakes
- Claiming the anomaly happens under LRU (it does not)
- Thinking more memory always strictly helps performance
- Not being able to explain the stack property
- Confusing Belady's Anomaly with thrashing, which is a different failure mode
Best Answer (HR Friendly)
“Belady’s Anomaly is the surprising discovery that under some page replacement rules, like FIFO, giving a program more memory can actually cause more slowdowns instead of fewer, because the rule for deciding what to remove is based on arrival order rather than actual usefulness. It matters because it shows that naive assumptions like more resources are always better can break down, and it is why smarter algorithms like LRU were designed to avoid this trap entirely.”
Code Example
#include <stdio.h>
/* returns number of page faults for FIFO with given frame count */
int fifo_faults(int refs[], int n, int frames) {
int mem[frames];
for (int i = 0; i < frames; i++) mem[i] = -1;
int front = 0, faults = 0;
for (int i = 0; i < n; i++) {
int present = 0;
for (int j = 0; j < frames; j++)
if (mem[j] == refs[i]) { present = 1; break; }
if (!present) {
mem[front] = refs[i]; /* replace oldest-loaded page */
front = (front + 1) % frames;
faults++;
}
}
return faults;
}
int main(void) {
int refs[] = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5};
int n = sizeof(refs) / sizeof(refs[0]);
printf("Faults with 3 frames: %d\n", fifo_faults(refs, n, 3));
printf("Faults with 4 frames: %d\n", fifo_faults(refs, n, 4));
/* the 4-frame run can report MORE faults than the 3-frame run */
return 0;
}Follow-up Questions
- What is the stack property and why does LRU satisfy it?
- Why is Optimal replacement immune to this anomaly?
- Can you construct a small reference string that triggers the anomaly under FIFO?
- How does this anomaly influence real-world choices of replacement algorithm?
MCQ Practice
1. Belady’s Anomaly describes a situation where?
The anomaly is specifically that more frames can paradoxically cause more faults under algorithms like FIFO.
2. Which property, if satisfied, guarantees immunity to this anomaly?
Algorithms whose resident set at k frames is always a subset of the set at k+1 frames satisfy the stack property and cannot exhibit the anomaly.
3. Which replacement algorithm is known to be susceptible to this anomaly?
FIFO evicts purely by arrival order and lacks the stack property, making it the classic algorithm that exhibits the anomaly.
Flash Cards
What is Belady’s Anomaly? — More page frames can increase page faults under FIFO replacement, contrary to intuition.
What property makes an algorithm immune to it? — The stack property — resident pages at k frames are always a subset of those at k+1 frames.
Which algorithms are immune? — LRU and Optimal both satisfy the stack property and are immune.
Which algorithm is the classic example that suffers from it? — FIFO (First-In-First-Out) page replacement.