Utilization-Tensity Bound for Real-Time DAG Tasks under Global EDF Scheduling

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

9 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Article number8807259
Pages (from-to)39-50
Journal / PublicationIEEE Transactions on Computers
Volume69
Issue number1
Online published20 Aug 2019
Publication statusPublished - Jan 2020
Externally publishedYes

Abstract

Utilization bound is a well-known concept in real-time scheduling theory for sequential periodic tasks, which can be used both for quantifying the performance of scheduling algorithms and as efficient schedulability tests. However, the schedulability of parallel real time task graphs depends on not only utilization, but also another parameter tensity, the ratio between the longest path length and period. In this paper, we use utilization-tensity bounds to better characterize the schedulability of parallel real-time tasks. In particular, we derive utilization-tensity bounds for parallel DAG tasks under global EDF scheduling, which facilitate significantly more precise schedulability analysis than the state-of-the-art analysis techniques based on capacity augmentation bound and response time analysis. Moreover, we apply the above results to the federated scheduling paradigm to improve the system schedulability by choosing proper scheduling strategies for tasks with different workload and structure features.

Research Area(s)

  • DAG, global EDF, Multi-core, parallel tasks, real-time scheduling, utilization

Citation Format(s)

Utilization-Tensity Bound for Real-Time DAG Tasks under Global EDF Scheduling. / Jiang, Xu; Sun, Jinghao; Tang, Yue; Guan, Nan.

In: IEEE Transactions on Computers, Vol. 69, No. 1, 8807259, 01.2020, p. 39-50.

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