mdh.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Exact Speedup Factors and Sub-Optimality for Non-Preemptive Scheduling
University of York, York, UK.
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.ORCID iD: 0000-0002-6355-3564
University of York, York, UK.
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.ORCID iD: 0000-0003-4157-3537
Show others and affiliations
(English)In: Real-time systems, ISSN 0922-6443, E-ISSN 1573-1383Article in journal (Refereed) Epub ahead of print
Abstract [en]

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 xed priority non-preemptive scheduling. Speci cally, 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). As this lower bound matches a recently published upper bound for the same quantity, it closes the exact sub-optimality for EDF-NP. It is known that neither preemptive, nor non-preemptive xed priority scheduling dominates the other, in other words, 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 the exact speed-up factor required to guarantee FP-P feasibility of any constrained-deadline FP-NP feasible task set.

Keyword [en]
real-time uniprocessor resource augmentation speedupfactor sub-optimality non-preemptive scheduling preemptive scheduling EDF xed priority
National Category
Computer Systems
Identifiers
URN: urn:nbn:se:mdh:diva-37337DOI: 10.1007/s11241-017-9294-3OAI: oai:DiVA.org:mdh-37337DiVA: diva2:1160968
Available from: 2017-11-28 Created: 2017-11-28 Last updated: 2017-11-28Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Thekilakkattil, AbhilashDobrin, RaduPunnekkat, Sasikumar

Search in DiVA

By author/editor
Thekilakkattil, AbhilashDobrin, RaduPunnekkat, Sasikumar
By organisation
Embedded Systems
In the same journal
Real-time systems
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf