TY - GEN

T1 - Competitive paging with locality of reference

AU - Borodin, Allan

AU - Irani, Sandy

AU - Raghavan, Prabhakar

AU - Schieber, Baruch

N1 - Publisher Copyright:
© 1991 ACM.

PY - 1991/1/3

Y1 - 1991/1/3

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=33749949514&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33749949514&partnerID=8YFLogxK

U2 - 10.1145/103418.103422

DO - 10.1145/103418.103422

M3 - Conference contribution

AN - SCOPUS:33749949514

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 249

EP - 259

BT - Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, STOC 1991

PB - Association for Computing Machinery

T2 - 23rd Annual ACM Symposium on Theory of Computing, STOC 1991

Y2 - 5 May 1991 through 8 May 1991

ER -