Dover: an optimal on-line scheduling algorithm for overloaded uniprocessor real-time systems

Gilad Koren, Dennis Shasha

Research output: Contribution to journalArticlepeer-review

Abstract

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-813] 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.

Original languageEnglish (US)
Pages (from-to)318-339
Number of pages22
JournalSIAM Journal on Computing
Volume24
Issue number2
DOIs
StatePublished - 1995

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'D<sup>over</sup>: an optimal on-line scheduling algorithm for overloaded uniprocessor real-time systems'. Together they form a unique fingerprint.

Cite this