Approximate response time analysis of real-time task graphs

Nan Guan, Chuancai Gu, Martin Stigge, Qingxu Deng, Wang Yi

Research output: Journal article publicationConference articleAcademic researchpeer-review

Abstract

The response time analysis problem is intractable for most existing real-time task models, except the simplest ones. Exact solutions for this problem in general have exponential complexity, and may run into scalability problems for large-scale task systems. In this paper, we study approximate analysis for static-priority scheduling of the Digraph Real-Time task model, which is a generalization of most existing graph-based real-time task models. We present two approximate analysis methods RBF and IBF, both of which have pseudo-polynomial complexity. We quantitatively evaluate their analysis precision using the metric speedup factor. We prove that RBF has a speedup factor of 2, and this is tight even for dual-task systems. The speedup factor of IBF is an increasing function with respect to k, the number of interfering tasks. This function converges to 2 as k approaches infinity and equals 1 when k = 1, implying that the IBF analysis is exact for dual-task systems. We also conduct simulation experiments to evaluate the precision and efficiency of RBF and IBF with randomly generated task sets. Results show that the proposed approximate analysis methods have very high efficiency with low precision loss.
Original languageEnglish
Article number7010497
Pages (from-to)304-313
Number of pages10
JournalProceedings - Real-Time Systems Symposium
Volume2015-January
Issue numberJanuary
DOIs
Publication statusPublished - 1 Jan 2015
Externally publishedYes
Event35th IEEE Real-Time Systems Symposium, RTSS 2014 - Rome, Italy
Duration: 2 Dec 20145 Dec 2014

Keywords

  • DRT
  • real-time systems
  • response time analysis
  • speedup factor
  • task graphs

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this