Analysis of Two Time-Sharing Algorithms Designed for Limited Swapping

ABSTRACT

The necessity for swapping in the operation of modern time-sharing systems constitutes the major reason for the latter's inefficiency compared to batch-processing systems. Time-sharing algorithms are discussed which are designed primarily for the reduction of swapping without intolerable changes in the waiting time distributions. A particular class of such algorithms in which conventional procedures are modified by making the quantum allocation dependent on input activity is given a more detailed treatment. In particular, queueing models corresponding to these algorithms are devised and then analyzed for the purpose of obtaining the mean waiting times conditioned on the service required. These results are then compared to those obtained for the conventional models and the comparison subsequently measured against the swapping requirements of the two classes of algorithms.

REFERENCES

• 1: COFFMAN, E. G. Stochastic models of multiple and time-shared computer operations. Rep. No. 66-38, Dep. of Eng., U. of California at Los Angeles, June 1966.
• 2: -- AND KLEINROCK, L. Some feedback queueing models of time-sharing systems. Dep. of Eng., U. of Califoraia at Los Angeles (to be published).
• 3: ----AND KRISIINAMOORTHI, B. PrelimiDary analyses of time-shared computer operation. SP-1719, System Development Corp., Aug. 1964.
• 4: CORBATS, F. J., MERWIN-DAGGETT, M., AND DALEY, R. C. An experimental time-sharin g system. Proe. AFIPS 1962 Spring Joint Comput. Conf., Vol. 21, pp. 335-344.
• 5: Leonard Kleinrock, Communication nets; stochastic message flow and delay, Dover Publications, Incorporated, 1972
• 6: B. Krishnamoorthi , Roger C. Wood, Time-Shared Computer Operations With Both Interarrival and Service Times Exponential, Journal of the ACM (JACM), v.13 n.3, p.317-338, July 1966 [doi>10.1145/321341.321342]
• 7: PATEL, N. R. A mathematical analysis of computer time-sharing systems. M.S. Thesis, Dep. of Elec. Eng., MIT, Cambridge, Mass., May 1964.
• 8: SCHRAGE, L. E. Some queueing models for a time-shared facility. Ph.D. dissertation, Dep. of Ind. Eng., Cornell U., Ithaca, N. Y., Feb. 1966.
• 9: --. The queue M/G/1 with feedback to lower priority queues. Manag. Sci. (to be published).
• 10: SCHWARTZ, J. I., COFFMAN, E. G., AND WEISSMAN, C. A general-purpose time-sharing system. Proc. AFIPS 1964 Spring Joint Comput. Conf., Vol. 25, pp. 397-411.
• 11: TAKAcs, L. Introduction to the Theory of Queues. Oxford U. Press, New York, 1962.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Algorithms, Performance, Theory, Verification