Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

O'Neil, Elizabeth J.
O'Neil, Patrick E.
Weikum, Gerhard

dblp
dblp
dblp

Not MPG Author(s):

O'Neil, Elizabeth J.
O'Neil, Patrick E.

BibTeX cite key*:

ONeilOW99

Title

Title*:

An Optimality Proof of the LRU-K Page Replacement Algorithm


ONeilOW99.pdf (154.94 KB)

Journal

Journal Title*:

Journal of the ACM

Journal's URL:

http://www.acm.org/jacm/

Download URL
for the article:

http://portal.acm.org/citation.cfm?doid=300515.300518

Language:

English

Publisher

Publisher's
Name:

ACM

Publisher's URL:


Publisher's
Address:

New York, USA

ISSN:

0004-5411

Vol, No, pp, Date

Volume*:

46

Number:

1

Publishing Date:

1999

Pages*:

92-112

Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) 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.

URL for the Abstract:


Categories,
Keywords:

LRU, LRU-K, optimality, page-replacement

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Databases and Information Systems Group

Audience:

Expert

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{ONeilOW99,
AUTHOR = {O'Neil, Elizabeth J. and O'Neil, Patrick E. and Weikum, Gerhard},
TITLE = {An Optimality Proof of the {LRU-K} Page Replacement Algorithm},
JOURNAL = {Journal of the ACM},
PUBLISHER = {ACM},
YEAR = {1999},
NUMBER = {1},
VOLUME = {46},
PAGES = {92--112},
ADDRESS = {New York, USA},
ISBN = {0004-5411},
}


Entry last modified by Adriana Davidescu, 04/11/2006
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Adriana Davidescu
Created
04/11/2006 05:58:07 PM
Revision
0.



Editor
Adriana Davidescu



Edit Date
11.04.2006 18:06:26



Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section
ONeilOW99.pdf
View attachments here: