Belady’s Anomaly in Operating System (OS)

Virtual Memory and Belady’s Anomaly

Operating systems (OS) use Virtual memory when the programs executed by them need more space than the physical memory can allocate. In the Virtual memory system, all the processes are divided into fixed-sized pages. These pages are loaded into the physical memory using the method of demand paging. Under demand paging, during the execution of a particular process, whenever a page is required, a page fault occurs, and then the required page gets loaded into the memory replacing some other page. The page replacement algorithm specifies the choice of the page which is to be replaced. Now, Belady’s Anomaly is said to occur when the number of page faults increases significantly.

Belady’s Anomaly

The rate of page faults varies directly with the number of frames allocated to the individual process. The increase in the number of frames considerably decreases the number of page faults. However, sometimes reverse action occurs when the increased number of frames results in increased page faults. This exception is known as the Belady’s Anomaly. The occurrence of this exception depends on the page replacement algorithm, which governs the demand paging process. The page replacement algorithms in which Belady’s Anomaly occurs the most includes:

  1. First In First Out (FIFO)
  2. Second Chance Algorithm
  3. Random Page Replacement Algorithm

Belady’s Anomaly Graph

The graph in Fig.1 symbolizes that the number of page faults is inversely proportional to the number of memory frames. In simple terms, when the number of page frames increases, the number of page faults decreases.

Belady's Anomaly GraphHowever, when FIFO, second chance algorithm, and Random Page Replacement Algorithm are utilized in demand paging, then Belady’s anomaly is suffered by increased page fault while the expected result should be decrease in the number of page faults. Fig. 2 depicts the graph for Belady’s Anomaly.

Belady's Anomaly Graph_Increased Page fault

Before solving this example; it will be great if you can understand how to solve the Page Replacement Algorithm

Example of Belady’s Anomaly

Consider the memory with 3 frames, the reference string used in this case be w=dcbadcedcbae

Belady's Anomaly_3 frames

Page faults = 1+1+1+1+1+1+1+1+1 = 9

Consider the memory with 4 frames, the reference string used in this case be w=dcbadcedcbae

Belady's Anomaly_4 frames

Page Faults = 1+1+1+1+1+1+1+1+1+1 = 10

In the above mentioned case, with the increase in number of frames number of faults increased, displaying Belady’s Anomaly.

How to eliminate Belady’s Anomaly?

Implementing alternative page replacement algorithm helps eliminate Belady’s Anomaly. Use of stack based algorithms, such as Optimal Page Replacement Algorithm and Least Recently Used (LRU) algorithm, can eliminate the issue of increased page faults as these algorithms assign priority to pages. In the example given below LRU is used as page replacement algorithm for string w = 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.

Let the size of memory frame be 3; number of page faults is given by:

LRU Belady's Anomaly_3 frames

Page Faults = 1+1+1+1+1+1+1+1+1+1= 10

Let the size of memory frame be 4; number of page faults is given by:

LRU Belady's Anomaly_4 frames

Page Faults = 1+1+1+1+1+1+1+1= 8

Please Login/Signup to comment