CoursifyCoursify

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** [^4].
  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** [^4].
  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}ot⊆{1,3,4,5}\{1, 2, 5\} ot\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

Various Addressing Modes of 8051 Microcontroller

The 8051 microcontroller provides multiple addressing modes that define how an instruction identifies the location or value of its operand.

  • Immediate (#data) – constant value encoded in the instruction, used for loading fixed numbers.
  • Register (Rn) – operand resides in CPU registers R0‑R7 (or A/B), giving the shortest and fastest code.
  • Direct (addr) – 8‑bit address is part of the opcode, accessing internal RAM or SFRs directly.
  • Register indirect (@R0, @R1, @DPTR) – a register holds the operand’s address, enabling pointer‑like traversal of memory.
  • Indexed (@A+DPTR or @A+PC) – adds the accumulator to DPTR or PC for table look‑ups in code memory; branch modes (relative, absolute, long) extend this concept for short, page‑limited, and full‑range jumps.
2

Inverted Page Table

3

The Banker's Algorithm: Deadlock Avoidance in Operating Systems

The Banker's Algorithm is a deadlock‑avoidance method that keeps a system in a safe state by checking each resource request against the maximum declared needs of processes.

  • Maintains Available, Max, Allocation, and Need matrices, where Need[i][j]=Max[i][j]−Allocation[i][j]\text{Need}[i][j]=\text{Max}[i][j]-\text{Allocation}[i][j].
  • The Safety Algorithm uses vectors Work and Finish to find an execution order; if all processes finish, the state is safe.
  • The Resource‑Request Algorithm simulates allocation, runs the safety check, and commits only if the resulting state remains safe.
  • Time complexity of the safety check is O(m×n2)O(m \times n^{2}).
  • In practice the algorithm is rarely used because processes must predeclare maximum needs and the algorithm’s overhead is high.
Research more with Coursify
Chat with Kiro