Skip to Main content Skip to Navigation
Conference papers

Quantifying the Sub-optimality of Uniprocessor Fixed Priority Non-Pre-emptive Scheduling

Robert Davis 1 Laurent George 2 Pierre Courbin 3
2 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, Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : This paper examines the relative effectiveness of fixed priority non-pre-emptive scheduling (FP-NP) in a uniprocessor system, compared to an optimal work-conserving non-pre-emptive algorithm; Earliest Deadline First (EDF-NP). 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 EDF-NP can be scheduled using FP-NP scheduling. For sporadic tasksets with implicit, constrained, or arbitrary deadlines, the speedup factor is shown to be lower bounded by 1/Omega (1.76322) and upper bounded by 2. We also report the results of empirical investigations into the speedup factor required to ensure schedulability in the non-pre-emptive case.
Document type :
Conference papers
Complete list of metadatas

Cited literature [8 references]  Display  Hide  Download

https://hal.inria.fr/inria-00536363
Contributor : Christine Rochange <>
Submitted on : Tuesday, November 16, 2010 - 3:46:20 PM
Last modification on : Tuesday, May 26, 2020 - 6:50:21 PM
Document(s) archivé(s) le : Thursday, February 17, 2011 - 2:45:42 AM

File

rtns2010_davis.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00536363, version 1

Collections

Citation

Robert Davis, Laurent George, Pierre Courbin. Quantifying the Sub-optimality of Uniprocessor Fixed Priority Non-Pre-emptive Scheduling. 18th International Conference on Real-Time and Network Systems, Nov 2010, Toulouse, France. pp.1-10. ⟨inria-00536363⟩

Share

Metrics

Record views

926

Files downloads

311