Use of the LRU stack depth distribution for simulation of paging behavior

ABSTRACT

Two families of probability distributions were needed for use by a virtual memory simulation model: headway between page fault distributions, and working set size distributions. All members of both families can be derived from the LRU stack depth distribution. Simple expressions for the computation of both kinds of distributions are given. Finally, examples are given of both families of distributions as computed from a published stack depth distribution.

REFERENCES

• 1: Mattson, R.L., Gecsei, J., Slutz, D.R., and Traiger, I.L. Evaluation techniques for storage hierarchies. IBM Syst. J. 9, 2 (1970), 78-117.
• 2: Spirn, F.R., and Denning, P.J. Experiments with program locality. Proc. AFIPS 1972 FJCC, AFIPS Press, Montvale, N.J., pp. 611-621.
• 3: Sager, G.R. Reproducing program memory reference behavior. Proc. Comptr. Sci. and Statist.: Seventh Annual Symp. on the Interface, Oct. 1973, pp. 41-47.
• 4: Turner, R. Simulation of paging behavior. Tech. Memo. 005- 171-003, Digital Equipment Corp., Maynard Mass., Oct. 1975.
• 5: Peter J. Denning , Stuart C. Schwartz, Properties of the working-set model, Proceedings of the third ACM symposium on Operating systems principles, p.130, October 18-20, 1971, Palo Alto, California, United States [doi>10.1145/800212.806511]

INDEX TERMS

Keywords:
LRU stack, computer system simulation, headway between page faults, paging, virtual memory, working set