D-OVER ; an optimal on-line scheduling algorithm for overloaded real-time systems - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport Année : 1992

D-OVER ; an optimal on-line scheduling algorithm for overloaded real-time systems

G. Koren
  • Fonction : Auteur
Dennis Shasha
  • Fonction : Auteur
  • PersonId : 833427

Résumé

Every task in a real-time system has a deadline by which time it should complete. Each task also 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 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 firtst performs very badly when the system is overloaded and proposed heuristics to deal with overload. This paper presents an optimal on-line scheduling algorithm for overloaded systems. It is optimal in the sense that it gives the best competitive factor possible relative to an offline scheduler.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RT-0138.pdf (2.15 Mo) Télécharger le fichier

Dates et versions

inria-00070030 , version 1 (19-05-2006)

Identifiants

  • HAL Id : inria-00070030 , version 1

Citer

G. Koren, Dennis Shasha. D-OVER ; an optimal on-line scheduling algorithm for overloaded real-time systems. RT-0138, INRIA. 1992, pp.45. ⟨inria-00070030⟩
131 Consultations
194 Téléchargements

Partager

Gmail Facebook X LinkedIn More