Abstract
This paper develops a model for studying the optimal allocation of cache memory among two or more competing processes. It uses this model to show that, for the examples studied, the least recently used (LRU) replacement strategy produces cache allocations that are very close to optimal. The optimal fixed allocation of cache among two or more processes is an allocation for which the miss-rate derivative with respect to cache size is equal for all processes. The paper also investigates the transient in cache allocation that occurs when program behavior changes, and shows that LRU replacement moves quickly toward the steady-state allocation if it is far from optimal, but converges slowly as the allocation approaches the steady-state allocation. It describes an efficient combinatorial algorithm for determining the optimal steady-state allocation, which, in theory, could be used to reduce the length of the transient. The algorithm generalizes to multilevel cache memories. For multiprogrammed systems, the paper describes a cache-replacement policy better than LRU replacement. The policy increases the memory available to the running process until the allocation reaches a threshold time that depends both on remaining quantum time and the marginal reduction in miss rate due to an increase in cache allocation. Beyond the threshold time, the replacement policy does not increase the cache memory allocated to the running process. For all of the questions studied in this paper, the examples shown here illustrate near-optimal performance of LRU replacement, but in the absence of a bound on near optimality the question remains open whether or not LRU replacement is near-optimal in all situations likely to arise in practice. © 1992 IEEE