Time-Shared Computer Operations With Both Interarrival and Service Times Exponential

ABSTRACT

The concept of time-shared computer operations is briefly described and a model of a time-sharing system is proposed, based on the assumption that both interarrival and service times possess an exponential distribution. Although the process described by this model is non-Markovian, an imbedded Markov chain is analyzed by exploiting the fact that the instants of completion of a “quantum” of service are regeneration points. It is shown that user congestion possesses a limiting distribution, and the method of generating functions is used to derive this distribution. The concept of cycle time is discussed and two measures of cycle time developed for a scheduling discipline employing a single queue. Finally, a number of numerical examples are presented to illustrate the effect of the system parameters upon user congestion, system response time and computer efficiency.

REFERENCES

• 1: COFFMAN, E. G., AND KISNAMOORTHI, B. Preliminary analyses of time-shared eomputer operation. SP-1719, System Development Corp., Santa Moniea, Aug. 1964.
• 2: CORBATO, F. T., MERWIN-DAGGET M., AND DALEY, R.C. An experimental time-sharing system. Proc. SJCC, Vol. 21, t962, pp. 335--344.
• 3: KIEINROCK, L. Message Delay in Communication Nets with Storage. McGraw Hill, New York, 1964.
• 4: McCARTHY, J. S., BOILEN, E., AND LICKLIDER, Z. C.R. A time-sharing debugging system for a small computer. Proc. SJCC, 1963, pp. 51-57.
• 5: SCHWARTZ, J. I., COFFMAN E. G., AND WEISSMAN, C. A general purpose time-sharingsystem. Proc. SJCC, 1964, pp. 397--411.
• 6: ScawAaTZ, J. I., COFFMAN, E. G., AND WEISSMAN, C. Potentials of a large scale timesharing system. Proc. Second Congress of Inf. Sciences, Nov. 1964. (Also available as SP-1723, System Development Corp., Santa Monica.)
• 7: BHAIIICI-REID, A.T. Elements of the Theory of Markov Processes and Their Applicatiots. McGraw Hill, New York, 1960, pp. 419--425.
• 8: CHUNG, K. L. Markov Chains with Stationary Transition Probabilities. Springer-Verlag, Berlin, 1960, p. 87.
• 9: FELIma, WIILIA. An Introduction to Probability Theory and Its Applications, Vol. l. John Wiley, New York, 1957.
• 10: Ivan Flores, Derivation of a Waiting-Time Factor for a Multiple-Bank Memory, Journal of the ACM (JACM), v.11 n.3, p.265-282, July 1964 [doi>10.1145/321229.321231]
• 11: KalSrrNAMOORTrlI, B. The stationary behavior of a time-sharing system under Poisson assumptions. SP-2090, System Development Corp., Santa Monica, Aug. 1965; to appear OPSEA RCH, d. Indian Operat. Res. Soc.

INDEX TERMS

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

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

General Terms:
Measurement, Performance, Theory