COMPETITIVE PAGING WITH LOCALITY OF REFERENCE

The Sleator-Tarjan competitive analysis of paging (Comm. ACM 28 (1985) , 202-208) gives us the ability to make strong theoretical statements about the performance of paging algorithms without making probabilisti c assumptions on the input. Nevertheless practitioners voice reservati ons about the model, citing its inability to discern between LRU and F IFO (algorithms whose performances differ markedly in practice), and t he fact that the theoretical comptitiveness of LRU is much larger than observed in practice, In addition, we would like to address the follo wing 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 eleme nt that underlies the philosophy behind paging: locality of reference. We devise a graph-theoretical model, the access graph, for studying l ocality of reference. We use it to prove results that address the prac tical concerns mentioned above, In addition, we use our model to addre ss the following questions: How well is LRU likely to perform on a giv en program? Is there a universal paging algorithm that achieves (nearl y) the best possible paging performance on every program? We do so wit hout compromising the benefits of the Sleator-Tarjan model, while brin ging it closer to practice. (C) 1995 Academic Press, Inc.