A note on the calculation of average working set size

ABSTRACT

Finite-length reference string of arbitrary structure are considered, and an exact expression for average working set size in terms of “corrected” interreference interval statistics is derived. An example is discussed; upper and lower bounds are obtained; and the average working set size function is shown to be efficiently obtained for a set of page sizes, in a single pass of the reference string. This work follows the developments of a paper by Denning and Schwartz, who consider infinite-length reference strings which satisfy certain statistical properties and who derive an expression relating the asymptotic average working set size to the asymptotic missing page rate function under working set replacement.

REFERENCES

• 1: Peter J. Denning , Stuart C. Schwartz, Properties of the working-set model, Communications of the ACM, v.15 n.3, p.191-198, March 1972 [doi>10.1145/361268.361281]
• 2: Edward G. Coffman, Jr. , Peter J. Denning, Operating Systems Theory, Prentice Hall Professional Technical Reference, 1973
• 3: Mattson, R.L., Gecsei, J., Slutz, D.R., and Traiger, I.L. Evaluation techniques for storage hierarchies. IBM Syst. J. 9 (1970), 78-117.
• 4: Traiger, I.L., and Slutz, D.R. One-pass techniques for the evaluation of memory hierarchies. IBM Res. Rep. RJ 892, 1971.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

General Terms:
Languages, Measurement, Performance

Keywords:
paging, program behavior, working-set model