Recall that Belady’s anomaly is that the page-fault rate may increase as the…

Belady’s anomaly: An algorithm suffers from Belady’s anomaly if there exists a reference string for which increasing the number of frames increases the number of page faults.

Key concept: Stack (inclusion) property — if at every time the set of pages held with k frames is always a subset of the set held with k+1 frames, then page faults cannot increase when frames increase.

• LRU: LRU is a stack algorithm. With k frames it contains the k most recently used pages, and with k+1 frames those same k pages remain plus one more, so pages(k) ⊆ pages(k+1). Therefore LRU cannot exhibit Belady’s anomaly.

• Random replacement: Random replacement is not a stack algorithm. Because evictions are chosen independently at random, the set of pages with k frames need not be a subset of the set with k+1 frames, so it can exhibit Belady’s anomaly for some reference strings.

Illustrative reference string: 1,2,3,4,1,2,5,1,2,3,4,5. For some runs of random replacement this string can produce more faults with 4 frames than with 3 frames (showing the anomaly), while LRU on the same string never increases faults when frames are increased.

Conclusion: S1 (Random replacement suffers from Belady’s anomaly) is true; S2 (LRU suffers from Belady’s anomaly) is false. The correct choice is the one that states S1 is true and S2 is false.