On the Decomposition-Based Global EDF Scheduling of Parallel Real-Time Tasks

Xu Jiang, Xiang Long, Nan Guan, Han Wan

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


Real-time systems are shifting from single-core to multi-core processors, on which software must be parallelized to fully utilize the additional computation power. Recently different types of scheduling algorithms and analysis techniques have been proposed for parallel real-time tasks modeled as directed acyclic graphs (DAG). However, this field is still much less mature than traditional real-time scheduling of sequential tasks. In this paper, we study the decomposition-based scheduling for parallel real-time tasks, where a task graph is transferred to a set of independent sporadic tasks. In particular, we proposed a new decomposition strategy that better explores the feature of each task, represented by its structure characteristic value, to improve schedulability. The structure characteristic values do not only provide a clear guidance in task decomposition, but also can be directly used for schedulability tests, as well as to quantify the suboptimality of our scheduling algorithm in terms of capacity augmentation bounds. We conduct comprehensive experiments to evaluate the real-time performance of our proposed scheduling algorithm, against the state-of-the-art scheduling and analysis methods of different types. Experiment results show that our method consistently outperforms all of the previous methods under different parameter settings.
Original languageEnglish
Title of host publicationProceedings - 2016 IEEE Real-Time Systems Symposium, RTSS 2016
Number of pages10
ISBN (Electronic)9781509053025
Publication statusPublished - 6 Jan 2017
Event2016 IEEE Real-Time Systems Symposium, RTSS 2016 - Porto, Portugal
Duration: 29 Nov 20162 Dec 2016


Conference2016 IEEE Real-Time Systems Symposium, RTSS 2016


  • global scheduling
  • multi-core processor
  • parallel tasks
  • real-time scheduling

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this