GATE CS 1995 Q1.8 — Memory Management and Virtual Memory

Belady's Anomaly is the phenomenon where increasing the number of page frames results in an increase in the number of page faults for certain page reference strings.

Page replacement algorithms can be classified based on whether they satisfy the stack property:

1. Stack Algorithms: An algorithm is a stack algorithm if the set of pages in memory for $n$ frames is always a subset of the set of pages in memory for $n+1$ frames. Stack algorithms never suffer from Belady's anomaly. Examples include:
   • LRU (Least Recently Used)
   • Optimal Page Replacement
2. Non-Stack Algorithms: Algorithms like FIFO (First-In, First-Out) do not satisfy the stack property. Consequently, FIFO can exhibit Belady's anomaly for specific reference strings (for example, the sequence 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 yields more faults with 4 frames than with 3 frames).

Therefore, only FIFO suffers from Belady's anomaly.