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. 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 language | English (US) |
---|---|
Pages | 178-186 |
Number of pages | 9 |
DOIs | |
State | Published - Nov 19 1975 |
Event | 5th ACM Symposium on Operating Systems Principles, SOSP 1975 - Austin, United States Duration: Nov 19 1975 → Nov 21 1975 |
Other
Other | 5th ACM Symposium on Operating Systems Principles, SOSP 1975 |
---|---|
Country/Territory | United States |
City | Austin |
Period | 11/19/75 → 11/21/75 |
Keywords
- Critical path algorithm
- Minimal length schedules
- Processor sharing
- Worst case analysis
ASJC Scopus subject areas
- Computational Theory and Mathematics
- Computer Science Applications
- Software