A computer has twenty physical page frames which contain pages numbered 101…

Step 1. Given information from the question:

• Total physical frames = 20

• Initially contain pages 101–120

• Access sequence = pages 1 to 100, repeated three times

Step 2. Behavior of the program: The program performs strictly increasing scans over the same set of 100 pages, repeating the forward sequence three times. During a single pass there is no backward reuse; every page is referenced once in increasing order.

Step 3. What the optimal policy (OPT) does:

OPT always evicts the page whose next use is farthest in the future. In a strictly increasing scan, the page that was just used has its next reference farthest ahead (it will not be used again until the next cycle). Therefore OPT will evict the most recently used resident page at each replacement point.

Concrete example: after pages 1–20 occupy the frames, when page 21 is accessed the most recently used page is 20. The next use of page 20 occurs later than the next use of any other resident page (it will be needed at a later position in the current or next cycle), so OPT evicts page 20. Most-Recently-Used also evicts page 20. This pattern repeats for subsequent accesses.

Step 4. Why the other policies do not match OPT:

• Least-Recently-Used (LRU): Evicts the least recently used page, which in this forward scan tends to be a page whose next use comes sooner than the most recently used page. Evicting that page causes earlier faults than OPT.

• First-In-First-Out (FIFO): Evicts by arrival order and does not consider which page’s next use is farthest, so its fault count differs from OPT.

• Last-In-First-Out (LIFO): Evicts recently inserted pages without matching the optimal future-use criterion, so it does not reliably produce OPT’s fault count.

Step 5. Conclusion: The Most-Recently-Used replacement policy evicts the page whose next use is farthest in the future for this access pattern, so it experiences the same number of page faults as the optimal policy for the given sequence.