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

Gilad Koren, Dennis Shasha

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Every task in a real-time system has a deadline by which time it should complete and a vaJue 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 obtained value. When such a system is underloaded (i.e. there exists a schedule for which all tasks meet their deadlines), Dertouzos showed that the earliest deadline first algorithm will achieve 100% of the possible value. Locke showed that earliest deadline first performs very badly when the system is overloaded and proposed heuristics to deal with overload. Baruah et al. showed that the best that an on-line algorithm can guarantee is 1/(1+k)2 of the value that an off-line (clairvoyant) algorithm can obtain where k is the ratio between the highest value density and the lowest value density task in the system (where the value density of a task is its value divided by its computation time). We present an on-line algorithm that achieves the above best possible guarantee in this model. This algorithm also obtains 100% of the possible value when the system is underloaded.

Original languageEnglish (US)
Title of host publicationProceedings - Real-Time Systems Symposium, RTSS 1992
Number of pages10
StatePublished - 1992
Event1992 Real-Time Systems Symposium, RTSS 1992 - Phoenix, AZ, United States
Duration: Dec 2 1992Dec 4 1992

Publication series

NameProceedings - Real-Time Systems Symposium
ISSN (Print)1052-8725


Other1992 Real-Time Systems Symposium, RTSS 1992
Country/TerritoryUnited States
CityPhoenix, AZ

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Dover: An optimal on-line scheduling algorithm for overloaded real-time systems'. Together they form a unique fingerprint.

Cite this