Belady’s Anomaly is a counterintuitive situation where increasing the number…
2025
Belady’s Anomaly is a counterintuitive situation where increasing the number of page frames results in more page faults for certain page replacement algorithms (like FIFO).
Consider the page reference string:
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Using FIFO with 3 frames causes 9 page faults.
Using FIFO with 4 frames causes 10 page faults → more faults with more memory.
Explain three algorithms in which the Belady’s Anomaly will not happen for this page reference string.
Show answer & explanation
Algorithms Immune to Belady’s Anomaly
Belady’s Anomaly occurs in some page replacement algorithms (such as FIFO) where increasing the number of page frames leads to more page faults. This happens because FIFO replaces pages only based on their arrival order.
However, some algorithms are called Stack Algorithms. These algorithms satisfy the stack property, which means that the set of pages in memory with n frames is always a subset of the pages with n+1 frames. Because of this property, increasing the number of frames will never increase the number of page faults, so Belady’s Anomaly cannot occur.
For the page reference string:
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5, the following algorithms will not show Belady’s anomaly.
1. Least Recently Used (LRU)
The LRU algorithm replaces the page that has not been used for the longest time in the past. It assumes that recently used pages will likely be used again soon. Since it keeps track of recent usage, increasing the number of frames will either reduce or keep the same number of page faults, so Belady’s anomaly does not occur.
2. Optimal Page Replacement (OPT)
The Optimal algorithm replaces the page that will not be used for the longest time in the future. It always produces the minimum possible number of page faults. Because it follows the stack property, adding more frames will never increase page faults.
3. Most Recently Used (MRU)
In the MRU algorithm, the page that was most recently used is replaced. The decision is based on the order of recent access, which keeps a consistent priority among pages. Therefore, increasing memory frames will not increase the number of page faults.
Conclusion
Algorithms such as LRU, Optimal, and MRU follow the stack property, meaning the pages present with n frames are always included in the pages with n+1 frames. Therefore, these algorithms are immune to Belady’s Anomaly, and increasing memory will never increase page faults.