Belady's Anomaly in Operating System

What is Belady’s Anomaly?

Belady’s Anomaly refers to the counterintuitive situation in operating system memory management where increasing the number of page frames results in an increase in the number of page faults.

This phenomenon is named after Laszlo Belady, who first identified it. Normally, as more page frames are available, the operating system has more flexibility to keep the necessary pages in memory, which should reduce the number of page faults. However, in the case of Belady’s Anomaly, this intuition fails, and we observe an unexpected increase in page faults with more available frames.

Page fault- When there is no required page present in RAM (secondary memory) on calling from the CPU, this is known as a "Page Fault".

Reason for Belady’s Anomaly

Generally, if we have less number of frames then, the number of page faults is more. The number of frames is inversely proportional to the number of page faults. But sometimes, a situation occurs when this concept is reversed.

The number of frames becomes directly proportional to page faults. As we increase the number of frames, the number of page faults also increases. When the execution of a process starts, the operating system starts allocating memory to a group of data. The group of data is called "pages".

And these pages are loaded into the virtual memory called "Frames", which are fixed in size. So, when there are no free frames to allocate a page, the oldest frame is replaced by a new one which ultimately leads to "page fault". The pages that are added first will swap out first because it will be for the longest time in memory. So, when swappig will take place, oldest page will be swapped first from frame.

Belady’s Anomaly in Page Replacement Algorithms

Belady’s Anomaly is a unique and counterintuitive phenomenon that occurs in the realm of page replacement algorithms within operating systems. These algorithms are crucial for memory management, helping to decide which pages should be kept in the limited space of the main memory and which should be swapped out in case a page fault occurs.

Page replacement algorithms work to optimize the utilization of the available memory, ensuring that the pages most likely to be used are readily accessible, while those less frequently accessed are stored on slower storage mediums. However, in certain situations, as observed by Laszlo Belady, the expected outcome of these algorithms can be flipped on its head.

The anomaly presents itself when, upon increasing the number of available page frames in the memory, the number of page faults unexpectedly increases rather than decreases.

This behavior is most notably observed in the First-In-First-Out (FIFO) page replacement algorithm. In a typical scenario, one would anticipate that providing more memory space would lead to fewer page faults, as there is more room to store the necessary pages. Belady’s Anomaly defies this logic, showing that under certain conditions, having more memory can actually lead to less efficient page replacement, resulting in an increased number of page faults.

This anomaly not only serves as an interesting case study in the world of computer science but also highlights the importance of choosing the right algorithm for memory management, as the implications of increased page faults can lead to slower program execution and reduced system performance. Understanding and mitigating the effects of Belady’s Anomaly is therefore crucial for optimizing system efficiency and ensuring the smooth operation of computer programs.

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

Generally, if we increase the number of frames, it will cause less number of page faults. In FIFO, the number of page faults increases even if we increase the number of frames. The pages that are added first will swap out first because it will be for the longest time in memory.

So, when swapping will take place, the oldest page will be swapped first from frame. In other page replacement algorithm that uses 'stack based algorithm' for allocating pages', Belady's Anomaly does not occur. These algorithm replaces the pages that are present for least time because the algorithm considers them as useless. But its not same in FCFS(First Come First Out)

Belady’s Anomaly Graph:

It is supposed that the number of page faults should be less when we increase the number of frames. But sometimes, when the number of page faults increases even after increasing the number of frames, "Belady's Anomaly" occurs. Let us understand this condition using a graph:

• In the above figure, the page fault is highest when the number of frames is 1.
• After that, as the number of frames increases, the number of faults is not increased up to frame number 2, but it is the same.
• At point 3, the number of faults decreased. But, at point 4, the number of faults again increased even if the frames are increased.
• At this point, we can clearly see "Belady's Anomaly".

Why Stack-Based Algorithms Do Not Suffer from Belady’s Anomaly

Stack-based algorithms for page replacement hold a significant advantage when it comes to avoiding Belady’s Anomaly, a phenomenon where increasing the number of page frames results in an increase in page faults. The reason these algorithms are immune to the anomaly lies in their inherent design and operational logic.

1. Prioritizing Recently Used Pages:

Stack-based algorithms, such as Least Recently Used (LRU), maintain a stack of pages to keep track of the order in which pages are accessed.

The most recently accessed pages are pushed to the top of the stack, while less frequently accessed pages move down. When a page needs to be replaced, the algorithm selects the page at the bottom of the stack, ensuring that the pages most likely to be used again remain in memory. This approach inherently minimizes the chance of page faults, regardless of the number of available frames.

2. Consistent Replacement Policy:

These algorithms follow a consistent policy for page replacement that is not influenced by the number of page frames. Whether the system has a high or low number of frames, the algorithm will always prioritize keeping the most recently used pages in memory. This consistency ensures that the number of page faults does not unexpectedly increase as more frames become available, preventing Belady’s Anomaly.

3. Utilizing Temporal Locality:

Stack-based algorithms take advantage of the principle of temporal locality, which states that pages accessed recently are likely to be accessed again in the near future. By keeping these pages readily available, the algorithms reduce the likelihood of page faults, contributing to their immunity to Belady’s Anomaly.

4. No Dependence on Frame Allocation:

Unlike other algorithms that might behave differently based on the number of allocated frames, stack-based algorithms base their decisions solely on the access history of the pages. This independence from frame allocation further insulates them from the conditions that lead to Belady’s Anomaly.

Example of Belady’s Anomaly:

Let us take some examples to visualize 'Belady's Anomaly'.

Example 1: Suppose a memory where number of frames = 3 and reference string = d,c,b,a,d,c,e,d,c,b,a,e

The strings will be allocated as shown in the figure and when there are frames unavailable for a string, the oldest frame will be swapped out and the desired string will be replaced. The swapping occurs on a "First In First Out" basis. Here, the number of page faults is: 1+1+1+1+1+1+1+1+1 = 9

Example 2: Again we will use the same string but now the number of frames is 4.

As you can see in the above image, the allocation of strings is done until the 4th frame is occupied. After that, the 5th string needs to be allocated. So, the oldest string is swapped. Here, the number of page faults is: 1+1+1+1+1+1+1+1+1+1 = 10

• We can clearly see that, as the number of frames is increased from 3 to 4, the number of page faults is also increased from 9 to 10. Here we can visualize the " Belady's Anomaly".

How to Eliminate Belady’s Anomaly?

Belady's Algorithm can be eliminated by using a stack-based algorithm. Examples of such algorithms are:

• Least Recently Used (LRU) algorithm
• Optimal Page Replacement Algorithm

These algorithms use the concept that- if a page is not used for a long time that means there is no frequent use of that particular page. So, it is better to remove this page from memory. In this way, memory management can be improvised and Belady's Anomaly can be eliminated.