On Paging with Locality of Reference

Susanne Albers, Lene Monrad Favrholdt, Oliver Giel

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


Motivated by the fact that competitive analysis yields too pessimistic results when applied to the paging problem, there has been considerable research interest in refining competitive analysis and in developing alternative models for studying online paging. The goal is to devise models in which theoretical results capture phenomena observed in practice.In this paper we propose a new, simple model for studying paging with locality of reference. The model is closely related to Denning's working set concept and directly reflects the amount of locality that request sequences exhibit. We demonstrate that our model is reasonable from a practical point of view.We use the page fault rate to evaluate the quality of paging algorithms, which is the performance measure used in practice. We develop tight or nearly tight bounds on the fault rates achieved by popular paging algorithms such as LRU, FIFO, deterministic Marking strategies and LFD. It shows that LRU is an optimal online algorithm, whereas FIFO and Marking strategies are not optimal in general. We present an experimental study comparing the page fault rates proven in our analyses to the page fault rates observed in practice. This is the first such study for an alternative/refined paging model.
Original languageEnglish
Title of host publicationACM Symposium on Theory of Computing
Number of pages10
Publication date2002
Publication statusPublished - 2002
EventACM Symposium on Theory of Computing - Montreal, Canada
Duration: 24. Aug 2010 → …
Conference number: 34


ConferenceACM Symposium on Theory of Computing
Period24/08/2010 → …


Dive into the research topics of 'On Paging with Locality of Reference'. Together they form a unique fingerprint.

Cite this