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.
['Kunal Agrawal', 'Michael A. Bender', 'Jeremy T. Fineman']
The Worst Page-Replacement Policy