GATE CS 2016 Set 2 Q20 — Memory Management and Virtual Memory

This phenomenon is known as Belady's Anomaly, where increasing the number of physical page frames results in an increase in the number of page faults for a specific page reference string.

• FIFO (First In First Out): FIFO is susceptible to Belady's Anomaly. For example, for the page reference string:
  $$\text{3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4}$$
  • With 3 frames, the number of page faults is 9.
  • With 4 frames, the number of page faults increases to 10.
• LRU and OPT: These belong to a class of page replacement algorithms called stack algorithms. A stack algorithm has the property that the set of pages in memory for $n$ frames is always a subset of the pages in memory for $n+1$ frames. Therefore, they never suffer from Belady's Anomaly.

Thus, the page fault rate can increase with more frames in the FIFO algorithm.