Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Belady’s Anomaly?
3.
Why does Belady's Anomaly occur in First Come First Serve(FCFS)?
3.1.
Using First Come First Serve(FCFS)
4.
Why does Belady's Anomaly not occur in other Algorithms?
4.1.
Using Least Recently Used(LRU)
4.2.
Using Optimal Page Replacement(OPR)
4.3.
Most Recently Used(MRU)
5.
Belady’s Anomaly Graph
6.
Example of Belady’s Anomaly
7.
Why does Belady’s Anomaly occur?
8.
Features of Belady’s Anomaly
9.
Advantages of Belady's Anomaly
10.
Disadvantages of Belady's Anomaly
11.
Frequently Asked Questions
11.1.
What is the Belady's anomaly?
11.2.
Why does FIFO suffer from Belady's anomaly?
11.3.
How do I get rid of Belady anomaly?
11.4.
How do I check my Belady's anomaly?
12.
Conclusion
Last Updated: Mar 27, 2024
Medium

What is Belady's Anomaly in Operating System

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Each process in the Virtual Memory system is divided into a fixed number of pages. Demand paging is used to load these pages into physical memory.

Whenever a new page is needed, a page fault occurs under Demand Paging, and the new page is then loaded into memory in place of some other page.

Replaced pages are chosen using an algorithm that specifies which pages should be replaced. It is said that Belady's Anomaly occurs whenever the number of page faults increases significantly when the number of frames increases.

what is belady's anomaly

 

What is Belady’s Anomaly?

Bélády’s anomaly occurs when adding more page frames to memory leads to more page faults for a specific access pattern. Occasionally, an exception, i.e., increased frames, leads to more page faults. Belady's anomaly refers to this exception. This issue is caused by the page replacement algorithm that governs demand paging.

Here are a few page replacement algorithms in which Belady's Anomaly most frequently occurs:

  • First In First Out (FIFO)
  • Second Chance Algorithm
  • Random Page Replacement Algorithm

Also read anomalies in database

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Why does Belady's Anomaly occur in First Come First Serve(FCFS)?

We know that increasing the number of frames will reduce page faults. As a result, the number of frames and page faults is inversely proportional.

The disadvantage of FIFO is that it may increase the number of page faults when the number of frames increases, unlike all other page replacement algorithms. See the below explanation for a better understanding.

Using First Come First Serve(FCFS)

The first page that loads in memory are swapped first using the  First in First Out algorithm. Similarly, the last page loaded into memory will be the last one swapped out. 

Let’s see how the pages are loaded into the memory: Consider a reference string that shows how the CPU demands the pages.

Reference String: 0,1, 2, 3, 0, 1, 4, 0, 1, 2, 3, 4.

When the number of Frames is: 3

 

1

2

3

4

5

6

7

8

9

10

11

12

F3     2 2 2 1 1 1 1 1 3 3
F2   1 1 1 0 0 0 0 0 2 2 2
F1 0 0 0 3 3 3 4 4 4 4 4 4

 

Now,

At positions 1,2,3,4,5,6,7,10,11, there is a page fault as the page is not already present.

There is no page fault at positions 8, 9,12, as the page is already present.

  • No. of hits= 3
  • No. of page faults = 9
     

When the number of Frames is: 4

If there are four empty frames in the memory, then pages 0, 1, 2, 3 come into the four frames. They are allocated to the empty frame in order of their arrival. It causes a page fault because 0, 1, 2, 3 are not present in the memory.

 

1

2

3

4

5

6

7

8

9

10

11

12

F4       3 3 3 3 3 3 2 2 2
F3     2 2 2 2 2 2 1 1 1 1
F2   1 1 1 1 1 1 0 0 0 0 4
F1 0 0 0 0 0 0 4 4 4 4 3 3

 

At position 1,2,3,4,7,8,9,10,11,12 there is a page fault as the page is not already present.

At position 5,6, there is no page fault as the page is already present.

  • No. of hits = 2
  • No. of page faults =10
     

From the above observation, we assumed that if we had increased the no. of frames (so that more pages can enter), there might be fewer page faults. But the number of hits were less, and page faults were more when we increased the number of frames. Hence, This is known as Belady's Anomaly.

But Least Recently Used(LRU), Optimal Page Replacement(OPR), and Most Recently Used(MRU) do not suffer from this anomaly. 

Why? See the below scenarios for both page replacements.

Why does Belady's Anomaly not occur in other Algorithms?

Using Least Recently Used(LRU)

LRU replaces the pages which haven't been used in a long time. The optimal page replacement algorithm is the opposite of this algorithm. Instead of looking at the future, we examine the past.

Let’s see how it works: Consider a reference string that shows how the CPU demands the pages.

Reference String: 0,1, 2, 3, 0, 1, 4, 0, 1, 2, 3, 4.

When the number of Frames is: 3

If there are three frames in the memory, then pages 0, 1, 2 come into the three frames. They are allocated to the empty frame in order of their arrival. It causes a page fault because 0, 1, 2 are not present in the memory.

After that, if the page is already loaded, there will be a page hit; if not, we will load the page into the memory by replacing the new page with the page that has not been used for a long time in the memory, which will cause the page fault.

 

1

2

3

4

5

6

7

8

9

10

11

12

F3

   

2

2

2

1

1

1

1

1

1

4

F2

 

1

1

1

0

0

0

0

0

0

3

3

F1

0

0

0

3

3

3

4

4

4

2

2

2

 

At positions 1,2,3,4,5,6,7,10,11,12 there is a page fault as the page is not already present.

At position 8,9, there is no page fault as the page is already present.

  • No. of hits = 2
  • No. of page faults =10
     

When the number of Frames is: 4

If there are four empty frames in the memory, then pages 0, 1, 2, 3 come into the four frames. They are allocated to the empty frame in order of their arrival. It causes a page fault because 0, 1, 2, 3 are not present in the memory.

 

1

2

3

4

5

6

7

8

9

10

11

12

F4

     

3

3

3

3

3

3

2

2

2

F3

   

2

2

2

2

4

4

4

4

3

3

F2

 

1

1

1

1

1

1

1

1

1

1

1

F1

0

0

0

0

0

0

0

0

0

0

0

4

 

At Positions 1,2,3,4,7,10,11,12, there is a page fault as the page is not already present.

There is no page fault at positions 5, 6, 8, 9 as the page is already present.

  • No. of hits = 4
  • No. of page faults = 8
     

Therefore, it does not suffer from Belady's anomaly because page faults decrease when frame size increases.
Learn more about Least Recently Used(LRU) -  LRU Page Replacement Algorithm 

Using Optimal Page Replacement(OPR)

This algorithm replaces pages that are not likely to be referred to for a long time in the future. Even though it isn't practical to implement, it can be used as a guide. Its optimality is compared to some other algorithms.

Let’s see how it works: Consider a reference string that shows how the CPU demands the pages.

Reference String: 0,1, 2, 3, 0, 1, 4, 0, 1, 2, 3, 4.

When the number of Frames is: 3

If there are three frames in the memory, then pages 0, 1, 2 come into the three frames. They are allocated to the empty frame in order of their arrival. It causes a page fault because 0, 1, 2 are not present in the memory.

There will then be a page hit if the page has already been loaded; if not, we will load the page into memory by replacing the new page with one that will not be used for the longest time ahead, causing a page fault.

 

1

2

3

4

5

6

7

8

9

10

11

12

F3

   

2

3

3

3

4

4

4

4

4

4

F2

 

1

1

1

1

1

1

1

1

1

1

1

F1

0

0

0

0

0

0

0

0

0

2

3

3

 

At positions 1,2,3,4,7,10,11, there is a page fault as the page is not already present.

There is no page fault at positions 5 6 8 9 12 as the page is already present.

  • No. of hits = 5
  • No. of page faults = 7
     

When the number of Frames is: 4

If there are four empty frames in the memory, then pages 0, 1, 2, 3 come into the four frames. They are allocated to the empty frame in order of their arrival. It causes a page fault because 0, 1, 2, 3 are not present in the memory.

 

1

2

3

4

5

6

7

8

9

10

11

12

F4

     

3

3

3

4

4

4

4

4

4

F3

   

2

2

2

2

2

2

2

2

2

2

F2

 

1

1

1

1

1

1

1

1

1

1

1

F1

0

0

0

0

0

0

0

0

0

0

3

3

 

At position 1,2,3,4,7,11, there is a page fault as the page is not already present.

There is no page fault at positions 5 6 8 9 10 12 as the page is already present.

  • No. of hits = 6
  • No. of page faults = 6
     

Therefore, it does not suffer from Belady's anomaly because page faults decrease when frame size increases.
 

Most Recently Used(MRU)

An MRU replaces the most recently used page in the main memory. Of all page replacement algorithms, MRU performs best.

Let’s see how it works: Consider a reference string that shows how the CPU demands the pages.

Reference String: 0,1, 2, 3, 0, 1, 4, 0, 1, 2, 3, 4.

When the number of Frames is: 3

In the beginning, if there are three frames in the memory, then pages 0, 1, 2 go into the three frames. In order of arrival, they are placed in the empty frame. Because they are not present, 0, 1, 2, 3 cause a page fault.

A page hit will occur when a page has been loaded already; if not, a page fault will occur as the page is replaced with one that was recently used before.

 

1

2

3

4

5

6

7

8

9

10

11

12

F3     2 3 3 3 3 3 3 3 3 3
F2   1 1 1 1 1 4 4 4 4 4 4
F1 0 0 0 0 0 0 0 0 1 2 2 2

 

There is a page fault at positions 1, 2, 3, 4, 7, 9, 10 as the page is not already present.

There is no page fault at positions 5, 6, 8, 11, 12 as the page is already present.

  • No. of hits = 5
  • No. of page faults = 7
     

When the number of Frames is: 4

If there are four empty frames in the memory, then pages 0, 1, 2, 3 come into the four frames. They are allocated to the empty frame in order of their arrival. It causes a page fault because 0, 1, 2, 3 are not present in the memory.

 

1

2

3

4

5

6

7

8

9

10

11

12

F4       3 3 3 3 3 3 3 3 3
F3     2 2 2 2 2 2 2 2 2 2
F2   1 1 1 1 1 4 4 4 4 4 4
F1 0 0 0 0 0 0 0 0 1 1 1 1

 

There is a page fault at positions 1, 2, 3, 4, 7, and 9, as the page is not already present.

There is no page fault at positions 5, 6, 8, 10, 11, and 12, as the page is already present.

  • No. of hits = 6
  • No. of page faults = 6
     

Hence, we can conclude that Least Recently Used, Optimal Page Replacement, and Most Recently Used algorithms do not suffer from Belady's Anomaly. As the frame size increases, these algorithms have lower page fault rates.

Belady’s Anomaly Graph

Belady's Anomaly graph is basically a graph of the number of page faults against the number of page frames. Such a picture depicts Belady's anomaly in graphical format. The graph should depict an increasing trend in the number of page faults as the number of page frames increases.

Belady's Anomaly Graph

As you can see above, at point P, when the number of page frames is increased from 7 to 8, the number of page faults, instead of decreasing further, increases from 3 to 4. Thus, at point Q, Benady's anomaly is shown.

Example of Belady’s Anomaly

Let us now see a live example of Belady's Anomaly. Consider the following sequence of page accesses:

6, 7, 8, 9, 6, 7, 10, 6, 7, 8, 9, 10

Let's analyze the page frames using the FIFO replacement policy. First, let's take the number of available page frames to be equal to 3. The following image illustrates this situation.

frames using the FIFO

As it is clear from the image above, the total number of page faults is equal to 9 when 3-page frames are available. Now, let's see the same page sequence using four-page frames:

sequence using four-page frames

As it is clear now, increasing the number of page frames, in this case, leads to an increased number of page faults.

You can also read about layered structure of operating system.

Why does Belady’s Anomaly occur?

  • When an algorithm doesn't follow the stack property, it suffers from Belady's Anomaly. 
  • These problems do not exist with LRU and Optimal Page Replacement as they are stack-based algorithms. The number of page faults decreases as the frame size increases in these algorithms.
  • Algorithms that follow the stack property are called stack-based algorithms.
  • Because of this, webpage replacement algorithms can assign priority to pages without regard to the number of frames in the main memory.
     

Must Read Process Management in OS

Features of Belady’s Anomaly

The idea that having additional memory should always reduce page faults is put to the test by this anomaly. The features of Belady's anomaly are as follows:

  • Not Intuitive: Contrary to intuition, additional memory doesn't seem to reduce page faults.
     
  • Optimal Page Replacement: An optimal page replacement algorithm can be used to solve this problem, although it frequently isn't practical in practical systems.
     
  • Page Fault Increase: Adding extra page frames causes an increase in page faults.
     
  • Algorithm Dependent: Depending on the page replacement algorithm being utilised, it occurs in particular situations.
    Unusual Access Patterns: These unusual access patterns to memory pages are frequently observed.

Advantages of Belady's Anomaly

The advantages of Belady's Anomaly are:

  • Algorithm Evaluation: Belady's Anomaly helps in evaluating the efficiency and performance of different page replacement algorithms. It highlights scenarios where seemingly intuitive strategies may not perform optimally, prompting the exploration of alternative algorithms.
  • Algorithm Design: Understanding Belady's Anomaly can lead to the development of more sophisticated page replacement algorithms that mitigate or prevent its occurrence. This drives innovation in memory management techniques, ultimately enhancing system performance and resource utilization.
  • Research and Education: Belady's Anomaly serves as a valuable concept in computer science education and research. It allows students and researchers to delve into the complexities of memory management systems, fostering a deeper understanding of the trade-offs involved in designing efficient algorithms.
  • Algorithm Comparison: Belady's Anomaly enables a comparative analysis of different page replacement algorithms under varying workloads and system configurations. This comparative analysis helps identify the strengths and weaknesses of each algorithm, facilitating informed decisions in selecting the most suitable algorithm for a given scenario.
  • Performance Tuning: By studying Belady's Anomaly, system administrators and developers can fine-tune memory management parameters and algorithms to achieve better performance in specific environments. This process involves understanding how different system configurations impact the occurrence and severity of the anomaly, allowing for optimization to minimize its effects.

Disadvantages of Belady's Anomaly

The disadvantages of Belady's Anomaly are:

  • Unpredictability: Belady's Anomaly introduces unpredictability into memory management systems. The fact that adding more page frames can unexpectedly degrade performance complicates system optimization and resource allocation decisions.
  • Resource Wastage: In real-world scenarios, Belady's Anomaly can lead to inefficient resource utilization. Allocating additional memory resources to a process in an attempt to improve performance may backfire, resulting in wasted memory and potentially impacting the performance of other processes sharing the system.
  • Complexity: Dealing with Belady's Anomaly requires a deeper understanding of memory management algorithms and their behavior. This complexity adds overhead to system design, implementation, and optimization efforts, making memory management more challenging to implement and maintain.
  • Overhead in System Monitoring: Mitigating Belady's Anomaly often requires continuous monitoring and adjustment of memory management parameters, which can introduce overhead in terms of system resources and administrative effort. Constantly monitoring and adapting to changing workloads to prevent or minimize the occurrence of the anomaly may divert resources from other critical tasks.
  • Complexity in Real-Time Systems: In real-time systems where predictable performance is paramount, Belady's Anomaly presents significant challenges. The unpredictable behavior of page replacement algorithms under varying conditions complicates the guarantee of meeting timing constraints and may lead to unacceptable performance degradation in critical applications.

Also Read About, pcb in operating system

Frequently Asked Questions

What is the Belady's anomaly?

When you add more memory space (page frames), you'd expect fewer page faults. However, Belady's Anomaly breaks this expectation by causing more page faults as you increase memory, which is counterintuitive.

Why does FIFO suffer from Belady's anomaly?

FIFO suffers as it evicts pages regardless of their usefulness, potentially removing crucial pages prematurely, contributing to increased page faults.

How do I get rid of Belady anomaly?

To mitigate Belady's Anomaly, utilize more advanced page replacement algorithms like LRU or Optimal, which prioritize retaining frequently accessed or soon-to-be-used pages.

How do I check my Belady's anomaly?

Detect Belady's Anomaly by monitoring page faults, memory utilization, and system performance metrics over time, observing for unexpected increases in page faults as page frames are added.

Conclusion

  • Belady's Anomaly is when there is a fixed number of page faults regardless of how many frames are present. 
  • The number of page faults is influenced by many factors, including the reference string length and the number of free page frames. 
  • In addition to the Random page replacement algorithm, Belady's Anomaly can also affect algorithms that act like First in First out (FIFO) page replacement algorithms. T
  • The advantage of stack-based algorithms is that they are guaranteed to deliver better page hits even when the frames are incremented when they are used. 
     

Refer to our guided paths on Coding Ninjas Studio to learn more about Operating System, DSAJavaScriptSystem DesignDBMSJava, etc. Enroll in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations. 

Happy Learning, Ninja!

Previous article
Convoy Effect in Operating System
Next article
Shortest Job First(Non-preemptive)
Live masterclass