uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • 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
Fixed-Priority Schedulability of Sporadic Tasks on Uniprocessors is NP-hard
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. (Embedded Systems)
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. (Embedded Systems)
2017 (English)In: 2017 IEEE Real-Time Systems Symposium (RTSS), IEEE, 2017, p. 139-146Conference paper, Published paper (Refereed)
Abstract [en]

We study the computational complexity of the FP-schedulability problem for sporadic or synchronous periodic tasks on a preemptive uniprocessor. We show that this problem is (weakly) NP-hard, even when restricted to either (i) task sets with implicit deadlines and rate-monotonic priority ordering, or (ii) task sets with constrained deadlines, deadline-monotonic priority ordering and utilization bounded by any constant c, such that 0 < c < 1.

Place, publisher, year, edition, pages
IEEE, 2017. p. 139-146
Series
Real-Time Systems Symposium-Proceedings, E-ISSN 1052-8725
Keywords [en]
Scheduling, real-time, complexity, fixed-priority
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:uu:diva-337581DOI: 10.1109/RTSS.2017.00020ISI: 000426466700013ISBN: 978-1-5386-1415-0 (electronic)OAI: oai:DiVA.org:uu-337581DiVA, id: diva2:1170243
Conference
38th IEEE Real-Time Systems Symposium (RTSS), Paris, France, December 5–8, 2017
Available from: 2018-02-01 Created: 2018-01-02 Last updated: 2018-05-29Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Ekberg, PontusWang, Yi

Search in DiVA

By author/editor
Ekberg, PontusWang, Yi
By organisation
Computer Systems
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 96 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • 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