Models of Pure time-sharing disciplines for resource allocation

ABSTRACT

Pure time sharing (PTS) disciplines are those which involve in some way the simultaneous sharing of a processor or other service facility by more than one job at a time. Implicit is the requirement that the total processor capacity is fixed so that individual job processing rates are reduced according as the number of jobs sharing the processor increases. In this paper the general class of such disciplines is surveyed and studied by the investigation of the behavior of mathematical models. By the introduction of appropriate algorithms it is shown how these disciplines can be applied to static processor scheduling problems in which total schedule time is to be minimized. Application of these disciplines to queueing systems is also examined, yielding characterizations which classify the performance measures optimized. The PTS disciplines discussed include one which bases scheduling decisions on the elapsed times of jobs and one which bases decisions on the expected remaining processing times of jobs. The simplest PTS discipline studied is one which makes no explicit use of any processing time information.

REFERENCES

• 1: Muntz, R.R., and Coffman, E.G., "Multiprocessor Scheduling of Computation Graphs," Report No. 63, Computer Science Laboratory, Electrical Engineering Department, Princeton University, June 1968. (To appear Journal of the ACM.)
• 2: Muntz, R.R., and Coffman, E.G., "The Optimal Sequencing of Computation Graphs on Two-Processor Systems," Report No. 68, Computer Science Laboratory, Electrical Engineering Department, Princeton University, July 1968.
• 3: E. G. Coffman, Jr. , R. R. Muntz , H. Trotter, Waiting Time Distributions for Processor-Sharing Systems, Journal of the ACM (JACM), v.17 n.1, p.123-130, Jan. 1970 [doi>10.1145/321556.321568]
• 4: Miller, L.W., and Schrage, L.E., "The Queue M/G/1 with the Shortest Remaining Processing Time Discipline," Rep. P-3263, RAND Corp., Santa Monica, Calif., November 1965.
• 5: McNaughton, R., "Scheduling with Deadlines and Loss Functions," Management Science, 6, No. 1, October 1959.
• 6: Little, J.D.C., "A Proof for the Queueing Formula L &equil; &lgr;W," Opns. Res., 2, No. 3, May 1961.
• 7: Takas, L., Introduction to the Theory of Queues, Oxford U. Press, New York, 1962.
• 8: Edward G. Coffman , Leonard Kleinrock, Feedback Queueing Models for Time-Shared Systems, Journal of the ACM (JACM), v.15 n.4, p.549-576, Oct. 1968 [doi>10.1145/321479.321483]
• 9: Leonard Kleinrock, Time-shared Systems: a theoretical treatment, Journal of the ACM (JACM), v.14 n.2, p.242-261, April 1967 [doi>10.1145/321386.321388]
• 10: Schrage, L.E., "Some Queueing Models for a Time-Shared Facility," Ph.D. Thesis, Cornell University, February 1966.
• 11: G. K. Manacher, Production and Stabilization of Real-Time Task Schedules, Journal of the ACM (JACM), v.14 n.3, p.439-465, July 1967 [doi>10.1145/321406.321408]
• 12: David Frederic Martin, Volume i. the automatic assignment and sequencing of computations on parallel processor systems. volume ii. program listings, 1966
• 13: Daniel J. Lasser, Productivity of multiprogrammed computers—progress in developing an analytic prediction method, Communications of the ACM, v.12 n.12, p.678-684, Dec. 1969 [doi>10.1145/363626.363640]
• 14: L. A. Belady , C. J. Kuehner, Dynamic space-sharing in computer systems, Communications of the ACM, v.12 n.5, p.282-288, May 1969 [doi>10.1145/362946.363002]
• 15: Sakata, M., Noguchi, S., and Oizumi, J., "Analysis of a Processor-Shared Queueing Model for Time-Sharing Systems," Proceedings, 2nd Hawaii International Conference on System Sciences, January 1969.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Multiprocessing/multiprogramming/multitasking

  G. Mathematics of Computing
  G.m MISCELLANEOUS

General Terms:
Design, Management