Analysis of Long-term Average Behaviors of Probabilistic Task Systems
Yifan Cai, Linh Thi Xuan Phan, P.S. Thiagarajan · 2024
We present a Markov chain-based framework for studying the longterm average behaviors of periodic real-time task systems in which the tasks have stochastically varying computation times.In sharp contrast to previous work, we construct our Markov chains w.r.t. to a unit of time that is not required to be the hyperperiod of the task system.Our chains have an important property called irreducibility, and this secures the mathematical basis for a simple sampling procedure for estimating the long-term averages of interest.This is significant because for task systems of practical interest, it will be computationally infeasible to use hyperperiods to determine the required expected values.Our experimental results show that our method can be used to analyze long-term average behaviors -such as deadline misses and weakly-hard constraint violations -with high accuracy, and that it scales well to large systems (with up to 1000 tasks).We further demonstrate its practical utility using a case study of a rover control system.