The worst page-replacement policy

Kunal Agrawal; Michael A. Bender; Jeremy T. Fineman

doi:10.1007/s00224-008-9114-1

The worst page-replacement policy

Kunal Agrawal
, Michael A. Bender
, Jeremy T. Fineman

Computer Science

Massachusetts Institute of Technology

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

In this paper, we consider the following question: what is the worst possible page-replacement strategy? Our goal is to devise an online strategy that has the highest possible fraction of page faults as compared to the worst offline strategy. We show that there is no deterministic, online page-replacement strategy that is competitive with the worst offline strategy. We give a randomized strategy based on the "most-recently-used" heuristic and show that this strategy is the worst possible online page-replacement strategy.

Original language	English
Pages (from-to)	175-185
Number of pages	11
Journal	Theory of Computing Systems
Volume	44
Issue number	2
DOIs	https://doi.org/10.1007/s00224-008-9114-1
State	Published - Feb 2009

Keywords

Caching
Competitive analysis
Online algorithms
Page replacement

Access to Document

10.1007/s00224-008-9114-1

Cite this

@article{7e142ae3e3164b5793df7d75a50aaa52,

title = "The worst page-replacement policy",

abstract = "In this paper, we consider the following question: what is the worst possible page-replacement strategy? Our goal is to devise an online strategy that has the highest possible fraction of page faults as compared to the worst offline strategy. We show that there is no deterministic, online page-replacement strategy that is competitive with the worst offline strategy. We give a randomized strategy based on the {"}most-recently-used{"} heuristic and show that this strategy is the worst possible online page-replacement strategy.",

keywords = "Caching, Competitive analysis, Online algorithms, Page replacement",

author = "Kunal Agrawal and Bender, \{Michael A.\} and Fineman, \{Jeremy T.\}",

year = "2009",

month = feb,

doi = "10.1007/s00224-008-9114-1",

language = "English",

volume = "44",

pages = "175--185",

journal = "Theory of Computing Systems",

issn = "1432-4350",

number = "2",

}

TY - JOUR

T1 - The worst page-replacement policy

AU - Agrawal, Kunal

AU - Bender, Michael A.

AU - Fineman, Jeremy T.

PY - 2009/2

Y1 - 2009/2

N2 - In this paper, we consider the following question: what is the worst possible page-replacement strategy? Our goal is to devise an online strategy that has the highest possible fraction of page faults as compared to the worst offline strategy. We show that there is no deterministic, online page-replacement strategy that is competitive with the worst offline strategy. We give a randomized strategy based on the "most-recently-used" heuristic and show that this strategy is the worst possible online page-replacement strategy.

AB - In this paper, we consider the following question: what is the worst possible page-replacement strategy? Our goal is to devise an online strategy that has the highest possible fraction of page faults as compared to the worst offline strategy. We show that there is no deterministic, online page-replacement strategy that is competitive with the worst offline strategy. We give a randomized strategy based on the "most-recently-used" heuristic and show that this strategy is the worst possible online page-replacement strategy.

KW - Caching

KW - Competitive analysis

KW - Online algorithms

KW - Page replacement

UR - https://www.scopus.com/pages/publications/59549106408

U2 - 10.1007/s00224-008-9114-1

DO - 10.1007/s00224-008-9114-1

M3 - Article

AN - SCOPUS:59549106408

SN - 1432-4350

VL - 44

SP - 175

EP - 185

JO - Theory of Computing Systems

JF - Theory of Computing Systems

IS - 2

ER -

The worst page-replacement policy

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this