In thia paper we are concerned with efficient methods for calculat ing the auccess function of
replacement policies used to manage very largo fixed size caches. Such problems arise in
studying tho caching of filos on disk, Wo roview earlier work by Coffman and Randell, and
Mattson et al. Wo characterizo a class of replacement policies for which it is possiblc to
ovaluato the success function for a single cache size in timo O (n* log (s)), where n is the
number of memory referonces in the trace and s ia the size of cache. We then construct an …