Belady’s Anomaly in Page Replacement

🔹 Definition

Belady’s Anomaly is a phenomenon where:

Increasing the number of page frames increases the number of page faults instead of decreasing them.

This behavior is unexpected, because normally adding more memory should reduce page faults.

Belady’s anomaly mainly occurs in:

• FIFO page replacement

It does not occur in:

• Optimal

• LRU

---

Example Demonstrating Belady’s Anomaly

Reference String

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

---

🔹 Case 1: 3 Page Frames (FIFO)

Reference	Frames	Page Fault
1	1	-
2	1 2	-
3	1 2 3	Fault
4	2 3 4	Fault
1	3 4 1	Fault
2	4 1 2	Fault
5	1 2 5	Fault
1	1 2 5	Hit
2	1 2 5	Hit
3	2 5 3	Fault
4	5 3 4	Fault
5	5 3 4	Hit

✅ Total Page Faults = 9

---

🔹 Case 2: 4 Page Frames (FIFO)

Reference	Frames	Page Fault
1	1	-
2	1 2	-
3	1 2 3	-
4	1 2 3 4	Fault
1	1 2 3 4	Hit
2	1 2 3 4	Hit
5	2 3 4 5	Fault
1	3 4 5 1	Fault
2	4 5 1 2	Fault
3	5 1 2 3	Fault
4	1 2 3 4	Fault
5	2 3 4 5	Fault

❗ Total Page Faults = 10

---

⚠️ Observation

Frames	Page Faults
3 Frames	9
4 Frames	10

Even though we added more memory, the number of page faults increased.

This is Belady’s Anomaly.

---

Why It Happens

FIFO removes pages based only on arrival time, not usage.

A page that is heavily used may still be removed simply because it was loaded earlier.

Adding more frames changes the eviction order, sometimes causing more faults.

---

 Algorithms Affected

Algorithm	Belady’s Anomaly
FIFO	Yes
Random	Possible
LRU	No
Optimal	No
LFU	Rare

---

Key Takeaway

Belady’s Anomaly shows that:

Some page replacement algorithms behave counter-intuitively, where adding memory can worsen performance.

This is why modern systems prefer algorithms like LRU or its approximations.