Abstract
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.
Original language | English |
---|---|
Title of host publication | Proceedings - Euromicro Conference on Real-Time Systems |
Publisher | IEEE |
Pages | 143-152 |
Number of pages | 10 |
ISBN (Electronic) | 9781479957989 |
DOIs | |
Publication status | Published - 1 Jan 2014 |
Externally published | Yes |
Event | 26th Euromicro Conference on Real-Time Systems, ECRTS 2014 - Madrid, Spain Duration: 8 Jul 2014 → 11 Jul 2014 |
Conference
Conference | 26th Euromicro Conference on Real-Time Systems, ECRTS 2014 |
---|---|
Country/Territory | Spain |
City | Madrid |
Period | 8/07/14 → 11/07/14 |
Keywords
- EDF
- fixed-priority
- response-time analysis
- Schedulability Analysis
ASJC Scopus subject areas
- Software
- Hardware and Architecture