Transforming Real-Time Task Graphs to Improve Schedulability

Chuancai Gu, Nan Guan, Zhiwei Feng, Qingxu Deng, Xiaobo Sharon Hu, Wang Yi

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

1 Citation (Scopus)

Abstract

Real-time task graphs are used to describe complex real-time systems with non-cyclic timing behaviors. The workload of such systems are typically bursty, which may degrade their schedulability even with sufficient resource in the long term. In this paper, we propose to use task graph transformation to improve system schedulability. The idea is to insert artificial delays to the release times of certain vertices of a task graph to get a new graph with a smoother workload, while still meeting the timing constraints of the original task graph. Delaying the release time of a vertex may smoothen the workload of some paths of the task graph, but at the same time make the workload of other paths even more bursty. We developed efficient techniques to search for an appropriate release time delay for each vertex. Experiments with randomly generated task systems show that the proposed transformation method can make a significant number of task systems that was originally unschedulable to become schedulable, and the transformation procedure is very efficient and can easily handle large-scale task graph systems in very short computation time.
Original languageEnglish
Title of host publicationProceedings - 2016 IEEE 22nd International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2016
PublisherIEEE
Pages29-38
Number of pages10
ISBN (Electronic)9781509024797
DOIs
Publication statusPublished - 29 Sep 2016
Event22nd IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2016 - Daegu, Korea, Republic of
Duration: 17 Aug 201619 Aug 2016

Conference

Conference22nd IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2016
Country/TerritoryKorea, Republic of
CityDaegu
Period17/08/1619/08/16

Keywords

  • DRT
  • real-time systems
  • workload shaping

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Computer Science Applications
  • Hardware and Architecture
  • Information Systems and Management

Cite this