Quantifying the Exact Sub-Optimality of Non-Preemptive Scheduling

Robert Davis 1, 2 Abhilash Thekkilakattil 3 Oliver Gettings 2 Radu Dobrin 3 Sasikumar Punnekkat 3
1 AOSTE - Models and methods of analysis and optimization for systems with real-time and embedding constraints
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Paris-Rocquencourt, COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : Fixed priority scheduling is used in many real-time systems; however, both preemptive and non-preemptive variants (FP-P and FP-NP) are known to be sub-optimal when compared to an optimal uniprocessor scheduling algorithm such as preemptive Earliest Deadline First (EDF-P). In this paper, we investigate the sub-optimality of fixed priority non-preemptive scheduling. Specifically, we derive the exact processor speed-up factor required to guarantee the feasibility under FP-NP (i.e. schedulablability assuming an optimal priority assignment) of any task set that is feasible under EDF-P. As a consequence of this work, we also derive a lower bound on the sub-optimality of non-preemptive EDF (EDF-NP), which since it matches a recently published upper bound gives the exact sub-optimality for EDF-NP. It is known that neither preemptive, nor non-preemptive fixed priority scheduling dominates the other, i.e., there are task sets that are feasible on a processor of unit speed under FP-P that are not feasible under FP-NP and vice-versa. Hence comparing these two algorithms, there are non-trivial speedup factors in both directions. We derive the exact speed-up factor required to guarantee the FP-NP feasibility of any FP-P feasible task set. Further, we derive upper and lower bounds on the speed-up factor required to guarantee FP-P feasibility of any FP-NP feasible task set. Empirical evidence suggests that the lower bound may be tight, and hence equate to the exact speed-up factor in this case.
Type de document :
Communication dans un congrès
36th Real-Time Systems Symposium (RTSS 2015), Dec 2015, San Antonio, Texas, United States
Liste complète des métadonnées

https://hal.inria.fr/hal-01231718
Contributeur : Robert Davis <>
Soumis le : vendredi 20 novembre 2015 - 15:34:56
Dernière modification le : samedi 21 novembre 2015 - 01:06:09

Identifiants

  • HAL Id : hal-01231718, version 1

Collections

Citation

Robert Davis, Abhilash Thekkilakattil, Oliver Gettings, Radu Dobrin, Sasikumar Punnekkat. Quantifying the Exact Sub-Optimality of Non-Preemptive Scheduling. 36th Real-Time Systems Symposium (RTSS 2015), Dec 2015, San Antonio, Texas, United States. <hal-01231718>

Partager

Métriques

Consultations de la notice

79