Efficient Methods for Calculating the Success Function of Fixed-Space Replacement Policies

摘要

Efficient methods are discussed for calculating the success function of replacement policies used to manage very large fixed size caches. Such problems arise in studying the caching of files on disk. Earlier work by Coffman and Randell, and Mattson et al. A class of replacement policies is characterized which it is possible to evaluate the success function for a single cache size in time O(n*log(s)), where n is the number of memory references in the trace and s is the size of cache. An algorithm is constructed to evaluate the success function for the Least Recently Used replacement policy in time O(n*log(s)), for cache sizes smaller than s. This algorithm runs in bounded memory, O(s). It is also shown how to modify Bennett and Kruskal's algorithm to run in bounded space. The two algorithms have the same asymptotic running times (within a constant factor). Measured running times for the classic LRU algorithm, Bennett and Kruskal's algorithm, and the new algorithm are compared. The impace of variable size segments (files, rather than fixed size pages), and deletions on algorithms for calculating success functions is considered. (ERA citation 06:034193)