Belady's Anomaly and Why LRU and Optimal Page Replacement Avoid It

Verified Sources

May 27, 2026

Virtual memory relies on paging and page replacement to manage limited physical memory. A page fault occurs when the referenced page is absent and must be loaded into a frame.2

Belady's anomaly is the counterintuitive case in which increasing the number of available page frames causes the number of page faults to increase for the same reference string.2 This was historically surprising because one would expect additional memory to weakly improve performance, not degrade it.2

The anomaly is most famously associated with FIFO page replacement, but it does not occur in LRU or Optimal replacement because those are [stack algorithms]{def="Algorithms whose memory contents with $n$ frames are always a subset of those with $n+1$ frames"} satisfying the inclusion property.2

Formally, if $M(n,t)$ is the set of pages in memory after time $t$ with $n$ frames, then a stack algorithm satisfies:

M(n,t) \subseteq M(n+1,t) \quad \text{for all } t

When this property holds, adding one more frame cannot remove any page that was already resident with fewer frames, so the page-fault count cannot increase.2

Bélády's anomaly - Wikipedia - Defines the anomaly, its historical context, and notes unbounded constructions. ↩ ↩² ↩³
CSE 120 Principles of Operating Systems - University lecture notes explaining Optimal replacement and paging concepts. ↩
Operating System - Belady's Anomaly - TutorialsPoint - Summarizes the inclusion property and identifies LRU and Optimal as stack algorithms. ↩ ↩² ↩³
Page replacement (CS 4410, Summer 2015) - Cornell lecture notes describing FIFO, LRU, Optimal, and the classic anomaly example. ↩
CS4411 Operating Systems Homework 2 Solutions - Formal discussion of the inclusion property and why stack algorithms cannot exhibit Belady's anomaly. ↩ ↩²

Belady's Anomaly in FIFO Page Replacement with Example

Key Misconception

Belady's anomaly does not mean more frames always cause more faults. It means that for some reference strings and some non-stack algorithms, more frames can paradoxically increase faults.2

Bélády's anomaly - Wikipedia - Defines the anomaly, its historical context, and notes unbounded constructions. ↩
Operating System - Belady's Anomaly - TutorialsPoint - Summarizes the inclusion property and identifies LRU and Optimal as stack algorithms. ↩

To understand the anomaly concretely, consider the classic reference string:

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

For FIFO, authoritative lecture notes and teaching resources report that this sequence produces 9 page faults with 3 frames but 10 page faults with 4 frames.2 That is the anomaly.

The reason is structural, not accidental. FIFO evicts the page that has been in memory the longest, regardless of whether it was used recently or will be needed soon. Thus FIFO uses arrival time as its priority rule, and that rule changes the memory content in a way that can break subset inclusion between the $n$ -frame and $(n+1)$ -frame executions.2

A concise comparison is below:

Algorithm	Replacement criterion	Stack property?	Can suffer Belady's anomaly?
FIFO	Oldest loaded page	No	Yes2
LRU	Least recently used page	Yes	No2
Optimal	Page used farthest in the future	Yes	No2

Page replacement (CS 4410, Summer 2015) - Cornell lecture notes describing FIFO, LRU, Optimal, and the classic anomaly example. ↩
Belady's Anomaly in Page Replacement Algorithms - GeeksforGeeks - Provides the standard FIFO example and explains why stack-based algorithms avoid the anomaly. ↩ ↩² ↩³ ↩⁴ ↩⁵
Operating System - Belady's Anomaly - TutorialsPoint - Summarizes the inclusion property and identifies LRU and Optimal as stack algorithms. ↩ ↩² ↩³
Bélády's anomaly - Wikipedia - Defines the anomaly, its historical context, and notes unbounded constructions. ↩ ↩²
CS4411 Operating Systems Homework 2 Solutions - Formal discussion of the inclusion property and why stack algorithms cannot exhibit Belady's anomaly. ↩ ↩² ↩³
CSE 120 Principles of Operating Systems - University lecture notes explaining Optimal replacement and paging concepts. ↩ ↩²

Classic Belady's Anomaly Example

FIFO page faults for the reference string $1,2,3,4,1,2,5,1,2,3,4,5$

How Belady's Anomaly Appears in FIFO

1
Step 1
The first few distinct page references fill the available frames, producing compulsory faults. With 3 frames, pages $1,2,3$ fill memory; with 4 frames, pages $1,2,3,4$ do so.

Footnotes

Belady's Anomaly in Page Replacement Algorithms - GeeksforGeeks - Provides the standard FIFO example and explains why stack-based algorithms avoid the anomaly. ↩
2
Step 2
Whenever a fault occurs and memory is full, the page that entered earliest is evicted, regardless of recency or future usefulness.

Footnotes

Belady's Anomaly in Page Replacement Algorithms - GeeksforGeeks - Provides the standard FIFO example and explains why stack-based algorithms avoid the anomaly. ↩
3
Step 3
Because the 3-frame and 4-frame runs maintain different queue orders, the set of pages held with 3 frames is not guaranteed to be a subset of the set held with 4 frames.2

Footnotes

Operating System - Belady's Anomaly - TutorialsPoint - Summarizes the inclusion property and identifies LRU and Optimal as stack algorithms. ↩

CS4411 Operating Systems Homework 2 Solutions - Formal discussion of the inclusion property and why stack algorithms cannot exhibit Belady's anomaly. ↩
4
Step 4
The altered queue order in the 4-frame execution can evict a page that the 3-frame execution still keeps, causing a later fault that would not have occurred with fewer frames.2

Footnotes

Operating System - Belady's Anomaly - TutorialsPoint - Summarizes the inclusion property and identifies LRU and Optimal as stack algorithms. ↩

Belady's Anomaly in Page Replacement Algorithms - GeeksforGeeks - Provides the standard FIFO example and explains why stack-based algorithms avoid the anomaly. ↩
5
Step 5
For the classic string, the 3-frame FIFO execution yields 9 faults, whereas the 4-frame execution yields 10 faults, establishing the anomaly.2

Footnotes

Page replacement (CS 4410, Summer 2015) - Cornell lecture notes describing FIFO, LRU, Optimal, and the classic anomaly example. ↩

Belady's Anomaly in Page Replacement Algorithms - GeeksforGeeks - Provides the standard FIFO example and explains why stack-based algorithms avoid the anomaly. ↩

A more conceptual way to see the problem is through inclusion property.

If an algorithm is well behaved in the stack sense, then after each reference, the memory contents with 3 frames should be contained inside the memory contents with 4 frames. FIFO does not guarantee this.2 In the classic example, the 3-frame execution and 4-frame execution drift apart because page age is measured from load time rather than from actual utility.

This matters because paging performance depends on locality, especially temporal locality.2 FIFO ignores locality; LRU tries to exploit recent past, and Optimal uses exact future knowledge.2

Operating System - Belady's Anomaly - TutorialsPoint - Summarizes the inclusion property and identifies LRU and Optimal as stack algorithms. ↩
CS4411 Operating Systems Homework 2 Solutions - Formal discussion of the inclusion property and why stack algorithms cannot exhibit Belady's anomaly. ↩
Belady's Anomaly in Page Replacement Algorithms - GeeksforGeeks - Provides the standard FIFO example and explains why stack-based algorithms avoid the anomaly. ↩ ↩²
Page replacement (CS 4410, Summer 2015) - Cornell lecture notes describing FIFO, LRU, Optimal, and the classic anomaly example. ↩ ↩²
CSE 120 Principles of Operating Systems - University lecture notes explaining Optimal replacement and paging concepts. ↩

Exam Shortcut

If a page replacement algorithm is a stack algorithm, it cannot exhibit Belady's anomaly. LRU and Optimal are the standard examples.2

Operating System - Belady's Anomaly - TutorialsPoint - Summarizes the inclusion property and identifies LRU and Optimal as stack algorithms. ↩
CS4411 Operating Systems Homework 2 Solutions - Formal discussion of the inclusion property and why stack algorithms cannot exhibit Belady's anomaly. ↩

Why LRU Does Not Suffer from Belady's Anomaly

LRU orders pages by recency of use, not by time of entry. After each reference, pages can be imagined as arranged in a stack from most recently used at the top to least recently used at the bottom.2 With $n$ frames, memory contains the top $n$ pages of this recency stack. With $n+1$ frames, memory contains the top $n+1$ pages. Therefore, the $n$ -frame contents are automatically a subset of the $(n+1)$ -frame contents.

That is exactly the inclusion property:

M_{\text{LRU}}(n,t) \subseteq M_{\text{LRU}}(n+1,t)

for every time $t$ .

Since any hit with $n$ frames must also be a hit with $n+1$ frames under subset inclusion, page faults cannot increase as frames increase. Hence LRU cannot exhibit Belady's anomaly.2

The intuition is that adding a frame to LRU simply allows one additional less-recent page to be retained. It does not force the algorithm to discard one of the pages that would have been kept with fewer frames.

Page replacement (CS 4410, Summer 2015) - Cornell lecture notes describing FIFO, LRU, Optimal, and the classic anomaly example. ↩
CS4411 Operating Systems Homework 2 Solutions - Formal discussion of the inclusion property and why stack algorithms cannot exhibit Belady's anomaly. ↩ ↩² ↩³ ↩⁴ ↩⁵
Operating System - Belady's Anomaly - TutorialsPoint - Summarizes the inclusion property and identifies LRU and Optimal as stack algorithms. ↩

Why LRU Is Safe

Why Optimal Page Replacement Does Not Suffer from Belady's Anomaly

Optimal page replacement—also called OPT or MIN—chooses the page that will not be used for the longest time in the future.2 Bélády showed that this policy minimizes the number of page faults for a fixed reference string and frame count.2

Optimal is also a stack algorithm.2 Conceptually, if one ranks resident pages by how soon they will next be used, then the set of pages retained with $n$ frames is contained within the set retained with $n+1$ frames. Adding a frame means the algorithm can keep one more page without dropping any page that would have been selected among the best $n$ future candidates.2

Thus:

M_{\text{OPT}}(n,t) \subseteq M_{\text{OPT}}(n+1,t)

and therefore page faults under OPT are monotonically non-increasing as frame count grows.3

The difference from FIFO is essential:

FIFO asks, "Which page has been here longest?"
LRU asks, "Which page was used least recently?"
OPT asks, "Which page will be needed farthest in the future?"3

Only the latter two induce the stack property in the standard discussion here.2

CSE 120 Principles of Operating Systems - University lecture notes explaining Optimal replacement and paging concepts. ↩ ↩² ↩³ ↩⁴
Page replacement (CS 4410, Summer 2015) - Cornell lecture notes describing FIFO, LRU, Optimal, and the classic anomaly example. ↩ ↩² ↩³
Operating System - Belady's Anomaly - TutorialsPoint - Summarizes the inclusion property and identifies LRU and Optimal as stack algorithms. ↩ ↩² ↩³ ↩⁴
CS4411 Operating Systems Homework 2 Solutions - Formal discussion of the inclusion property and why stack algorithms cannot exhibit Belady's anomaly. ↩ ↩² ↩³ ↩⁴
Belady's Anomaly in Page Replacement Algorithms - GeeksforGeeks - Provides the standard FIFO example and explains why stack-based algorithms avoid the anomaly. ↩

FIFO evicts the oldest loaded page. This ignores both recent use and future need, so the memory contents with $n$ frames need not be a subset of those with $n+1$ frames. Hence Belady's anomaly is possible.2

Bélády's anomaly - Wikipedia - Defines the anomaly, its historical context, and notes unbounded constructions. ↩
Belady's Anomaly in Page Replacement Algorithms - GeeksforGeeks - Provides the standard FIFO example and explains why stack-based algorithms avoid the anomaly. ↩

Conceptual Roadmap of the Belady's Anomaly Discussion

Demand paging

Step 1

A process references pages; absent pages cause page faults and must be loaded into frames.2"

Bélády's anomaly - Wikipedia - Defines the anomaly, its historical context, and notes unbounded constructions. ↩
CSE 120 Principles of Operating Systems - University lecture notes explaining Optimal replacement and paging concepts. ↩

Replacement decision

Step 2

When all frames are occupied, the system must choose a victim page according to a replacement policy.2"

CSE 120 Principles of Operating Systems - University lecture notes explaining Optimal replacement and paging concepts. ↩
Belady's Anomaly in Page Replacement Algorithms - GeeksforGeeks - Provides the standard FIFO example and explains why stack-based algorithms avoid the anomaly. ↩

Belady's observation

Step 3

For FIFO and certain traces, more frames can produce more page faults, contradicting naive expectations.3"

Bélády's anomaly - Wikipedia - Defines the anomaly, its historical context, and notes unbounded constructions. ↩
Page replacement (CS 4410, Summer 2015) - Cornell lecture notes describing FIFO, LRU, Optimal, and the classic anomaly example. ↩
Belady's Anomaly in Page Replacement Algorithms - GeeksforGeeks - Provides the standard FIFO example and explains why stack-based algorithms avoid the anomaly. ↩

Search for better policies

Step 4

This motivated the study of policies like LRU and OPT that align more closely with locality or future knowledge.2"

CSE 120 Principles of Operating Systems - University lecture notes explaining Optimal replacement and paging concepts. ↩
Page replacement (CS 4410, Summer 2015) - Cornell lecture notes describing FIFO, LRU, Optimal, and the classic anomaly example. ↩

Stack property insight

Step 5

Algorithms satisfying inclusion, such as LRU and OPT, cannot exhibit Belady's anomaly.2"

Operating System - Belady's Anomaly - TutorialsPoint - Summarizes the inclusion property and identifies LRU and Optimal as stack algorithms. ↩
CS4411 Operating Systems Homework 2 Solutions - Formal discussion of the inclusion property and why stack algorithms cannot exhibit Belady's anomaly. ↩

Formal Reasoning: Why Stack Algorithms Cannot Have the Anomaly

Suppose an algorithm satisfies the inclusion property for all times $t$ :

M(n,t) \subseteq M(n+1,t)

Now consider a page reference $p_t$ .

If $p_t \in M(n,t-1)$ , then the access is a hit with $n$ frames.
Because $M(n,t-1) \subseteq M(n+1,t-1)$ , the same page is also in memory with $n+1$ frames.
Therefore, every hit under $n$ frames is also a hit under $n+1$ frames.

Equivalently, the set of faults with $n+1$ frames is a subset of the faults with $n$ frames, so:

\text{Faults}(n+1) \le \text{Faults}(n)

Hence Belady's anomaly is impossible for any stack algorithm.

This proof explains both LRU and Optimal at once. What remains is to justify that they are stack algorithms:

LRU keeps the top $n$ most recently used pages.2
OPT keeps the best $n$ pages according to future next-use distance.2

FIFO lacks such frame-independent ranking and therefore can violate inclusion.2

CS4411 Operating Systems Homework 2 Solutions - Formal discussion of the inclusion property and why stack algorithms cannot exhibit Belady's anomaly. ↩ ↩² ↩³ ↩⁴
Page replacement (CS 4410, Summer 2015) - Cornell lecture notes describing FIFO, LRU, Optimal, and the classic anomaly example. ↩
CSE 120 Principles of Operating Systems - University lecture notes explaining Optimal replacement and paging concepts. ↩
Operating System - Belady's Anomaly - TutorialsPoint - Summarizes the inclusion property and identifies LRU and Optimal as stack algorithms. ↩
Belady's Anomaly in Page Replacement Algorithms - GeeksforGeeks - Provides the standard FIFO example and explains why stack-based algorithms avoid the anomaly. ↩

Common Questions and Edge Cases

Most Important Takeaway

Belady's anomaly is fundamentally about whether increasing frame count preserves previously retained pages. LRU and Optimal do preserve them through the inclusion property; FIFO does not.3

Operating System - Belady's Anomaly - TutorialsPoint - Summarizes the inclusion property and identifies LRU and Optimal as stack algorithms. ↩
CS4411 Operating Systems Homework 2 Solutions - Formal discussion of the inclusion property and why stack algorithms cannot exhibit Belady's anomaly. ↩
Belady's Anomaly in Page Replacement Algorithms - GeeksforGeeks - Provides the standard FIFO example and explains why stack-based algorithms avoid the anomaly. ↩

Final Synthesis

Belady's anomaly is a paradox of page replacement: more memory can lead to more page faults under certain non-stack algorithms, especially FIFO.2 The phenomenon arises because FIFO's victim choice depends on load order, not on a stable ranking of utility. As frame count changes, the memory contents can change in a non-nested way, and useful pages may disappear from the larger-memory execution.2

LRU and Optimal do not suffer from this problem because they satisfy the stack property. For LRU, memory with $n$ frames contains the top $n$ most recently used pages; for Optimal, memory with $n$ frames contains the best $n$ pages according to future use distance.3 In both cases, increasing the frame count only adds pages; it does not discard any page that would have been present with fewer frames.2

Therefore, if the question is why LRU and Optimal avoid Belady's anomaly, the precise answer is:

\boxed{\text{They are stack algorithms satisfying } M(n,t)\subseteq M(n+1,t)\text{ for all }t, \text{ so faults cannot increase with more frames.}}

Bélády's anomaly - Wikipedia - Defines the anomaly, its historical context, and notes unbounded constructions. ↩
Belady's Anomaly in Page Replacement Algorithms - GeeksforGeeks - Provides the standard FIFO example and explains why stack-based algorithms avoid the anomaly. ↩ ↩²
Operating System - Belady's Anomaly - TutorialsPoint - Summarizes the inclusion property and identifies LRU and Optimal as stack algorithms. ↩ ↩²
CSE 120 Principles of Operating Systems - University lecture notes explaining Optimal replacement and paging concepts. ↩
Page replacement (CS 4410, Summer 2015) - Cornell lecture notes describing FIFO, LRU, Optimal, and the classic anomaly example. ↩
CS4411 Operating Systems Homework 2 Solutions - Formal discussion of the inclusion property and why stack algorithms cannot exhibit Belady's anomaly. ↩ ↩²

Knowledge Check

Question 1 of 4

Q1Single choice

What is Belady's anomaly?

A condition where increasing page frames can increase page faults

A condition where decreasing page size reduces throughput

A scheduling problem caused by deadlocks

A cache issue where hits become misses after compaction

Explore Related Topics

Virtual Memory, Its Implementation, and the Role of the TLB

Virtual memory abstracts physical RAM by giving each process a large contiguous logical address space, implemented with paging, page tables, and a Translation Lookaside Buffer (TLB) that caches recent translations.

Provides protection, simplifies programming, enables demand paging and sharing of code/pages.
Virtual address = (VPN, offset); physical address = (PFN, offset) with VPN → PFN via TLB or page‑table walk.
Effective access time: $EAT = \alpha (m+\epsilon) + (1-\alpha)(2m+\epsilon)$ , so high TLB hit rate $\alpha$ is critical.
Multi‑level page tables reduce memory use for sparse address spaces.
TLB reach = (entries) × (page size); exceeding it causes TLB thrashing and performance loss.

Purpose of the Modify Bit in a Page Table

The modify (dirty) bit in a page‑table entry signals whether a page in RAM has been altered since it was loaded from its backing store, guiding the OS during page replacement.

If the bit is 0 the page is clean and can be discarded; if 1 it is dirty and must be written back before the frame is reused.
Hardware (or the MMU) sets the bit automatically on any write to the page.
Eviction cost:
$\text{Eviction cost}= \begin{cases}\text{read replacement page only}, & \text{modify}=0\\ \text{write old page} + \text{read replacement page}, & \text{modify}=1\end{cases}$
It works with other status bits (present, accessed) to support efficient replacement policies and avoid unnecessary disk I/O.

Compare and Contrast Between Linked and Indexed Disk Allocation Strategies

Linked and indexed allocation are non‑contiguous disk‑space strategies that both eliminate external fragmentation, but they differ in pointer placement and access performance.

Linked allocation stores a next‑block pointer in every data block, giving excellent sequential access and simple growth, yet random access costs $O(k)$ for the $k$ ‑th block.
Indexed allocation keeps all block addresses in a separate index block, enabling direct $O(1)$ lookup of any logical block but incurring higher metadata overhead, especially for small files.
Metadata risk is split: a broken link can truncate a linked file, while a corrupted index block can hide the entire file.
Indexed schemes scale better for large files using multilevel indexes; linked schemes remain flexible for unpredictable growth.
Modern systems favor indexed or hybrid inode‑based designs for their balanced random‑access capability and extensibility.

Research more with Coursify

Belady's Anomaly and Why LRU and Optimal Page Replacement Avoid It

Footnotes

Belady's Anomaly in FIFO Page Replacement with Example

Key Misconception

Footnotes

Footnotes

Classic Belady's Anomaly Example

How Belady's Anomaly Appears in FIFO

Footnotes

Footnotes

Footnotes

Footnotes

Footnotes

Footnotes

Exam Shortcut

Footnotes

Why LRU Does Not Suffer from Belady's Anomaly

Footnotes

Why LRU Is Safe

Why Optimal Page Replacement Does Not Suffer from Belady's Anomaly

Footnotes

Footnotes

Conceptual Roadmap of the Belady's Anomaly Discussion

Demand paging

Footnotes

Replacement decision

Footnotes

Belady's observation

Footnotes

Search for better policies

Footnotes

Stack property insight

Footnotes

Formal Reasoning: Why Stack Algorithms Cannot Have the Anomaly

Footnotes

Common Questions and Edge Cases

Most Important Takeaway

Footnotes

Final Synthesis

Footnotes

Knowledge Check

Explore Related Topics