An analysis of the performance of the page fault frequency (PFF) replacement algorithm.

ABSTRACT

Most of the replacement algorithms devised and implemented largely depend on program behavior, in other words, to optimally select the parameters of these algorithms program behavior or at least a probability model of it should be known. The page fault frequency (PFF) algorithm adapts to dynamic changes in program behavior during execution. Therefore its performance is expected to be less dependent on prior knowledge of the program behavior during execution. Therefore its performance is expected to be less dependent on prior knowledge of the program behavior and input data. The PFF algorithm uses the measured page fault frequency (by actually monitoring the inter-page fault interval) as the basic parameter for memory allocation decision process. In order to analyze the performance of the PFF algorithm, a mathematical model was developed. The resultant random process is the memory space allocation for a program as a function of the processor time (virtual time). This random process can be analyzed using the method of imbedded Markov chains. The parameter obtained from this analysis are the distributions of the memory allocation during processing interval and during page waiting intervals, the average page fault rate and the expected space time product accumulated by the program. The input parameters for the model were obtained from address traces of two programs. The results of the model were validated by simulation.

REFERENCES

• 1: Arvind, "Experiments to evaluate working set properties," Dept. of EE, University of Minnesota, TR NSF-CCA-CJ 32504, Nov. 1973.
• 2: Arvind , R. Y. Kain , E. Sadeh, On reference string generation processes, Proceedings of the fourth ACM symposium on Operating system principles, p.80-87, January 1973
• 3: W.W. Chu and H. Opderbeck, "The page fault frequency replacement algorithm," FJCC 1972 AFIPS 41, pp. 597-609.
• 4: E. G. Coffman, Jr. , Thomas A. Ryan, Jr., A study of storage partitioning using a mathematical model of locality, Communications of the ACM, v.15 n.3, p.185-190, March 1972 [doi>10.1145/361268.361280]
• 5: Peter J. Denning, Virtual Memory, ACM Computing Surveys (CSUR), v.2 n.3, p.153-189, Sept. 1970 [doi>10.1145/356571.356573]
• 6: P.J. Denning, J.E. Savage and J.E. Spirn, "Models of locality in program behavior," Princeton University, Dept. of EE, Computer Science TR-107, April 1972.
• 7: P.J. Denning, "On modelling program behavior," SJCC 1972, AFIPS 40, pp. 937-944.
• 8: 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]
• 9: N. Feller, An Introduction to Probability Theory and Its Applications, Vol. II, Wiley.
• 10: R.Y. Kain, "How to evaluate page replacement algorithm" Technical Report, Mpls., Minnesota, Oct. 1975.
• 11: H. Opderback and W.W. Chu, "Performance of the PFF replacement algorithm in a multiprogramming environment," IFIPS, Stockholm, Aug. 1974.
• 12: Eitan Sadeh, Analysis of the page fault frequency replacement algorithm., 1975
• 13: G.H. Shedler and C. Tung, "Locality in page reference strings," SIAM J. Comput. 1, 3, Sept. 1972.
• 14: J.R. Spirn and P.J. Denning, "Experiments with program locality," FJCC 1972 AFIPS 41, pp. 611-621.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Virtual memory

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis

General Terms:
Algorithms, Performance, Verification

Keywords:
Imbedded markov chain, Memory requirement process, PFF replacement algorithm, Page fault rate, Paged virtual memory systems, Reference string, Space time product