A computer has twenty physical page frames which contain pages numbered 101 through 120. Now a program accesses the pages numbered 1, 2, ..., 100 in that order, and repeats the access sequence THRICE. Which one of the following page replacement policies experiences the same number of page faults as the optimal page replacement policy for this program? (A) Least-recently-used (B) First-in-first-out (C) Last-in-first-out (D) Most-recently-used

Consider the reference string repeating $1, 2, \dots, 100$ three times with $N = 20$ frames initially holding pages $101$ through $120$.

1. First pass ($1, \dots, 100$): All policies (including Optimal) will experience 100 page faults to bring pages in.

2. Optimal Page Replacement: When replacing a page, Optimal replaces the page that will not be used for the longest period of time. In a cyclic sequence $1, 2, \dots, 100$, the page accessed most recently is the one that will be needed furthest in the future (at the end of the next cycle). Hence, replacing the Most-Recently-Used (MRU) page mimics the Optimal replacement strategy for repeated cyclic access strings.

3. Comparison:

   • Under FIFO and LRU, the oldest pages in the frames are replaced, causing every single reference to fault ($300$ page faults in total).

   • Under MRU, once 19 frames are filled with the first 19 pages ($1, \dots, 19$), the 20th frame is repeatedly replaced with the newest page ($20, 21, \dots, 100$). On subsequent iterations, pages $1$ to $19$ are already in memory and produce hits! This achieves the minimum possible number of page faults, matching the Optimal replacement algorithm.

Therefore, Most-recently-used (MRU) is the correct option.