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

Xu Jiang, Jinghao Sun, Yue Tang, Nan Guan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

10 Citations (Scopus)


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
Number of pages12
JournalIEEE Transactions on Computers
Issue number1
Publication statusPublished - 1 Jan 2020


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

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


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