An empirical study of the behavior of programs in a paging environment

ABSTRACT

This paper reports initial results from an empirical study directed at the measurement of program operating behavior in those multiprogramming systems in which programs are organized into fixed length pages. The data collected from the interpretive execution of a number of paged programs is used to describe the frequency of page faults; i.e. the frequency of those instants at which an executing program requires a page of data or instructions not in main (core) memory. These data are used also for the evaluation of two page replacement algorithms and for assessing the effects on performance of changes in the amount of storage allocated to executing programs.

REFERENCES

• 1a: Corbato, F.J. and V.A. Vyssotsky, "Introduction and Overview of the Multics System,"
• 1b: Vyssotsky, V.A., F.J. Corbato, and R.M. Graham, "Structure of the Multics Supervisors,"
• 1c: Daley, R.C. and P.G. Neumann, "A General-Purpose File System for Secondary Storage," to be found in Proc. FJCC, 1965.
• 2a: Gibson, C.T., "Time-Sharing with the IBM System/360: Model 67" Proc. SJCC. 1966
• 2b: "System/360 Model 67 Time-Sharing Preliminary Technical Summary," IBM Document, Form C20-1647-0.
• 3: Jack B. Dennis, Segmentation and the Design of Multiprogrammed Computer Systems, Journal of the ACM (JACM), v.12 n.4, p.589-602, Oct. 1965 [doi>10.1145/321296.321310]
• 4: B. W. Arden , B. A. Galler , T. C. O'Brien , F. H. Westervelt, Program and Addressing Structure in a Time-Sharing Environment, Journal of the ACM (JACM), v.13 n.1, p.1-16, Jan. 1966 [doi>10.1145/321312.321313]
• 5: John W. Weil, A heuristic for page turning in a multiprogrammed computer, Communications of the ACM, v.5 n.9, p.480-481, Sept. 1962 [doi>10.1145/368834.368885]
• 6: John Fotheringham, Dynamic storage allocation in the Atlas computer, including an automatic use of a backing store, Communications of the ACM, v.4 n.10, p.435-436, Oct. 1961 [doi>10.1145/366786.366800]
• 7: Belady, L.A., "A Study of Replacement Algorithms for a Virtual Storage Computer," IBM Systems Journal, Vol. 5, No. 2, 1967.
• 8: D. J. Farber , R. E. Griswold , I. P. Polonsky, SNOBOL , A String Manipulation Language, Journal of the ACM (JACM), v.11 n.1, p.21-30, Jan. 1964 [doi>10.1145/321203.321207]
• 9: Gentlemen, W.M. and G. Sande, "Fast Fourier Transforms - For Fun and Profit," Proc. FJCC, 1966.
• 10: O'Neill, R.W., "Experience Using a Time-Shared Multi-Programming System with Dynamic Address Relocation Hardware," Proc. SJCC, 1967.
• 11: 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]
• 12: Schwartz, J.I., E.G. Coffman, and C. Weissman, "A General-Purpose Time-Sharing System," Proc. SJCC, 1964.
• 13: Shemer, J.E. and G.A. Shippey, "Statistical Analysis of Paged and Segmented Computer Systems," IEEETEC, Dec. 1966.
• 14: Norman R. Nielsen, The simulation of time sharing systems, Communications of the ACM, v.10 n.7, p.397-412, July 1967 [doi>10.1145/363427.363436]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Multiprocessing/multiprogramming/multitasking

General Terms:
Management