Question 43

Problem Setting:

• 20 physical frames containing initial pages 101 to 120.
• Access sequence: $1, 2, \dots, 100$ repeated 3 times.
• Let loop length $N = 100$ and frames $M = 20$.

Optimal Page Replacement Behavior:

• In the first round, accessing pages 1 through 20 causes 20 page faults, filling all 20 frames with pages $\{1, 2, \dots, 20\}$.
• When page 21 is accessed, an eviction must occur. The optimal algorithm evicts the page whose next request occurs latest in the future.
• In the sequence, after page 100 finishes round 1, round 2 requests pages in order $1, 2, 3, \dots$.
• Thus, page 1 will be needed earliest, then page 2, ..., while page 20 will be needed furthest in the future among pages in memory!
• Optimal therefore evicts page 20 to load page 21. Next, when page 22 arrives, page 21 is evicted, and so on.
• In this way, Optimal always evicts the page that was brought in most recently, keeping pages $\{1, 2, \dots, 19\}$ permanently in memory for subsequent rounds!

Comparison with Standard Policies:

• LRU and FIFO: Evict page 1, then page 2, ..., completely flushing the loop and suffering a 100% miss rate on all subsequent passes.
• Most-Recently-Used (MRU): Explicitly evicts the most recently referenced page on every miss. Thus, it keeps the early pages $\{1, \dots, 19\}$ in memory and only cycles the 20th frame, exactly mirroring the optimal replacement policy for this loop.

Conclusion:
MRU experiences the same number of page faults as the optimal policy, corresponding to option (D).