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

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

Keywords

  • 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

Cite this