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.
Fiat and Rosen @cite_11 present an access graph based heuristic that is truly online and makes use of a (weighted) dynamic access graph. In this sense we emulate their concept. While the Fiat and Rosen algorithm is experimentally interesting in that it seems to beat , it is certainly not strongly competitive, and is known to have a competitive ratio of @math .
@cite_11
2068714069
In this paper we devise new paging heuristics motivated by the access graph model of paging. Unlike the access graph model and the related Markov paging model our heuristics are truly on-line in that we do not assume any prior knowledge of the program just about to be executed. The Least Recently Used heuristic for paging is remarkably good, and is known experimentally to be superior to many of the suggested alternatives on real program traces. Experiments we ve performed suggest that our heuristics beat LRU fairly consistently, over a wide range of cache sizes and programs. The number of page faults can be as low as 1 2 the number of page faults for LRU and is on average 7 to 9 percent less than the number of faults for LRU. (Depending on how this average is computed.) We have built a program tracer that gives the page access sequence for real program executions of 200 - 3,300 thousand page access requests, and our simulations are based on 25 of these program traces. Overall, we have performed several thousand such simulations. While we have no real evidence to suggest that the programs we ve traced are typical in any sense, we havemore » made use of an experimental open_quotes protocol close_quotes designed to avoid experimenter bias. We strongly emphasize that our results are only preliminary and that much further work needs to be done.« less