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.
Virtual Memory and Belady’s Anomaly
- 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.
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:
- First In First Out (FIFO)
- Second Chance Algorithm
- 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.
However, 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.
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
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
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:
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:
Page Faults = 1+1+1+1+1+1+1+1= 8
- Memory Management Introduction
- Partition Allocation Method
- Buddy- System Allocator
- Types of Paging
- Mapping Virtual address to Physical Address.
- Virtual Memory
- Demand Paging
- Implementation of Demand paging and page fault
- Page Replacement Algorithms
- Belady’s Anomaly
- Static vs Dynamic Loading
- Static vs Dynamic Linking
- Translational Look Aside Buffer
- Process Address Space
- Difference between Segmentation and Paging