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
Quantifying the Exact Sub-Optimality of Non-Preemptive Scheduling
University of York, UK.
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.ORCID iD: 0000-0002-6355-3564
University of York, UK.
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.ORCID iD: 0000-0003-4157-3537
Show others and affiliations
2016 (English)In: Proceedings - Real-Time Systems Symposium, 2016, Vol. jan, 96-106 p.Conference paper, Published paper (Refereed)
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 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.

Place, publisher, year, edition, pages
2016. Vol. jan, 96-106 p.
National Category
Computer Systems
Identifiers
URN: urn:nbn:se:mdh:diva-29627DOI: 10.1109/RTSS.2015.17ISI: 000380424600010Scopus ID: 2-s2.0-84964677912ISBN: 978-146739507-6 (print)OAI: oai:DiVA.org:mdh-29627DiVA: diva2:881504
Conference
36th IEEE Real-Time Systems Symposium, RTSS 2015; San Antonio; United States; 1 December 2015 through 4 December 2015; Category numberE5651; Code 119070
Projects
CONTESSE - Contract-Based Components for Embedded Software
Available from: 2015-12-10 Created: 2015-11-26 Last updated: 2016-08-18Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Thekkilakattil, AbhilashDobrin, RaduPunnekkat, Sasikumar
By organisation
Embedded Systems
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 8 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