= Optimal page replacement
On a miss with all <page frames> occupied, evict the resident <memory page> whose next access is farthest in the remaining <page-reference trace>. Treat no further access as farther than any finite next-use index; in the diagram, ties choose the lowest-numbered <page frame>. This is an offline, clairvoyant benchmark: a general <operating system> cannot know its future <memory references>. It minimizes miss count in the stated fixed-capacity <demand paging> model, rather than predicting the future from <temporal locality>.<Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and others/Beyond Physical Memory: Policies>[Section 22.2, pp. 2–4: farthest-future MIN policy, minimum misses, and the unavailable-future limitation]{ref}
In the <page-reference trace>, seven misses with three <page frames> is therefore a lower bound for any policy using the same assumptions; with four <page frames> the corresponding minimum is six. The benchmark is useful for judging how much improvement is possible on a recorded workload. Its objective counts each miss equally. Different <page writeback> costs or unequal loading costs require a different objective; minimum misses alone does not prove minimum elapsed time.
Back to article page
