In which one of the following page replacement algorithms it is possible for…

Belady's Anomaly: some page replacement algorithms can have a higher page fault rate after increasing the number of allocated frames for particular reference strings.

• LRU (Least Recently Used): This algorithm replaces the page that has not been used for the longest time. LRU is a stack algorithm and satisfies the inclusion property, so increasing the number of frames cannot increase the page fault rate for LRU.

• OPT (Optimal Page Replacement): This theoretical algorithm evicts the page that will not be used for the longest time in the future. OPT is also a stack algorithm and cannot suffer from Belady's Anomaly.

• MRU (Most Recently Used): This algorithm evicts the most recently used page. MRU is not a stack algorithm, so it does not guarantee the inclusion property and can show increased faults for some reference strings; however, it is not the classic example associated with Belady's Anomaly.

• FIFO (First In First Out): This algorithm evicts the oldest loaded page regardless of recent use. FIFO is a non-stack algorithm and is the standard example that can exhibit Belady's Anomaly; adding more frames can increase page faults for certain reference strings.

Illustrative example (classic reference string):

1. Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

2. Under FIFO: with 3 frames this reference string causes fewer page faults than with 4 frames (for this sequence FIFO yields 9 faults with 3 frames and 10 faults with 4 frames), demonstrating that adding a frame increased the page fault count.

Conclusion: FIFO (First In First Out) is the correct choice because it can exhibit Belady's Anomaly — increasing allocated frames may increase the page fault rate for some reference sequences.