Refinement-Based Exact Response-Time Analysis
Authors:
- Martin StiggeMSMartin Stigge
- Nan GuanNGNan Guan
- Wang YiWYWang Yi
- 1 July 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 143-152
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.Keywords
This publication has 16 references indexed in Scilit:
- General and efficient Response Time Analysis for EDF scheduling2014
- Compositional performance analysis with improved analysis techniques for obtaining viable end-to-end latencies in distributed embedded systemsInternational Journal on Software Tools for Technology Transfer, 2012
- Hardness Results for Static Priority Real-Time Scheduling2012
- Generalizing Response-Time Analysis2010
- Exact scheduling analysis of non-accumulatively monotonic multiframe tasksReal-Time Systems, 2009
- Improved response time analysis of tasks scheduled under preemptive Round-Robin2007
- Characterization and Analysis of Tasks with Offsets: Monotonic Transactions2006
- Real-time calculus for scheduling hard real-time systems2002
- Holistic schedulability analysis for distributed hard real-time systemsMicroprocessing and Microprogramming, 1994
- Finding Response Times in a Real-Time SystemThe Computer Journal, 1986