Competitive paging with locality of reference

Allan Borodin, Sandy Irani, Prabhakar Raghavan, Baruch Schieber

Research output: Chapter in Book/Report/Conference proceedingConference contribution

61 Scopus citations


The Sleator-Tarjan competitive analysis of paging [19] gives us the ability to make strong theoretical statements about the performance of paging algorithms without making probabilistic assumptions on the input. Nevertheless practitioners voice reservations about the model, citing its inability to discern between LRU and FIFO (algorithms whose performances differ markedly in practice), and the fact that the theoretical competitiveness of LRU is much larger than observed in practice. In addition, we would like to address the following important question: given some knowledge of a program's reference pattern, can we use it to improve paging performance on that program? We address these concerns by introducing an important practical element that underlies the philosophy behind paging: locality of reference. We devise a graph-Theoretical model, the access graph, for studying locality of reference. We use it to prove results that address the practical concerns mentioned above. In addition, we use our model to address the following questions: How well is LRU likely to perform on a given program? Is there a universal paging algorithm that achieves (nearly) the best possible paging performance on every program? We do so without compromising the benefits of the Sleator-Tarjan model, while bringing it closer to practice.

Original languageEnglish (US)
Title of host publicationProceedings of the 23rd Annual ACM Symposium on Theory of Computing, STOC 1991
PublisherAssociation for Computing Machinery
Number of pages11
ISBN (Electronic)0897913973
StatePublished - Jan 3 1991
Externally publishedYes
Event23rd Annual ACM Symposium on Theory of Computing, STOC 1991 - New Orleans, United States
Duration: May 5 1991May 8 1991

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
VolumePart F130073
ISSN (Print)0737-8017


Conference23rd Annual ACM Symposium on Theory of Computing, STOC 1991
Country/TerritoryUnited States
CityNew Orleans

All Science Journal Classification (ASJC) codes

  • Software

Cite this