Coursify

Understanding Belady's Anomaly in Operating Systems

Understanding Belady's Anomaly in Operating Systems

Verified Sources
May 28, 2026

In modern operating systems, virtual memory allows programs to execute even if they exceed physical RAM capacity . When a program references a page not currently mapped in RAM, a page fault is triggered . The operating system must then allocate one of the physical page frames to load that page from disk .

If all frames are occupied, a page replacement algorithm is invoked to select a "victim" page to evict .

Historically, computer scientists assumed that allocating more physical memory (more page frames) to a process would always decrease (or at least maintain) the number of page faults . However, in 1969, computer scientist László Bélády proved this assumption wrong . He demonstrated that under certain conditions and specific replacement algorithms, increasing the number of page frames can counterintuitively cause an increase in the number of page faults . This phenomenon is known as Belady's Anomaly (or the FIFO anomaly) .

Footnotes

  1. Bélády's Anomaly - Wikipedia - Detailed historical context and mathematical properties of non-stack-based memory management. ↩ ↩2 ↩3 ↩4 ↩5 ↩6

  2. Belady's Anomaly in OS: Why More Frames Mean More Faults - Unwired Learning guide detailing the history, affected algorithms, and the role of Laszlo Belady in 1969. ↩

  3. BELADY'S ANOMALY : Explained - A comprehensive explanation of Belady's anomaly with the classic 3 vs 4 frame example. ↩

Belady's Anomaly in Operating Systems

The FIFO Pitfall

While FIFO is simple to implement using a queue, its lack of consideration for page access frequency or recency makes it highly susceptible to performance degradation and Belady's Anomaly .

Footnotes

  1. BELADY'S ANOMALY : Explained - A comprehensive explanation of Belady's anomaly with the classic 3 vs 4 frame example. ↩

Tracing Belady's Anomaly (FIFO with 3 vs 4 Frames)

  1. 1
    Step 1

    We will use the classic reference string: 1,2,3,4,1,2,5,1,2,3,4,51, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. We will trace the execution under the First-In-First-Out (FIFO) replacement policy for both 33 and 44 memory frames .

    Footnotes

    1. BELADY'S ANOMALY : Explained - A comprehensive explanation of Belady's anomaly with the classic 3 vs 4 frame example. ↩

  2. 2
    Step 2

    With 33 frames, the memory states evolve as follows:

    • 11 -> [1,−,−][1, -, -] (Fault)
    • 22 -> [1,2,−][1, 2, -] (Fault)
    • 33 -> [1,2,3][1, 2, 3] (Fault)
    • 44 -> [4,2,3][4, 2, 3] (Fault, 11 replaced)
    • 11 -> [4,1,3][4, 1, 3] (Fault, 22 replaced)
    • 22 -> [4,1,2][4, 1, 2] (Fault, 33 replaced)
    • 55 -> [5,1,2][5, 1, 2] (Fault, 44 replaced)
    • 11 -> [5,1,2][5, 1, 2] (Hit)
    • 22 -> [5,1,2][5, 1, 2] (Hit)
    • 33 -> [5,3,2][5, 3, 2] (Fault, 11 replaced)
    • 44 -> [5,3,4][5, 3, 4] (Fault, 22 replaced)
    • 55 -> [5,3,4][5, 3, 4] (Hit)

    Total Page Faults with 3 Frames = 9 .

    Footnotes

    1. Belady's Anomaly in OS - Testbook - Testbook educational article showing the mathematical proof and step-by-step trace of FIFO. ↩

  3. 3
    Step 3

    With 44 frames, the memory states evolve as follows:

    • 11 -> [1,−,−,−][1, -, -, -] (Fault)
    • 22 -> [1,2,−,−][1, 2, -, -] (Fault)
    • 33 -> [1,2,3,−][1, 2, 3, -] (Fault)
    • 44 -> [1,2,3,4][1, 2, 3, 4] (Fault)
    • 11 -> [1,2,3,4][1, 2, 3, 4] (Hit)
    • 22 -> [1,2,3,4][1, 2, 3, 4] (Hit)
    • 55 -> [5,2,3,4][5, 2, 3, 4] (Fault, 11 replaced)
    • 11 -> [5,1,3,4][5, 1, 3, 4] (Fault, 22 replaced)
    • 22 -> [5,1,2,4][5, 1, 2, 4] (Fault, 33 replaced)
    • 33 -> [5,1,2,3][5, 1, 2, 3] (Fault, 44 replaced)
    • 44 -> [4,1,2,3][4, 1, 2, 3] (Fault, 55 replaced)
    • 55 -> [4,5,2,3][4, 5, 2, 3] (Fault, 11 replaced)

    Total Page Faults with 4 Frames = 10 .

    Footnotes

    1. Belady's Anomaly in OS - Testbook - Testbook educational article showing the mathematical proof and step-by-step trace of FIFO. ↩

  4. 4
    Step 4

    Comparing the two scenarios, we observe that increasing the number of frames from 33 to 44 caused the total page faults to increase from 99 to 1010. This counterintuitive outcome is the exact manifestation of Belady's Anomaly .

    Footnotes

    1. BELADY'S ANOMALY : Explained - A comprehensive explanation of Belady's anomaly with the classic 3 vs 4 frame example. ↩

Page Faults vs. Frame Allocation

Comparison of page faults for FIFO with 3 vs 4 frames on the reference string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Stack Immunity

To completely eliminate Belady's Anomaly, design your virtual memory system to use stack algorithms like LRU or Optimal Page Replacement .

Footnotes

  1. Belady's Anomaly Karim City College Document - Academic analysis of stack-based page replacement algorithms and the inclusion property. ↩

Non-Stack Algorithms (e.g., FIFO, Random)

  • Definition: Do not satisfy the inclusion property .
  • Belady's Anomaly: Susceptible. Increasing frames can increase page faults .
  • Subset Rule: The set of pages in memory with NN frames is not guaranteed to be a subset of the pages in memory with N+1N+1 frames .
  • Example Trace: With N=3N=3, memory may contain {1,2,5}\{1, 2, 5\}, while with N=4N=4, memory contains {1,3,4,5}\{1, 3, 4, 5\}. Here, {1,2,5}⊈{1,3,4,5}\{1, 2, 5\} \not\subseteq \{1, 3, 4, 5\} .

Footnotes

  1. Belady's Anomaly Karim City College Document - Academic analysis of stack-based page replacement algorithms and the inclusion property. ↩ ↩2 ↩3 ↩4

Deep Dive into Page Replacement Mechanics

Knowledge Check

Question 1 of 3
Q1Single choice

Which of the following page replacement algorithms is susceptible to Belady's Anomaly?

Explore Related Topics

1

Floating Point Data Type in Computer Organisation and Architecture

2

Paging with Translation Lookaside Buffer (TLB) Scheme

3

Thrashing in Operating Systems: Meaning, Causes, Occurrence, and Prevention

Browse all research articles