On-line scheduling in the presence of overload
- 9 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 100-110
- https://doi.org/10.1109/sfcs.1991.185354
Abstract
The preemptive scheduling of sporadic tasks on a uniprocessor is considered. A task may arrive at any time, and is characterized by a value that reflects its importance, an execution time that is the amount of processor time needed to completely execute the task, and a deadline by which the task is to complete execution. The goal is to maximize the sum of the values of the completed tasks. An online scheduling algorithm that achieves optimal performance when the system is underloaded and provides a nontrivial performance guarantee when the system is overloaded is designed. The algorithm is implemented using simple data structures to run at a cost of O(log n) time per task, where n bounds the number of tasks in the system at any instant. Upper bounds on the best performance guarantee obtainable by an online algorithm in a variety of settings are derived.<>Keywords
This publication has 4 references indexed in Scilit:
- 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