A Capacity Augmentation Bound For Real-Time Constrained-Deadline Parallel Tasks Under Gedf
Keywords
Capacity augmentation bound; directed acyclic graph (DAG); global earliest deadline first (GEDF); parallel tasks; real-time scheduling; schedulability analysis
Abstract
Capacity augmentation bound is a widely used quantitative metric in theoretical studies of schedulability analysis for directed acyclic graph (DAG) parallel real-time tasks, which not only quantifies the suboptimality of the scheduling algorithms, but also serves as a simple linear-time schedulability test. Earlier studies on capacity augmentation bounds of the sporadic DAG task model were either restricted to a single DAG task or a set of tasks with implicit deadlines. In this paper, we consider parallel tasks with constrained deadlines under global earliest deadline first policy. We first show that it is impossible to obtain a constant bound for our problem setting, and derive both lower and upper bounds of the capacity augmentation bound as a function with respect to the maximum ratio of task period to deadline. Our upper bound is at most 1.47 times larger than the optimal one. We conduct experiments to compare the acceptance ratio of our capacity augmentation bound with the existing schedulability test also having linear-time complexity. The results show that our capacity augmentation bound significantly outperforms the existing linear-time schedulability test under different parameter settings.
Publication Date
11-1-2018
Publication Title
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume
37
Issue
11
Number of Pages
2200-2211
Document Type
Article
Personal Identifier
scopus
DOI Link
https://doi.org/10.1109/TCAD.2018.2857362
Copyright Status
Unknown
Socpus ID
85055505869 (Scopus)
Source API URL
https://api.elsevier.com/content/abstract/scopus_id/85055505869
STARS Citation
Sun, Jinghao; Guan, Nan; Jiang, Xu; Chang, Shuangshuang; and Guo, Zhishan, "A Capacity Augmentation Bound For Real-Time Constrained-Deadline Parallel Tasks Under Gedf" (2018). Scopus Export 2015-2019. 9163.
https://stars.library.ucf.edu/scopus2015/9163