Overload tolerance for single-processor workloads
- 27 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
In firm real time environments in which tasks must complete by their deadlines if they are to be of any value to the system, it is known that no uniprocessor online scheduling algorithm can guarantee to perform particularly well under conditions of overload as compared to clairvoyant algorithms. The article explores the issue of designing online scheduling algorithms that use multiple processors to compensate for their lack of clairvoyance. In particular, it is shown that given enough processors, online scheduling algorithms can be designed with performance guarantees arbitrarily close to that of optimal clairvoyant uniprocessor scheduling algorithms.Keywords
This publication has 9 references indexed in Scilit:
- MOCA: A multiprocessor on-line competitive algorithm for real-time system schedulingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Earliest deadline scheduling for real-time database systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On-line scheduling in the presence of overloadPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Scheduling for overload in real-time systemsIEEE Transactions on Computers, 1997
- On-line scheduling to maximize task completionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1994
- ROBUSTPublished by Association for Computing Machinery (ACM) ,1993
- On the competitiveness of on-line real-time task schedulingReal-Time Systems, 1992
- On being optimistic about real-time constraintsPublished by Association for Computing Machinery (ACM) ,1990
- Multiprocessor online scheduling of hard-real-time tasksIEEE Transactions on Software Engineering, 1989