https://www.mdu.se/

mdu.sePublications
Planned maintenance
A system upgrade is planned for 10/12-2024, at 12:00-13:00. During this time DiVA will be unavailable.
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
2018 (English)In: Real-time systems, ISSN 0922-6443, E-ISSN 1573-1383, p. 208-246Article in journal (Refereed) Published
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.

Place, publisher, year, edition, pages
2018. p. 208-246
Keywords [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-3ISI: 000419955500007Scopus ID: 2-s2.0-85032335776OAI: oai:DiVA.org:mdh-37337DiVA, id: diva2:1160968
Available from: 2017-11-28 Created: 2017-11-28 Last updated: 2018-01-26Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

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
Total: 87 hits
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