BELADY’S ANOMALY : Explained

Belady’s Anomaly occurs when an increase in the number of frames allocated leads to an increase in the number of page faults.

Scope

This article explains Belady’s Anomaly in detail.

Definition

If no frame is free, we find one that is not currently being used and free it. We can free a frame by writing its contents to swap space and changing the page table to indicate that the page is no longer in memory. We modify the page fault service runtime to include page replacement :

  1. Find the location of the desired page on the disk.
  2. Find a free frame
    If there is a free frame, use it.
    If there is no free frame use a page replacement algorithm to select a victim frame.
    Write the victim frame to the disk; change the page and frame tables accordingly.
  3. Read the desired page into the newly freed frame; change the page and frame tables 
  4. Restart the user process.

Two-page transfers which include swap out and swap in are required if no frames are free. To reduce this overhead we use a modified bit (or dirty bit). When this scheme is used, each page or frame has a modified bit associated with it, which indicates that the page has been modified. 

If the bit is set, we know that the page has been modified since it was read in from the disk and we must write that page to the disk. If the modify bit is not set, the page has not been modified since it was read into memory.

We develop a frame allocation algorithm and page replacement algorithm to implement demand paging. If multiple processes are in memory, we must decide how many frames to allocate to each process. 

An algorithm is evaluated by running it on a particular string of reference and computing the number of page faults. The string of memory reference is called a reference string.

Page replacement algorithm

  • FIFO page replacement (First in, First out)

In this algorithm time when the page was brought into memory is associated with each page. When a page must be replaced, the oldest page is chosen.

Example 1:

Reference string for a memory with three frames
 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1.

Therefore the total number of faults = 15.

Example 2:

Reference string : 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.
The number of faults for a frame is greater than the number of faults for 3 frames.

This unexpected result is known as Belady’s Anomaly.

For some page replacement algorithms, the page fault rate may increase as the number of allocated frames increases.

Taking 3 frames 

  • Optimal Page Replacement: 

One result of the discovery of Belady’s anomaly was the search for an optimal page replacement algorithm. An optimal page replacement algorithm has the lowest page-fault rate of all algorithms and never suffers from Belady’s anomaly. It replaces the page that will not be used for the longest period of time.

Eg. Reference String 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1.
  • LRU Page Replacement (Least Recently Used)

Replace the page that has not been used for the longest period of time.

LRU replacement associates each page with the time of that page’s last use. When a page must be replaced, LRU chooses the page that has not been used for the longest period of time. 

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

LRU replacement does not suffer from Belady’s anomaly.

Counting Based Page Replacement

  1. Least Frequently Used (LFU): Requires that the page with the smallest count be replaced. An actively used page should have a large reference count.
  2. Most Frequently Used (MFU): The page with the smallest count was probably just brought in and has got to be used.  

Summary

The general principle of the page replacement algorithm is that, if the number of frames increases, the page fault rate will decrease. But if the number of frames increases with the increase in a page fault, an unexpected result happens which is known as Belady’s Anomaly. Belady’s Anomaly is not always true. It is applicable only to the FIFO algorithm, not to LRU and the optimal page replacement algorithm. 

Special thanks to Ami Jangid for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article