Optimality and non-preemptive real-time scheduling revisited

Abstract : In this paper, we investigate the non-preemptive scheduling problem as it arises with single processor systems. We extend some previously published results concerning preemptive and non-preemptive scheduling over a single processor. We examine non-idling and idling scheduling issues. The latter are of particular relevance in the case of non-preemption. We first embark on analyzing non-idling scheduling. The optimality of the non-idling non-preemptive Earliest Deadline First scheduling policy is revisited. Then, we provide feasibility conditions in the presence of aperiodic or periodic traffic. Second, we examine the concept of idling scheduling, whereby a processor can remain idle in the presence of pending tasks. The non-idling non-preemptiv- e Earliest Deadline First scheduling policy is not optimal since it is possible to find feasible task sets for which this policy fails to produce a valid schedule. An optimal algorithm to find a valid schedule (if any) is presented and its complexity analyzed. This paper shows that preemptive and non-preemptive scheduling are closely related. However, non-preemptive scheduling leads to more complex problems when combined with idling scheduling.
Type de document :
[Research Report] RR-2516, INRIA. 1995
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 14:38:58
Dernière modification le : vendredi 25 mai 2018 - 12:02:05
Document(s) archivé(s) le : dimanche 4 avril 2010 - 22:13:00



  • HAL Id : inria-00074162, version 1



Laurent George, Paul Muhlethaler, Nicolas Rivierre. Optimality and non-preemptive real-time scheduling revisited. [Research Report] RR-2516, INRIA. 1995. 〈inria-00074162〉



Consultations de la notice


Téléchargements de fichiers