Belady’s Anomaly in Operating System (OS)
Virtual Memory and Belady’s Anomaly
On this page we will discuss about Belady’s Anomaly in operating system . Operating systems (OS) use Virtual memory when the programs executed by them need more space than the physical memory can allocate.
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.
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 it occurs the most includes:
- First In First Out (FIFO)
- Second Chance Algorithm
- Random Page Replacement Algorithm
Belady’s 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.
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 Anomaly?
Implementing alternative page replacement algorithm helps eliminate it. 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
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment