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. 1 CFFMAN, E G JR, Ed Computer and Jobshop Scheduhng Theory Wdey, New York, 1976
2. 2 COFFMAN, E G JR , AND GRAHAM, R.L Optimal scheduling for two processor systems Acta lnformanca 1, 3 (1972), 200-213
3. 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. 4 LAM, S, AND SETm, R Worst case analysis of two scheduhng algorithms (To appear in SlAM J Comptg, 1976 )
5. 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. 6 LIU, J W S , AND YANO, A Optimal scheduling of independent tasks on heterogeneous computing systems Proc ACM 1974 Annual Conf., pp 38-45
7. 7 McNAUGHTON, R Scheduhng with deadhnes and loss functions Manage Sct 12, 1 (Oct 1959), 1-12
8. 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. 9 MUNTZ, R R, AND COFFMAN, E G JR. Preemptwe scheduhng of real ume tasks on mult~processor systems J ACM 17, 2 (Aprd 1970), 324-338
10. 10 ROTRKOPF, M H Scheduhng independent tasks on parallel processors Manage Sct 12, 5 (Jan 1966), 437-447

Index Terms

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Process management

          • Scheduling

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

      • Scheduling algorithms

    • Online algorithms

      • Online learning algorithms

        • Scheduling algorithms

  • Theory and algorithms for application domains

    • Machine learning theory

      • Reinforcement learning

        • Sequential decision making