A large body of literature has examined cache replacement algorithms.
Examples of buffer cache replacement algorithms include the LRU
[9,6], GCLOCK [36,19], First
in First Out (FIFO), MRU, LFU, Random, FBR [31], LRU-
[15], 2Q [23], and LFRU [14]. In the
spectrum of off-line algorithms, Belady's OPT algorithm and WORST
algorithm [2,17] are widely used to derive a lower
and upper bound on the cache miss rate. Other closely related works
include Muntz and Honeyman's file server caching
study [28] and Eager and Bunt's disk cache study
[43]. Most of these works have been described in our
Introduction and Methodology sections.
Cache replacement policies have been intensively studied in various contexts in the past, including processor caches [38], paged virtual memory systems [36,3,40,4,12,4,34,13,10], and disk caches [37]. Although several studies [1,20,24] focus on two level processor cache design issues, their conclusions do not apply to software based L2 buffer cache designs because the former has more restrictions. Some analytical models of the storage hierarchies have been given in [21,25].
Many past studies have used metrics such as LRU stack distance [17], marginal distribution of stack distances [18] or distance string models [39] to analyze the temporal locality of programs. However, the proposed LRU stack distance models were designed specifically for stack replacement algorithms like LRU. Moreover, distance string models do not capture the long-range relationships among references. O'Neil and et. al. recently proposed the inter-reference gap (IRG) model [30] to characterize temporal localities in program behavior. The IRG value for an address in a trace represents the time interval between successive references to the same address. But this model looks at each address separately and does not look at the overall distribution of the IRG values. Thesefore, it cannot well capture global access behavior.
Our study uses the distribution of temporal distances to measure temporal locality. The idea of using multiple queues with feedback has appeared in process scheduling [26,41]. With this method, the priority of a process increases on an I/O event and decreases when its time slice expires without an I/O event.