Capacity Augmentation Function for Real-Time Parallel Tasks with Constrained Deadlines under GEDF Scheduling

Jinghao Sun, Nan Guan, Shuangshuang Chang, Feng Li, Qingxu Deng, Wang Yi

Research output: Journal article publicationJournal articleAcademic researchpeer-review


Capacity augmentation bound (CAB) is a widely-used quantitative metric in theoretical analysis for DAG parallel real-time tasks, which reveals the key factors the schedulability of DAG tasks heavily depending on: the normalized utilization (the ratio of the total utilization to the core numbers) and the tensity (the maximum ratio of task’s longest path length to task’s deadline). However, CAB requires both factors of a schedulable task system to be capped by the same threshold. A task system with a normalized utilization slightly larger than that threshold but very small tensity, or very smaller normalized utilization but slightly larger than that threshold have good chance to be scheduled are both denied by CAB. To this end, we propose a new concept called capacity augmentation function (CAF) to better characterize the schedulability of parallel real-time tasks, which provides more loose and different threshold for both factors. In particular, we derive a CAF-based linear-time schedulability test for real-time constrained-deadline DAG tasks under global EDF, which entirely dominates the state-of-the-art CAB-based test for constrained-deadline settings. Finally, we conduct experiments to compare the acceptance ratio of our CAF-based test with the existing schedulability tests also having linear-time complexity. The results show that CAF-based test significantly outperforms the existing linear-time schedulability test under different parameter settings.

Original languageEnglish
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Publication statusAccepted/In press - 1 Jan 2020


  • Capacity augmentation function
  • Constrained deadline
  • DAG
  • GEDF
  • Schedulability.

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Cite this