Question 40

Belady's anomaly occurs when increasing the number of page frames allocated to a process results in an increase in the number of page faults.

A page replacement algorithm is called a stack algorithm if the set of pages that would be in memory with $m$ frames is always a subset of the pages that would be in memory with $m + 1$ frames at any point in time: $M_t(m) \subseteq M_t(m + 1)$.

It is mathematically proven that stack algorithms never suffer from Belady's anomaly. Both LRU (Least Recently Used) and Optimal (OPT) are stack algorithms. Therefore, LRU never suffers from Belady's anomaly, making statement S2 false.

In contrast, non-stack algorithms like FIFO (First-In, First-Out) and Random replacement do not maintain the inclusion property. The Random page replacement algorithm can replace a page that is needed immediately afterward, and increasing the number of frames can lead to a higher expected or actual number of page faults for specific reference strings. Hence, statement S1 is true.

Thus, S1 is true and S2 is false.