Time-shared Systems: a theoretical treatment

ABSTRACT

Time-shared computer (or processing) facilities are treated as stochastic queueing systems under priority service disciplines, and the performance measure of these systems is taken to be the average time spent in the system. Models are analyzed in which time-shared computer usage is obtained by giving each request a fixed quantum Q of time on the processor, after which the request is placed at the end of a queue of other requests; the queue of requests is constantly cycled, giving each user Q seconds on the machine per cycle. The case for which Q → 0 (a processor-shared model) is then analyzed using methods from queueing theory. A general time-shared facility is then considered in which priority groups are introduced. Specifically, the pth priority group is given gpQ seconds in the processor each time around. Letting Q → 0 gives results for the priority processor-shared system. These disciplines are compared with the first-come-first-served disciplines. The systems considered provide the two basic features desired in any time-shared system, namely, rapid service for short jobs and the virtual appearance of a (fractional capacity) processor available on a full-time basis. No charge is made for swap time, thus providing results for “ideal” systems. The results hold only for Poisson arrivals and geometric (or exponential) service time distributions.

REFERENCES

• 1: FANO, R.M. The MAC system: the computer utility approach. IEEE Spectrum2, No. I (Jan. 1965), 56-64.
• 2: LICHTENEERGER, W. W. AND DIRTLE, M.W. A facility for experimentation in maR-machine interactions. Proc. AFIPS 1965 Fall Joint Comput. Conf., Vol. 27, Pt. I, 1965, pp. 589-598.
• 3: FORGIE, J. W. A time- and memory-sharing executive program for quick response on-line applications. Proc. AFIPS 1965 Fall Joint Comptit. Conf., Vol. 27, Pt. 1, 1965, pp. 599-609.
• 4: MCCARTHY, J. Time-sharing computer systems. In Management and the Computer of the Future, M. Greenberger, Ed. MIT Press, Cambridge, Mass., 1962, pp. 221-236.
• 5: SCHWARTZ, J. I., COFFMAN, E. G. AND WEISSAN, C. A general purpose time-sharing system. Proc. AFIPS, 1962 Spring Joint Comput. Conf., 1962, pp. 335-344.
• 6: KLEINROCK, L. Analysis of a time-shared processor. Naval Res. Logistics Quart. 11, 10 (March 1964), 59-73.
• 7: LITTLE, J. D.C. A proof of the queueing formula L = kW. Operations Res. 9 (1961), 383- 387.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization

General Terms:
Measurement, Performance, Theory, Verification