Asymptotic miss ratios over independent references

Abstract

It is proven that under the assumption of independent references, the (apparently analytically and computationally intractable) expected LRU (least recently used) miss ratio with main memory size CAP can be approximated arbitrarily closely by the (analytically and computationally tractable) expected working-set miss ratio with expected working-set size CAP, as the size of the database goes to infinity. Thier common asymptotic value is given by a tractable formula involving integrals. An immediate corollary of the representation is the asymptotic independence of miss ratio from page size in the independent reference model and in some generalizations of this model. This result also has implications about the effect on miss ratio of variable or fixed partitioning of main memory, in case of multiprogramming. Furthermore, in certain database environments, we can answer the question as to how the size of main memory must vary in order to maintain the same miss ratio, when the size of the database increases. The methods of this paper are extended to give an asymptotic formula for the miss ratio under VMIN, the optimal variable-space page replacement algorithm under demand paging. © 1977 Academic Press, Inc.