Refinement-Based exact Response-Time analysis

Martin Stigge, Nan Guan, Wang Yi

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

13 Citations (Scopus)

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 languageEnglish
Title of host publicationProceedings - Euromicro Conference on Real-Time Systems
PublisherIEEE
Pages143-152
Number of pages10
ISBN (Electronic)9781479957989
DOIs
Publication statusPublished - 1 Jan 2014
Externally publishedYes
Event26th Euromicro Conference on Real-Time Systems, ECRTS 2014 - Madrid, Spain
Duration: 8 Jul 201411 Jul 2014

Conference

Conference26th Euromicro Conference on Real-Time Systems, ECRTS 2014
CountrySpain
CityMadrid
Period8/07/1411/07/14

Keywords

  • EDF
  • fixed-priority
  • response-time analysis
  • Schedulability Analysis

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture

Cite this