The dependence of computer system queues upon processing time distribution and central processor scheduling

ABSTRACT

The stationary distribution of the number of jobs being served by a processor-sharing central server is independent of both the distribution of service times and the distribution of interarrival times when those distributions have rational Laplace-Stieltjes transforms. This result holds for both finite source and infinite source models. The steady state is identical to the steady state when all distributions are exponential. The expected response time, queue size, and central processor idle time of the finite source model under processor-sharing and FCFS scheduling are compared. These measures of system performance are all larger under processor-sharing for a class of central processor service time distributions with a coefficient of variation less than one. The measures are all smaller under processor-sharing for a class of distributions with a coefficient of variation greater than one. Experiments with data collected from actual computer systems indicate that these results extend to more general models and have practical applications in existing computer systems.

REFERENCES

• 1: I. Adiri , B. Avi-Itzhak, A Time-Sharing Queue with a Finite Number of Customers, Journal of the ACM (JACM), v.16 n.2, p.315-323, April 1969 [doi>10.1145/321510.321523]
• 2: Baskett, F. Mathematical Models of Multi-programmed Computer Systems. TSN-17, Computation Center, The University of Texas at Austin, January, 1971.
• 3: Bryan, G. E. Joss: 20,000 Hours at the Console: A Statistical Summary. Proc. AFIPS 1967 Fall Joint Computer Conf., Washington, D.C. 1967, Vol. 31, 769-777.
• 4: Jeffrey Buzen, Analysis of system bottlenecks using a queueing network model, Proceedings of the SIGOPS workshop on System performance evaluation, p.82-103, January 1971 [doi>10.1145/800024.808355]
• 5: E. G. Coffman, Jr. , R. R. Muntz, Models of Pure time-sharing disciplines for resource allocation, Proceedings of the 1969 24th national conference, p.217-228, August 26-28, 1969 [doi>10.1145/800195.805934]
• 6: Cox, D. R. A Use of Complex Probabilities in the Theory of Stochastic Processes, Proc. Camb. Phil. Soc., 51 (1955), 313-319.
• 7: 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]
• 8: J. M. McKinney, A Survey of Analytical Time-Sharing Models, ACM Computing Surveys (CSUR), v.1 n.2, p.105-116, June 1969 [doi>10.1145/356546.356549]
• 9: Morse, P. M. Queues, Inventories, and Maintenance. Wiley, New York, 1958.
• 10: Scherr, A. L. An Analysis of Time-shared Computer Systems. MIT Press, Cambridge, Mass., 1967.
• 11: Schrage, L. E. Some Queueing Models for a Time-Shared Facility. Ph.D. Thesis, Cornell University, 1966.
• 12: Stephen Sherman , Forest Baskett, III , J. C. Browne, Trace driven modeling and analysis of CPU scheduling in a multi-programming system, Proceedings of the SIGOPS workshop on System performance evaluation, p.173-199, January 1971 [doi>10.1145/800024.808358]
• 13: Takás, L. On a Stochastic Process Concerning Some Waiting Time Problems. Theory of Probability and its Applications, 11,1 (1957), 90-103.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Queueing theory

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

General Terms:
Management