Computation of page fault probability from program transition diagram

ABSTRACT

An algorithm is given for calculating page fault probability in a virtual memory system operating under demand paging with various memory sizes and replacement rules. A first order Markov model of program behavior is assumed, and a representation of the system based on memory states, control states, and memory substates is presented. The algorithm is general in the sense that the page fault probabilities can be calculated for nonpredictive replacement rules applied to any program represented by a one-step Markov chain. A detailed example is given to illustrate the algorithm for Random and Least Recently Used (LRU) replacement rules.

REFERENCES

• 1: Alfred V. Aho , Peter J. Denning , Jeffrey D. Ullman, Principles of Optimal Page Replacement, Journal of the ACM (JACM), v.18 n.1, p.80-93, Jan. 1971 [doi>10.1145/321623.321632]
• 2: Beizer, B. Analytic techniques for the statistical evaluation of program running time. Proc. AFIPS 1970 FJCC, Vol. 37, AFIPS Press, Montvale, N. J., pp. 519-524.
• 3: Belady, L.A. A study of replacement algorithms for a virtualstorage computer, lBMSystems J. 5, 2 (1966), 78-101.
• 4: Chu, W.W., and Opderbeck H. The page fault frequency replacement algorithm. Proc. AFIPS 1972 FJCC, Vol. 41, Pt. 1, AFIPS Press, Montvale, N. J., pp. 597-609.
• 5: 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]
• 6: Peter J. Denning, Virtual Memory, ACM Computing Surveys (CSUR), v.2 n.3, p.153-189, Sept. 1970 [doi>10.1145/356571.356573]
• 7: Hatfield, D.J. Experiments on page size, program access patterns and virtual memory performance. IBM J. R&D 16, I (Jan. 1972), 58-66.
• 8: Kemeny, J.G., and Snell, J.L. Finite Markov Chains. D. Van Nostrand, Princeton, N.J., 1960.
• 9: King, W. F. Analysis of paging algorithms. IBM Res. Rep. RC 3288, Mar. 17, 1971.
• 10: David Martin , Gerald Estrin, Models of Computations and Systems—Evaluation of Vertex Probabilities in Graph Models of Computations, Journal of the ACM (JACM), v.14 n.2, p.281-299, April 1967 [doi>10.1145/321386.321391]
• 11: 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.
• 12: Parmelee, R.P., Peterson, T.I., Tillman, C.C., and Hatfield, D.J. Virtual storage and virtual machine concepts. 1BMSyst. J 11, 2 (1972), 99-130.
• 13: C. V. Ramamoorthy, Analysis of computational systems: Discrete Markov analysis of computer programs, Proceedings of the 1965 20th national conference, p.386-392, August 24-26, 1965, Cleveland, Ohio, United States [doi>10.1145/800197.806061]
• 14: Shedler, G. S., and Tung C. Locality in page reference strings. IBM Res. Rep. RJ932, Oct. 29, 1971.
• 15: Spirn, J.R., and Denning, P.J. Experiments with program locality. Proc. AFIPS 1972 SJCC, Vol. 41, Pt. 1, AFIPS Press, Montvale, N. J., pp. 611-621.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Virtual memory

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms

Keywords:
Markov model, demand paging, page fault, page fault probability, program behavior, program model, replacement rule, virtual memory