Real-time scheduling of DAG tasks with arbitrary deadlines

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

6 Scopus Citations
View graph of relations

Author(s)

  • Kankan WANG
  • Xu JIANG
  • Di LIU
  • Weichen LIU
  • Qingxu DENG

Detail(s)

Original languageEnglish
Article number66
Journal / PublicationACM Transactions on Design Automation of Electronic Systems
Volume24
Issue number6
Online published14 Oct 2019
Publication statusPublished - Nov 2019
Externally publishedYes

Abstract

Real-time and embedded systems are shifting from single-core to multi-core processors, on which the software must be parallelized to fully utilize the computation capacity of the hardware. Recently, much work has been done on real-time scheduling of parallel tasks modeled as directed acyclic graphs (DAG). However, most of these studies assume tasks to have implicit or constrained deadlines. Much less work considered the general case of arbitrary deadlines (i.e., the relative deadline is allowed to be larger than the period), which is more difficult to analyze due to intra-task interference among jobs. In this article, we study the analysis of Global Earliest Deadline First (GEDF) scheduling for DAG parallel tasks with arbitrary deadlines. We develop new analysis techniques for GEDF scheduling of a single DAG task and this new analysis techniques can guarantee a better capacity augmentation bound 2.41 (the best known result is 2.5) in the case of a single task. Furthermore, the proposed analysis techniques are also extended to the case of multiple DAG tasks under GEDF and federated scheduling. Finally, through empirical evaluation, we justify the out-performance of our schedulability tests compared to the state-of-the-art in general.

Research Area(s)

  • Arbitrary deadline, GEDF scheduling, Parallel task

Citation Format(s)

Real-time scheduling of DAG tasks with arbitrary deadlines. / WANG, Kankan; JIANG, Xu; GUAN, Nan; LIU, Di; LIU, Weichen; DENG, Qingxu.

In: ACM Transactions on Design Automation of Electronic Systems, Vol. 24, No. 6, 66, 11.2019.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review