A Level Algorithm for Preemptive Scheduling

ABSTRACT

Muntz and Coffman give a level algorithm that constructs optimal preemptive schedules on identical processors when the task system is a tree or when there are only two processors available. Their algorithm is adapted here to handle processors of different speeds. The new algorithm is optimal for independent tasks on any number of processors and for arbitrary task systems on two processors, but not on three or more processors, even for trees. By taking the algorithm as a heuristic on m processors and using the ratio of the lengths of the constructed and optimal schedules as a measure, an upper bound on its performance is derived in terms of the speeds of the processors. It is further shown that 1.23√m is an upper bound over all possible processor speeds and that the 1.23√m bound can be improved at most by a constant factor, by giving an example of a system for which the bound 0.35√m can be approached asymptotically.

REFERENCES

• 1: CFFMAN, E G JR, Ed Computer and Jobshop Scheduhng Theory Wdey, New York, 1976
• 2: COFFMAN, E G JR , AND GRAHAM, R.L Optimal scheduling for two processor systems Acta lnformanca 1, 3 (1972), 200-213
• 3: GONZALEZ, T, IBA~A, O, ANt) SAHNI, S. Bounds for LPT schedules on umform processors Comptr Scl Tech Rep No 75-1, U of Minnesota, Minneapolis, Mmn, 1974
• 4: LAM, S, AND SETm, R Worst case analysis of two scheduhng algorithms (To appear in SlAM J Comptg, 1976 )
• 5: LitJ, J.W S, xNo LIu, C.L Performance analysis of heterogeneous multlprocessor computing systems In Computer Architectures and Networks, E Gelenbe and R. Mahl, Eds, North-Holland Pub Co, Amsterdam, 1974, pp 27-45
• 6: Jane W. S. Liu , Ai-Tsung Yang, Optimal scheduling of independent tasks on heterogeneous computing systems, Proceedings of the 1974 annual conference, p.38-45, January 1974 [doi>10.1145/800182.810377]
• 7: McNAUGHTON, R Scheduhng with deadhnes and loss functions Manage Sct 12, 1 (Oct 1959), 1-12
• 8: MuNlz, R R , AND COFFMAN, E G JR Optimal preemptwe scheduhng on two-processor systems IEEE Trans Comptrs C-18, 11 (Nov 1969), 1014-1020
• 9: R. R. Muntz , E. G. Coffman, Jr., Preemptive Scheduling of Real-Time Tasks on Multiprocessor Systems, Journal of the ACM (JACM), v.17 n.2, p.324-338, April 1970 [doi>10.1145/321574.321586]
• 10: ROTRKOPF, M H Scheduhng independent tasks on parallel processors Manage Sct 12, 5 (Jan 1966), 437-447

INDEX TERMS

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

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:
Algorithms, Design, Measurement, Performance, Theory, Verification