Quantifying the Sub-optimality of Uniprocessor Fixed Priority Pre-emptive Scheduling for Sporadic Tasksets with Arbitrary Deadlines

Abstract : This paper examines the relative effectiveness of fixed priority pre-emptive scheduling in a uniprocessor system, compared to an optimal algorithm such as Earliest Deadline First (EDF). The quantitative metric used in this comparison is the processor speedup factor, defined as the factor by which processor speed needs to increase to ensure that any taskset that is schedulable according to an optimal scheduling algorithm can be scheduled using fixed priority pre-emptive scheduling. For implicit-deadline tasksets, the speedup factor is 1/ln(2) ≈ 1.44270. For constrained-deadline tasksets, the speedup factor is 1/Ω ≈ 1.76322. In this paper, we show that for arbitrary-deadline tasksets, the speedup factor is lower bounded by 1/Ω ≈ 1.76322 and upper bounded by 2. Further, when deadline monotonic priority assignment is used, we show that the speedup factor is exactly 2.
Type de document :
Communication dans un congrès
Laurent George and Maryline Chetto andMikael Sjodin. 17th International Conference on Real-Time and Network Systems, Oct 2009, Paris, France. pp.23-34, 2009
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00441952
Contributeur : Alain Monteil <>
Soumis le : jeudi 17 décembre 2009 - 16:46:10
Dernière modification le : samedi 11 novembre 2017 - 19:04:02
Document(s) archivé(s) le : jeudi 17 juin 2010 - 21:59:24

Fichier

UniprocessorScheduling_Davis.p...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00441952, version 1

Collections

Citation

Robert Davis, Sanjoy Baruah, Thomas Rothvoss, Alan Burns. Quantifying the Sub-optimality of Uniprocessor Fixed Priority Pre-emptive Scheduling for Sporadic Tasksets with Arbitrary Deadlines. Laurent George and Maryline Chetto andMikael Sjodin. 17th International Conference on Real-Time and Network Systems, Oct 2009, Paris, France. pp.23-34, 2009. 〈inria-00441952〉

Partager

Métriques

Consultations de la notice

606

Téléchargements de fichiers

623