D/sup over/; an optimal on-line scheduling algorithm for overloaded real-time systems
- 2 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 290-299
- https://doi.org/10.1109/real.1992.242650
Abstract
An optimal online scheduling algorithm for overloaded systems is presented. It is optimal in the sense that it gives the best competitive factor possible relative to an offline (i.e., clairvoyant) scheduler. It also gives 100% of the value of a clairvoyant scheduler when the system is underloaded. In fact the performance guarantee of D/sup over/ is even stronger: D/sup over/ schedules to completion all tasks in underloaded periods and achieves at least 1/(1+ square root k)/sup 2/ of the value a clairvoyant algorithm can get during overloaded periods. The model accounts for different value densities and generalizes to soft deadlines.<>Keywords
This publication has 7 references indexed in Scilit:
- On-line scheduling in the presence of overloadPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On the competitiveness of on-line real-time task schedulingReal-Time Systems, 1992
- The Spring kernel: a new paradigm for real-time systemsIEEE Software, 1991
- The cyclic executive model and AdaReal-Time Systems, 1989
- Competitive snoopy cachingAlgorithmica, 1988
- Amortized efficiency of list update and paging rulesCommunications of the ACM, 1985
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time EnvironmentJournal of the ACM, 1973