Optimal Page Replacement Algorithm

• Easy to describe – impossible to implement because OS cannot look into future.
• Useful to evaluate page replacement algorithms.
• Best (optimal) page replacement algorithm
1. Page fault occurs; a set of pages is in memory.
2. Label all pages with the number of instructions that will be executed before this page will be used again in the future.
3. Replace the page with the highest number.

A paging algorithm is described which is optimal when the program behavior is represented by the LRU (least recently used) stack model with arbitrary reference probability distributions.
In this model, a stack is defined which, at a given time, indicates the ordering of all the pages referenced by a program according to their time of use (the most recent on the top of the stack). A time-invariant reference probability, p (i), is assigned to the i/th/ stack position. The LRU replacement algorithm is optimal for a memory of size M if min {p(i) Absolute Value i less than or equal greater than or equal M maxpp(i) i>M}. The LRU stack model that is optimal for arbitrary probability distributions in the reference stack. The LRU algorithm is then a particular case of this optimal replacement algorithm.
This algorithm minimizes the number of page faults for a demand paging system occurring during the execution of a program, given the following assumptions:

1. The reference pattern of the program can be represented by the LRU stack model where the i/th/ stack page is S(i).
2. The independent stack probability distribution p is known.