An optimality proof of the LRU- K page replacement algorithm

This paper analyzes a recently published algorithm for page replacement in hierarchical paged memory systems O'Neil et al. 1993. The algorithm is called the LRU- K method, and reduces to the well-known LRU (Least Recently Used) method for K = 1. Previous work O'Neil et al. 1993; Weikum et al. 1994; Johnson and Shasha 1994 has shown the effectiveness for K > 1 by simulation, especially in the most common case of K = 2. The basic idea in LRU- K is to keep track of the times of the last K references to memory pages, and to use this statistical information to rank-order the pages as to their expected future behavior. Based on this the page replacement policy decision is made: which memory-resident page to replace when a newly accessed page must be read into memory. In the current paper, we prove, under the assumptions of the independent reference model, that LRU- K is optimal. Specifically we show: given the times of the (up to) K most recent references to each disk page, no other algorithm A making decisions to keep pages in a memory buffer holding n - 1 pages based on this infomation can improve on the expected number of I/Os to access pages over the LRU- K algorithm using a memory buffer holding n pages. The proof uses the Bayesian formula to relate the space of actual page probabilities of the model to the space of observable page numbers on which the replacement decision is acutally made.