Some Mathematical Considerations of Time-Sharing Scheduling Algorithms

ABSTRACT

A mathematical derivation of expected response time is presented for selected cyclic and priority scheduling disciplines, thereby demonstrating analytic techniques which may be utilized to evaluate such servicing doctrines. To illustrate the constant time quantum (round-robin) results, a hypothetical is defined and resolved.

REFERENCES

• 1: PATEL, NITIN R. A mathematical analysis of computer time-sharing systems. Interim Tech. Rep. No. 20, Army Res. OIfice (Durham), Grant No. DA-ARO (D)-31-124-G158, Oper. Res. Center, MIT, 1964.
• 2: A. L. Scherr, AN ANALYSIS OF TIME-SHARED COMPUTER SYSTEMS, Massachusetts Institute of Technology, Cambridge, MA, 1965
• 3: KLEINROCK, L. Analysis of a time-shared processor. Nay. Res. Logistics Quart. 11, 10 (March 1964), 59-73.
• 4: CHANG, W. A queuing model for a simple case of time-sharing. IBM Syst. J. 5, 2 (1966), 115-125.
• 5: SAATY, T. L. Elements of Queueing Theory. McGraw-Hill, New York, 1961.
• 6: BIOCKMEYER, E. HALSTROM, H. L., AND JENSEN, ARNE. The life and works of A. K. Erlang. Trans. Danish Acad. Tech. Sci., No. 2, Copenhage Telephone Company, Copenhagen, 1948.
• 7: ConBAro, F. J., MERWIN-DAGGE M., ND DAIEY, R .C . An experimental time-sharing system. Proc. Spring Joint Comput. Conf., Vo. 21, 1962, pp. 335-344.
• 8: COBHM, A. Priority assignment in waiting line problems. J. Operations Res. Soc. Am. 2 (1954), 70--76.
• 9: SYSKI, R. Introduclion to Congestion Theory in Telephone Systems. Oliver and Boyd, London, 1960.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Scheduling

General Terms:
Algorithms, Measurement, Performance, Theory