Asymptotic Miss Ratios over Independent References

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 dosely by the (analyt-ically and computationally tractable) expected working-set miss ratio with expected working-set size CAP, as the size of the database goes to infinity. Their 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 in-dependent 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