Refinement-based Exact Response-Time Analysis
2014 (English)In: 2014 26TH EUROMICRO CONFERENCE ON REAL-TIME SYSTEMS (ECRTS 2014), 2014, 143-152 p.Conference paper (Refereed)
A recent trend in the theory of real-time scheduling is to consider generalizations of the classical periodic task model. Work on the associated schedulability and feasibility problems has resulted in algorithms that run efficiently and provide exact results. While these analyses give black-and-white answers about whether timing constraints are being met or not, response-time analysis adds a quantitative dimension. This brings new challenges for models more expressive than the classical periodic task model. An exact quantification of response time is difficult because of non-deterministic task behavior and a lack of combinable task-local worst cases. Therefore, previous approaches all make a trade-off between efficiency and precision, resulting in either prohibitively slow analysis run-times or imprecise over-approximate results. In this paper, we show that analysis can be both exact and efficient at the same time. We develop novel response-time characterizations to which we apply combinatorial abstraction refinement. Our algorithms for static-priority and EDF scheduling give exact results and are shown to be efficient for typical problem sizes. We advance the state-of-the-art by providing the first exact response-time analysis framework for graph-based task models.
Place, publisher, year, edition, pages
2014. 143-152 p.
, Euromicro Workshop on Real-Time Systems-Proceedings, ISSN 1068-3070
IdentifiersURN: urn:nbn:se:uu:diva-247631DOI: 10.1109/ECRTS.2014.29ISI: 000349236400015ISBN: 978-1-4799-5798-9OAI: oai:DiVA.org:uu-247631DiVA: diva2:797143
26th Euromicro Conference on Real-Time Systems (ECRTS), JUL 08-11, 2014, Madrid, SPAIN