Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
  An Optimality Proof of the LRU-K Page Replacement Algorithm

O'Neil, E. J., O'Neil, P. E., & Weikum, G. (1999). An Optimality Proof of the LRU-K Page Replacement Algorithm. Journal of the ACM, 46(1), 92-112. Retrieved from http://portal.acm.org/citation.cfm?doid=300515.300518.

Item is

Dateien

einblenden: Dateien
ausblenden: Dateien
:
ONeilOW99.pdf (beliebiger Volltext), 155KB
 
Datei-Permalink:
-
Name:
ONeilOW99.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Privat
MIME-Typ / Prüfsumme:
application/pdf
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
O'Neil, Elizabeth J., Autor
O'Neil, Patrick E., Autor
Weikum, Gerhard1, Autor           
Affiliations:
1Databases and Information Systems, MPI for Informatics, Max Planck Society, ou_24018              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2006-04-111999
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: Expertenbegutachtung
 Identifikatoren: eDoc: 520346
URI: http://portal.acm.org/citation.cfm?doid=300515.300518
Anderer: Local-ID: C1256DBF005F876D-20C00B6FF1E4F2B8C125714D0057B83B-ONeilOW99
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Journal of the ACM
Genre der Quelle: Zeitschrift
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 46 (1) Artikelnummer: - Start- / Endseite: 92 - 112 Identifikator: ISSN: 0004-5411