SIAM Journal on Computing · 1995 · 189 citations · 6 references
ComputingComputer EngineeringComputer ScienceAlgorithmsReal-time SystemsSchedulingEarliest Deadline First SchedulingPreemptive SchedulingReal-time SchedulingReal-time Systems DesignSchedulability AnalysisScheduling TheoryCompetitive RatioEarliest Deadline First SchedulabilityOverload HandlingOverload SchedulingReal-time System ModelsScheduler DesignScheduling With DeadlinesUniprocessor Earliest Deadline First Scheduling
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.
6
Anna R. Karlin, Mark S. Manasse, Larry Rudolph et al. · Algorithmica · 1988 · 612 citations
The Spring kernel: a new paradigm for real-time systems
John A. Stankovic, Krithi Ramamritham · IEEE Software · 1991 · 262 citations
On the competitiveness of on-line real-time task scheduling
Sanjoy Baruah, G. Koren, Dacheng Mao et al. · Real-Time Systems · 1992 · 172 citations
The cyclic executive model and Ada
T. P. Baker, Alan Shaw · Real-Time Systems · 1989 · 164 citations