TY - GEN
T1 - Approximate response time analysis of real-time task graphs
AU - Guan, Nan
AU - Gu, Chuancai
AU - Stigge, Martin
AU - Deng, Qingxu
AU - Yi, Wang
N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].
PY - 2015/1/14
Y1 - 2015/1/14
N2 - The response time analysis problem is intractable for most existing real-time task models, except the simplest ones. Exact solutions for this problem in general have exponential complexity, and may run into scalability problems for large-scale task systems. In this paper, we study approximate analysis for static-priority scheduling of the Digraph Real-Time task model, which is a generalization of most existing graph-based real-time task models. We present two approximate analysis methods RBF and IBF, both of which have pseudo-polynomial complexity. We quantitatively evaluate their analysis precision using the metric speedup factor. We prove that RBF has a speedup factor of 2, and this is tight even for dual-task systems. The speedup factor of IBF is an increasing function with respect to k, the number of interfering tasks. This function converges to 2 as k approaches infinity and equals 1 when k = 1, implying that the IBF analysis is exact for dual-task systems. We also conduct simulation experiments to evaluate the precision and efficiency of RBF and IBF with randomly generated task sets. Results show that the proposed approximate analysis methods have very high efficiency with low precision loss.
AB - The response time analysis problem is intractable for most existing real-time task models, except the simplest ones. Exact solutions for this problem in general have exponential complexity, and may run into scalability problems for large-scale task systems. In this paper, we study approximate analysis for static-priority scheduling of the Digraph Real-Time task model, which is a generalization of most existing graph-based real-time task models. We present two approximate analysis methods RBF and IBF, both of which have pseudo-polynomial complexity. We quantitatively evaluate their analysis precision using the metric speedup factor. We prove that RBF has a speedup factor of 2, and this is tight even for dual-task systems. The speedup factor of IBF is an increasing function with respect to k, the number of interfering tasks. This function converges to 2 as k approaches infinity and equals 1 when k = 1, implying that the IBF analysis is exact for dual-task systems. We also conduct simulation experiments to evaluate the precision and efficiency of RBF and IBF with randomly generated task sets. Results show that the proposed approximate analysis methods have very high efficiency with low precision loss.
KW - DRT
KW - real-time systems
KW - response time analysis
KW - speedup factor
KW - task graphs
UR - https://www.scopus.com/pages/publications/84936947394
UR - https://www.scopus.com/pages/publications/84936947394#tab=impact
U2 - 10.1109/RTSS.2014.20
DO - 10.1109/RTSS.2014.20
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 9781479972876
VL - 2015-January
T3 - Proceedings - Real-Time Systems Symposium
SP - 304
EP - 313
BT - Proceedings - IEEE 35th Real-Time Systems Symposium, RTSS 2014
PB - IEEE
T2 - 35th IEEE Real-Time Systems Symposium, RTSS 2014
Y2 - 2 December 2014 through 5 December 2014
ER -