TY - JOUR
T1 - Utilization-Tensity Bound for Real-Time DAG Tasks under Global EDF Scheduling
AU - Jiang, Xu
AU - Sun, Jinghao
AU - Tang, Yue
AU - Guan, Nan
PY - 2020/1
Y1 - 2020/1
N2 - 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.
AB - 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.
KW - DAG
KW - global EDF
KW - Multi-core
KW - parallel tasks
KW - real-time scheduling
KW - utilization
UR - http://www.scopus.com/inward/record.url?scp=85078706277&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85078706277&origin=recordpage
U2 - 10.1109/TC.2019.2936477
DO - 10.1109/TC.2019.2936477
M3 - RGC 21 - Publication in refereed journal
SN - 0018-9340
VL - 69
SP - 39
EP - 50
JO - IEEE Transactions on Computers
JF - IEEE Transactions on Computers
IS - 1
M1 - 8807259
ER -