The digraph real-time task model

Martin Stigge, Pontus Ekberg, Nan Guan, Wang Yi

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

95 Citations (Scopus)

Abstract

Models for real-time systems have to balance the inherently contradicting goals of expressiveness and analysis efficiency. Current task models with tractable feasibility tests have limited expressiveness, restricting their ability to model many systems accurately. In particular, they are all recurrent, preventing the modeling of structures like mode switches, local loops, etc. In this paper, we advance the state-of-the-art with a model that is free from these constraints. Our proposed task model is based on arbitrary directed graphs (digraphs) for job releases. We show that the feasibility problem on preemptive uniprocessors for our model remains tractable. This even holds in the case of task systems with arbitrary deadlines.
Original languageEnglish
Title of host publicationProceedings - 17th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2011
Pages71-80
Number of pages10
DOIs
Publication statusPublished - 1 Jun 2011
Externally publishedYes
Event17th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2011 - Chicago, IL, United States
Duration: 11 Apr 201114 Apr 2011

Conference

Conference17th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2011
CountryUnited States
CityChicago, IL
Period11/04/1114/04/11

Keywords

  • feasibility
  • real-time systems
  • task models
  • tractability

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Hardware and Architecture
  • Software

Cite this