The access graph model for paging, defined by (, 1991) and studied in (, 1992) has a number of troubling aspects. The access graph has to be known in advance to the paging algorithm and the memory required to represent the access graph itself may be very large. We present a truly online strongly competitive paging algorithm in the access graph model that does not have any prior information on the access sequence. We give both strongly competitive deterministic and strongly competitive randomized algorithms. Our algorithms need only O(k log n) bits of memory, where k is the number of page slots available and n is the size of the virtual address space, i.e., no more memory than needed to store the virtual translation tables for pages in memory. In fact, we can reduce this to O(k log k) bits using appropriate probabilistic data structures. We also extend the locality of reference concept captured by the access graph model to allow changes in the behavior of the underlying process. We formalize this by introducing the concept of an "extended access graph". We consider a graph parameter spl Delta that captures the degree of change allowed. We study this new model and give algorithms that are strongly competitive for the (unknown) extended access graph. We can do so for almost all values of spl Delta for which it is possible.
Borodin al @cite_8 also consider deterministic uniform paging algorithms. They prove the existence of an optimal paging algorithm in PSPACE( @math ). They give a natural uniform paging algorithm, called , and prove that obtains a competitive ratio no worse than @math times the asymptotic competitive ratio for the graph. This result is improved in a paper by Irani, Karlin and Phillips @cite_6 in which it is shown that is very strongly competitive. The same paper also presents a very strongly competitive algorithm for a sub-class of access graphs, called .
@cite_6 @cite_8
2073713788 2069162168
What is the best paging algorithm if one has partial information about the possible sequences of page requests? We give a partial answer to this question by presenting the analysis of strongly competitive paging algorithms in the access graph model. This model restricts page requests so that they conform to a notion of locality of reference given by an arbitrary access graph. We first consider optimal algorithms for undirected access graphs. [ Proc. 23rd ACM Symposium on Theory of Computing, 1991, pp. 249--259] define an algorithm, called FAR, and prove that it is within a logarithmic factor of the optimal online algorithm. We prove that FAR is in fact strongly competitive, i.e., within a constant factor of the optimum. For directed access graphs, we present an algorithm that is strongly competitive on structured program graphs---graphs that model a subset of the request sequences of structured programs. The Sleator-Tarjan competitive analysis of paging (Comm. ACM28 (1985), 202-208) 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 comptitiveness 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.