Experimental studies of access graph based heuristics: beating the LRU standard?
Amos Fiat, Ziv Rosen · 1997
In this paper we devise new paging heuristics motivated by the access graph model of paging [2]. Unlike the access graph model [2, 7, 4] and the related Markov paging model [8] our heuristics are truly online 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 [17]. 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 ...