Analysis of a level algorithm for preemptive scheduling

Shui Lam, Ravi Sethi

Research output: Contribution to conferencePaperpeer-review


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. A variation of their algorithm is adapted for processors of different speeds. The algorithm is shown to be optimal on two processors for arbitrary task systems, but not on three or more processors even for trees. 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, we show that, on identical processors, its performance is bounded by 2-2/m. Moreover 2 - 2/m is a best bound in that there exist task systems for which this ratio is approached arbitrarily closely. On processors of different speeds, we derive an upper bound of its performance in terms of the speeds of the given processor system and show that √ 1.5m is an upper bound over all processor systems. We also give an example of a system for which the bound √m/2 √2 can be approached asymptotically, thus establishing that the √1.5m bound can at most be improved by a constant factor.

Original languageEnglish (US)
Number of pages9
StatePublished - Nov 19 1975
Event5th ACM Symposium on Operating Systems Principles, SOSP 1975 - Austin, United States
Duration: Nov 19 1975Nov 21 1975


Other5th ACM Symposium on Operating Systems Principles, SOSP 1975
Country/TerritoryUnited States


  • Critical path algorithm
  • Minimal length schedules
  • Processor sharing
  • Worst case analysis

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Computer Science Applications
  • Software


Dive into the research topics of 'Analysis of a level algorithm for preemptive scheduling'. Together they form a unique fingerprint.

Cite this