 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.^[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.