### An optimality proof of the $LRU-\textit{K}$ page replacement algorithmAn optimality proof of the $LRU-\textit{K}$ page replacement algorithm

Access Restriction
Subscribed

 Author O'Neil, Elizabeth J. ♦ O'Neil, Patrick E. ♦ Weikum, Gerhard Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1999 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword LRU ♦ LRU-K ♦ Optimality ♦ Page-replacement 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-\textit{K}$ method, and reduces to the well-known LRU (Least Recently Used) method for $\textit{K}$ = 1. Previous work [O'Neil et al. 1993; Weikum et al. 1994; Johnson and Shasha 1994] has shown the effectiveness for $\textit{K}$ > 1 by simulation, especially in the most common case of $\textit{K}$ = 2. The basic idea in $LRU-\textit{K}$ is to keep track of the times of the last $\textit{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-\textit{K}$ is optimal. Specifically we show: given the times of the (up to) $\textit{K}$ most recent references to each disk page, no other algorithm $\textit{A}$ making decisions to keep pages in a memory buffer holding $\textit{n}$ - 1 pages based on this infomation can improve on the expected number of I/Os to access pages over the $LRU-\textit{K}$ algorithm using a memory buffer holding $\textit{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. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1999-01-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 46 Issue Number 1 Page Count 21 Starting Page 92 Ending Page 112

#### Open content in new tab

Source: ACM Digital Library