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

Xu Jiang, Jinghao Sun, Yue Tang, Nan Guan*

*Corresponding author for this work

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

22 Citations (Scopus)

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.
Original languageEnglish
Article number8807259
Pages (from-to)39-50
JournalIEEE Transactions on Computers
Volume69
Issue number1
Online published20 Aug 2019
DOIs
Publication statusPublished - Jan 2020
Externally publishedYes

Research Keywords

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

Fingerprint

Dive into the research topics of 'Utilization-Tensity Bound for Real-Time DAG Tasks under Global EDF Scheduling'. Together they form a unique fingerprint.

Cite this