Principle of Optimal Page Replacement and the LRU Stack Model

Program reference strings generated by the LRU stack model are considered, and expressions for the expected times to next reference for all pages occupying different LRU stack positions are derived. Using these expressions, necessary and sufficient conditions as well as sufficient conditions on the distance distribution are obtained which guarantee implementation by the LRU replacement algorithm of the "informal principle of optimality" for page replacements. The sufficient conditions are found to be the same as those under which the LRU replacement algorithm is shown to be optimal. Relaxed conditions are also obtained for special cases where the number of page frames is fixed.