Consider a demand paging system with three frames, and the following page…

We have 3 frames and the reference string: 1, 2, 3, 4, 5, 4, 1, 6, 4, 5, 1, 3, 2.

Analyze the starred replacements by comparing future uses of pages currently in the frames.

• After the first three misses we have {1, 2, 3}.

• When 4 is referenced (first replacement), the next uses of 1, 2, 3 are at positions 7, 13, and 12 respectively. The page whose next use is farthest away is page 2 (position 13), so evict 2 and load 4 → {1, 3, 4}.

• When 5 is referenced next, the frames are {1, 3, 4}. Their next uses are at positions 7 for 1, 12 for 3, and 6 for 4. The farthest is 3 (position 12), so evict 3 and load 5 → {1, 4, 5}.

• When 6 is referenced later, the frames are {1, 4, 5}. Their next uses after that point are 1 at position 11, 4 at 9, and 5 at 10. The farthest future use is page 1 (position 11), so evict 1 and load 6 → {6, 4, 5}.

• When 1 is referenced again (later miss), the remaining future references are only 3 and 2, so none of 6, 4, 5 are used again. Any of them could be evicted; the table shows 6 replaced resulting in {1, 4, 5}. Subsequent replacements follow the same future-use logic.

These choices match the rule: evict the page whose next use is farthest in the future (or never used again).

Why the other common policies do not match this sequence:

• Least Recently Used (LRU): At the replacement for 4, LRU would evict the page that was used least recently (page 1), but the table evicts page 2. This disagreement shows LRU does not produce the shown sequence.

• Least Frequently Used (LFU) and Most Frequently Used (MFU): These use past access counts, not future knowledge. For example, just before loading 6 the frames are {1, 4, 5} with counts 1:2, 4:2, 5:1, so LFU would evict page 5 (lowest count), but the table evicts page 1. Relying on past frequencies cannot explain the consistent future-driven evictions in the table.

Answer: Optimal page replacement policy