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
Hardness Results for Static Priority Real-Time Scheduling
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
2012 (English)In: Proceedings Of The 24th Euromicro Conference On Real-Time Systems (Ecrts 2012), 2012, 189-198 p.Conference paper, Published paper (Refereed)
Abstract [en]

Real-time systems are often modeled as a collection of tasks, describing the structure of the processor's workload. In the literature, task-models of different expressiveness have been developed, ranging from the traditional periodic task model to highly expressive graph-based models. For dynamic priority schedulers, it has been shown that the schedulability problem can be solved efficiently, even for graph-based models. However, the situation is less clear for the case of static priority schedulers. It has been believed that the problem can be solved in pseudo-polynomial time for the generalized multiframe model (GMF). The GMF model constitutes a compromise in expressiveness by allowing cycling through a static list of behaviors, but disallowing branching. Further, the problem complexity for more expressive models has been unknown so far. In this paper, we show that previous results claiming that a precise and efficient test exists are wrong, giving a counterexample. We prove that the schedulability problem for GMF models (and thus also all more expressive models) using static priority schedulers is in fact coNP-hard in the strong sense. Our result thus establishes the fundamental hardness of analyzing static priority real-time scheduling, in contrast to its dynamic priority counterpart of pseudo-polynomial complexity.

Place, publisher, year, edition, pages
2012. 189-198 p.
Series
Euromicro Workshop on Real-Time Systems-Proceedings, ISSN 1068-3070
National Category
Natural Sciences Engineering and Technology
Identifiers
URN: urn:nbn:se:uu:diva-207203DOI: 10.1109/ECRTS.2012.13ISI: 000322959300018ISBN: 978-0-7695-4739-8 (print)OAI: oai:DiVA.org:uu-207203DiVA: diva2:647092
Conference
24th Euromicro Conference on Real-Time Systems (ECRTS), JUL 10-13, 2012, Pisa, ITALY
Available from: 2013-09-10 Created: 2013-09-10 Last updated: 2013-09-10Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full texthttp://ecrts.eit.uni-kl.de/ecrts12

Authority records BETA

Stigge, MartinYi, Wang

Search in DiVA

By author/editor
Stigge, MartinYi, Wang
By organisation
Computer Systems
Natural SciencesEngineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 401 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