Thumbnail
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

   Open content in new tab
Source: ACM Digital Library