A simple linear model of demand paging performance

ABSTRACT

Predicting the performance of a proposed automatically managed multilevel memory system requires a model of the patterns by which programs refer to the information stored in the memory. Some recent experimental measurements on the Multics virtual memory suggest that, for rough approximations, a remarkably simple program reference model will suffice. The simple model combines the effect of the information reference pattern with the effect of the automatic management algorithm to produce a single, composite statement: the mean number of memory references between paging exceptions increases linearly with the size of the paging memory. The resulting model is easy to manipulate, and is applicable to such diverse problems as choosing an optimum size for a paging memory, arranging for reproducible memory usage charges, and estimating the amount of core memory sharing.

REFERENCES

• 1: Mattson, R.L., et al. Evaluation techniques for storage hierarchies. IBM Systems J. 9, 2 (1970), 78-117.
• 2: Michael D. Schroeder, Performance of the GE-645 associative memory while Multics is in operation, Proceedings of the SIGOPS workshop on System performance evaluation, p.227-245, January 1971 [doi>10.1145/800024.808361]
• 3: A. Bensoussan , C. T. Clingen , R. C. Daley, The Multics virtual memory: concepts and design, Communications of the ACM, v.15 n.5, p.308-318, May 1972 [doi>10.1145/355602.361306]
• 4: Corbate, F. J. A paging experiment with the Multics system. in Ingard, bt Honor of P.M. Morse, M.I.T. Press, Cambridge, Mass., 1969, pp. 217-228.
• 5: L. C. Varian , E. G. Coffman, An empirical study of the behavior of programs in a paging environment, Proceedings of the first ACM symposium on Operating System Principles, p.16.1-16.13, January 1967 [doi>10.1145/800001.811682]
• 6: Gerald H. Fine , Calvin W. Jackson , Paul V. Mc Isaac, Dynamic program behavior under paging, Proceedings of the 1966 21st national conference, p.223-228, January 1966 [doi>10.1145/800256.810701]
• 7: Brawn, Barbara S., and Gustavson, Frances G. Program behavior in a paging environment. Proc. AFIPS 1968 FJCC, Vol. 33, Pt. 2, AFIPS Press, Montvale, N.J., pp. 1019-1032.
• 8: Barbara S. Brawn , Frances G. Gustavson , Efrem S. Mankin, Sorting in a paging environment, Communications of the ACM, v.13 n.8, p.483-494, Aug. 1970 [doi>10.1145/362705.362710]
• 9: O'Neill, R. W., Experience using a time-shared multiprogramming system with dynamic address relocation hardware. Proc. AFIPS 1966 SJCC, Vol. 30, AFIPS Press, Montvale, N.J., pp. 611-621.
• 10: Belady, L.A. A study of replacement algorithms for a virtualstorage computer, lBMSystems J. 5, 2 (1966), 78-101.
• 11: Baylis, M.H.K., et al. Paging studies made on the I.C.T. Atlas computer. Proe. IFIP Congress 68, North Holland Pub. Co., Vol. 2, pp. 831-837.
• 12: Peter J. Denning, The working set model for program behavior, Communications of the ACM, v.11 n.5, p.323-333, May 1968 [doi>10.1145/363095.363141]
• 13: L. A. Belady , C. J. Kuehner, Dynamic space-sharing in computer systems, Communications of the ACM, v.12 n.5, p.282-288, May 1969 [doi>10.1145/362946.363002]
• 14: Taylor, A. Should the charges vary with each job execution? Computerworld 5, 44 (Nov. 3, 1971), 7.
• 15: Sekino, Akira. Performance evaluation of multiprogrammed time-shared computer system. Ph.D. Th., M.I.T., Dept. of Electrical Engineering, Sept. 1972. (Available as Project MAC Tech. Rep. TR-103.)

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Experimentation, Measurement, Performance

Keywords:
Multics, associative memory, demand paging, memory models, memory usage accounting, multilevel memory systems, paging, performance measurement, program models, virtual memory