hide
Free keywords:
-
Abstract:
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.
