TY - GEN
T1 - Bounding the Response Time of DAG Tasks Using Long Paths
AU - He, Qingqiang
AU - Guan, Nan
AU - Lv, Mingsong
AU - Jiang, Xu
AU - Chang, Wanli
N1 - Funding Information:
This work is supported by the Research Grants Council of Hong Kong (GRF 11208522, 15206221) and the National Natural Science Foundation of China (NSFC 62102072). The authors also thank the anonymous reviewers for their helpful comments.
Publisher Copyright:
© 2022 IEEE.
PY - 2022/12
Y1 - 2022/12
N2 - In 1969, Graham developed a well-known response time bound for a DAG task using the total workload and the longest path of the DAG, which has been widely applied to solve many scheduling and analysis problems of DAG-based task systems. This paper presents a new response time bound for a DAG task using the total workload and the lengths of multiple long paths of the DAG, instead of the longest path in Graham's bound. Our new bound theoretically dominates and empirically outperforms Graham's bound. We further extend the proposed approach to multi-DAG task systems. Our schedulability test theoretically dominates federated scheduling and outperforms the state-of-the-art by a considerable margin.
AB - In 1969, Graham developed a well-known response time bound for a DAG task using the total workload and the longest path of the DAG, which has been widely applied to solve many scheduling and analysis problems of DAG-based task systems. This paper presents a new response time bound for a DAG task using the total workload and the lengths of multiple long paths of the DAG, instead of the longest path in Graham's bound. Our new bound theoretically dominates and empirically outperforms Graham's bound. We further extend the proposed approach to multi-DAG task systems. Our schedulability test theoretically dominates federated scheduling and outperforms the state-of-the-art by a considerable margin.
UR - http://www.scopus.com/inward/record.url?scp=85146122561&partnerID=8YFLogxK
U2 - 10.1109/RTSS55097.2022.00047
DO - 10.1109/RTSS55097.2022.00047
M3 - Conference article published in proceeding or book
AN - SCOPUS:85146122561
T3 - Proceedings - Real-Time Systems Symposium
SP - 474
EP - 486
BT - Proceeding - 43rd IEEE Real-Time Systems Symposium, RTSS 2022
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 43rd IEEE Real-Time Systems Symposium, RTSS 2022
Y2 - 5 December 2022 through 8 December 2022
ER -