What is Belady’s Anomaly?

In general, if we think the page faults should directly depend on the frame size. Like if the frame size is more then there are more pages of the processes available at any time in the memory. This would mean that the number of hits would increase. But, this is not the case in the FIFO page replacement algorithm. So, let's start the blog and understand why FIFO suffers from Belady’s Anomaly and what is this Belady's Anomaly?

First In First Out

In this page replacement algorithm, the OS maintains a queue that keeps track of all the pages in memory, with the oldest page at the front and the most recent page at the back.

When there is a need for page replacement, the FIFO algorithm, swaps out the page at the front of the queue, that is the page which has been in the memory for the longest time will be swapped. Now let's take an example and understand Belady’s Anamoly.

Example:

Consider the page reference string of size 12: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 with frame size 3(i.e. maximum 3 pages in a frame).

Total Page Fault = 9

1. Initially, all 3 frames are empty, so when 1, 2, 3 came, they are allocated to the empty frames in order of their arrival. This is page fault as 1, 2, 3 are not available in memory.
2. When 4 comes, it is not available in memory so page fault occurs and it replaces the oldest page in memory, i.e., 1.
3. When 1 comes, it is not available in memory so page fault occurs and it replaces the oldest page in memory, i.e., 2.
4. When 2 comes, it is not available in memory so page fault occurs and it replaces the oldest page in memory, i.e., 3.
5. When 5 comes, it is not available in memory so page fault occurs and it replaces the oldest page in memory, i.e., 1.
6. When 1 comes, it is available in the memory, i.e., page hit, so no replacement occurs.
7. When 2 comes, it is available in the memory, i.e., page hit, so no replacement occurs.
8. When 3 comes, it is not available in memory so page fault occurs and it replaces the oldest page in memory, i.e., 1.
9. When 4 comes, it is not available in memory so page fault occurs and it replaces the oldest page in memory, i.e., 2.
10. When 5 comes, it is available in the memory, i.e., page hit, so no replacement occurs.

Page Fault ratio = 9/12 i.e. total miss/total possible cases

Hit ratio= 3/12 i.e total hit/ total possible cases

Now, let's see what happens when we increase the frame size from 3 to 4.

Total Page Fault = 10

1. Initially, all 4 frames are empty, so when 1, 2, 3, 4 came they are allocated to the empty frames in order of their arrival. This is page fault as 1, 2, 3, 4 are not available in memory.
2. When 1 comes, it is available in the memory, i.e., page hit, so no replacement occurs.
3. When 2 comes, it is available in the memory, i.e., page hit, so no replacement occurs.
4. When 5 comes, it is not available in memory so page fault occurs and it replaces the oldest page in memory, i.e., 1.
5. When 1 comes, it is not available in memory so page fault occurs and it replaces the oldest page in memory, i.e., 2.
6. When 2 comes, it is not available in memory so page fault occurs and it replaces the oldest page in memory, i.e., 3.
7. When 3 comes, it is not available in memory so page fault occurs and it replaces the oldest page in memory, i.e., 4.
8. When 4 comes, it is not available in memory so page fault occurs and it replaces the oldest page in memory, i.e., 5.
9. When 5 comes, it is not available in memory so page fault occurs and it replaces the oldest page in memory, i.e., 1.

Page Fault ratio = 10/12 (total miss/total possible cases)

Hit ratio= 2/12 (total hit/ total possible cases)

So, here as we are increasing the frame number the hit ratio should increase because now more pages of processes are available in the memory at a time. So, the chances of hits should increase but here the opposite is happening. The hit ratio is decreasing in place of increasing although we have increased the frame size. This is called Belady’s Anamoly. This problem comes in FIFO page algorithms. However, this unusual behavior is only observed sometimes. It doesn't mean that every time the frame size is increased the page faults will increase.

LRU and Optimal Page Replacement algorithm doesn't suffer from this problem. In these algorithms, the page faults decrease as the frame size is increased.

This was about Belady's Anomaly. Hope you learned something new today.

Do share this blog with your friends to spread the knowledge. Visit our YouTube channel for more content. You can read more blogs from here.

Keep Learning 🙂

Team AfterAcademy!