TY - JOUR
T1 - A General Analysis Framework for Soft Real-time Tasks
AU - Dong, Zheng
AU - Liu, Cong
AU - Bateni, Soroush
AU - Kong, Zelun
AU - He, Liang
AU - Zhang, Lingming
AU - Prakash, Ravi
AU - Zhang, Yuqun
N1 - Funding Information:
This work was supported in part by National Key R&D Program of China (Grant No. 2017YFC0804002), Shenzhen Peacock Plan (Grant No. KQTD2016112514355531), the Science and Technology Innovation Committee Foundation of Shenzhen (Grant No. ZDSYS201703031748284 and No. JCYJ20170817110848086) and the Program for University Key Laboratory of Guangdong Province (Grant No. 2017KSYS008). This work also supported in part by US NSF under Grants CNS 1527727 and CNS CAREER 1750263. Zheng Dong and Yuqun Zhang work was partially accomplished during the visit to Southern University of Science and Technology. This work was partially accomplished during Z. Dong’s visit to Southern University of Science and Technology.
Publisher Copyright:
© 2018 IEEE.
PY - 2019/6/1
Y1 - 2019/6/1
N2 - Much recent work has been conducted on supporting soft real-time tasks on multiprocessors due to the multicore revolution. While most earlier works focus on the traditional sporadic task model with deterministic worst-case specification, several recent works investigate the stochastic nature of many workloads seen in practice, specifying task execution times using average-case provisioning instead of the worst case. Unfortunately, all the existing work on supporting soft real-time workloads ignores a simple practical fact that the job inter-arrival time (or task period) is also stochastic for many real-world applications. Adopting a fixed worst-case period to model all the arriving pattern is rather pessimistic and may result in significant capacity loss in practice. Based on these observations, we present a general soft real-time multiprocessor schedulability analysis framework in this paper for practical sporadic task systems specified by stochastic period and execution demand, following probability distributions. Our analysis can be generally applied to global tunable priority-based schedulers, which allow any job's priority to be changed dynamically at runtime within a priority window of constant length. We have extensively evaluated the analysis framework using a MPEG video decoding case study and simulation-based experiments. Experimental results demonstrate significant advantages of our analysis, which yields over 200 and 50 percent improvements compared to existing analysis assuming worst-case task periods in terms of schedulability and magnitude of the derived tardiness bound, respectively.
AB - Much recent work has been conducted on supporting soft real-time tasks on multiprocessors due to the multicore revolution. While most earlier works focus on the traditional sporadic task model with deterministic worst-case specification, several recent works investigate the stochastic nature of many workloads seen in practice, specifying task execution times using average-case provisioning instead of the worst case. Unfortunately, all the existing work on supporting soft real-time workloads ignores a simple practical fact that the job inter-arrival time (or task period) is also stochastic for many real-world applications. Adopting a fixed worst-case period to model all the arriving pattern is rather pessimistic and may result in significant capacity loss in practice. Based on these observations, we present a general soft real-time multiprocessor schedulability analysis framework in this paper for practical sporadic task systems specified by stochastic period and execution demand, following probability distributions. Our analysis can be generally applied to global tunable priority-based schedulers, which allow any job's priority to be changed dynamically at runtime within a priority window of constant length. We have extensively evaluated the analysis framework using a MPEG video decoding case study and simulation-based experiments. Experimental results demonstrate significant advantages of our analysis, which yields over 200 and 50 percent improvements compared to existing analysis assuming worst-case task periods in terms of schedulability and magnitude of the derived tardiness bound, respectively.
KW - probability distribution
KW - Real-time scheduling
KW - schedulability test
KW - stochastic tasks
KW - tardiness bound
UR - http://www.scopus.com/inward/record.url?scp=85058079498&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85058079498&partnerID=8YFLogxK
U2 - 10.1109/TPDS.2018.2884980
DO - 10.1109/TPDS.2018.2884980
M3 - Article
AN - SCOPUS:85058079498
SN - 1045-9219
VL - 30
SP - 1222
EP - 1237
JO - IEEE Transactions on Parallel and Distributed Systems
JF - IEEE Transactions on Parallel and Distributed Systems
IS - 6
M1 - 8565912
ER -