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 -