Degree of multiprogramming in page-on-demand systems

ABSTRACT

A simple stochastic model is described which offers a base for understanding the relationship between the number of programs permitted to share memory (the degree of multiprogramming), drum traffic rates, and central processing unit utilization in page-on-demand, multiprogrammed, time-shared computer systems. The model preserves, as a key feature, the property of page-demand statistics which implies a “burst” of page demands at the beginning of any job or quantum execution. The model, a Markov chain, is analyzed numerically and the results are presented graphically for a wide range of key environment-descriptive parameters. Implications of the results to time-shared system design and programming are discussed, and a calculation of the optimal degree of multiprogramming for a wide range of parameters is presented graphically.

REFERENCES

• 1: 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]
• 2: John L. Smith, Microprogamming under a page on demand strategy, Communications of the ACM, v.10 n.10, p.636-646, Oct. 1967 [doi>10.1145/363717.363763]
• 3: D. P. Gaver, Jr., Probability Models for Multiprogramming Computer Systems, Journal of the ACM (JACM), v.14 n.3, p.423-438, July 1967 [doi>10.1145/321406.321407]
• 4: 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]
• 5: 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]
• 6: WALLACE, V. L., AND ROSENBERG, R.S. RQA-1, the reeursive queue analyzer. Tech. Rep. No. 2, Syst. Eng. Lab., U. of Michigan, Ann Arbor, Mich. Feb. 1966.
• 7: G. Oppenheimer , N. Weizer, Resource management for a medium scale time-sharing operating system, Communications of the ACM, v.11 n.5, p.313-322, May 1968 [doi>10.1145/363095.363140]
• 8: E. G. Coffman , L. C. Varian, Further experimental data on the behavior of programs in a paging environment, Communications of the ACM, v.11 n.7, p.471-474, July 1968 [doi>10.1145/363397.363398]
• 9: 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]
• 10: PINKERTON, W.B. Program behavior and control in virtual storage computer systems, Tech. Rep. 4, Concomp Project, U. of Michigan, Ann Arbor, Mich. Apr. 1968.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

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

Keywords:
Markovian computer models, demand paging, memory management, operating systems, page-on-demand, scheduling strategies, time-sharing multiprogramming