GATE CS 2009 Q9 — Memory Management and Virtual Memory

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

This anomaly can occur in page replacement algorithms that do not satisfy the stack property.

• Stack Algorithms: An algorithm is a stack algorithm if the set of pages in a memory of size $n$ frames is always a subset of the pages in a memory of size $n+1$ frames. Stack algorithms never exhibit Belady's anomaly. Examples include LRU (Least Recently Used) and Optimal replacement.
• Non-Stack Algorithms: Algorithms like FIFO (First-In-First-Out) do not satisfy the stack property and are susceptible to Belady's anomaly.

For example, using the FIFO policy on the reference string: $1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5$:

• With 3 frames: 9 page faults occur.
• With 4 frames: 10 page faults occur (an increase in page faults despite more memory).

Therefore, Belady's anomaly occurs in the FIFO page replacement policy.