Hardness Results for Static Priority Real-Time Scheduling
2012 (English)In: Proceedings Of The 24th Euromicro Conference On Real-Time Systems (Ecrts 2012), 2012, 189-198 p.Conference paper (Refereed)
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.
, Euromicro Workshop on Real-Time Systems-Proceedings, ISSN 1068-3070
Natural Sciences Engineering and Technology
IdentifiersURN: urn:nbn:se:uu:diva-207203DOI: 10.1109/ECRTS.2012.13ISI: 000322959300018ISBN: 978-0-7695-4739-8OAI: oai:DiVA.org:uu-207203DiVA: diva2:647092
24th Euromicro Conference on Real-Time Systems (ECRTS), JUL 10-13, 2012, Pisa, ITALY