D^over: An Optimal On-Line Scheduling Algorithm for Overloaded Uniprocessor Real-Time Systems

Consider a real-time system in which every task has a value that it obtains only if it completes by its deadline. The problem is to design an on-line scheduling algorithm (i.e., the scheduler has no knowledge of a task until it is released) that maximizes the guaranteed value obtained by the system. When such a system is underloaded (i.e., there exists a schedule for which all tasks meet their deadlines), Dertouzos Proceedings IFIF Congress, 1974, pp. 807–8131 showed that the earliest deadline first algorithm will achieve 100% of the possible value. Locke [Ph.D. thesis, Computer Science Dept., Carnegie-Mellon Univ., Pittsburgh, PA showed that earliest deadline first performs very badly, however, when the system is overloaded, and he proposed heuristics to deal with overload. This paper presents an optimal on-line scheduling algorithm for overloaded uniprocessor systems. It is optimal in the sense that it gives the best competitive ratio possible relative to an off-line scheduler.