2007 | OriginalPaper | Buchkapitel
The Worst Page-Replacement Policy
verfasst von : Kunal Agrawal, Michael A. Bender, Jeremy T. Fineman
Erschienen in: Fun with Algorithms
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper, we consider the question: what is the worst possible page-replacement strategy? Our goal is to devise an online strategy that has the highest possible fraction of misses 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 is the worst possible online page-replacement strategy.