A Distribution-Agnostic and Correlation-Aware Analysis of Periodic Tasks
Filip Marković, Georg von der Brüggen, Mario Günzel, Jian-Jia Chen, Björn B. Brandenburg · 2024
Real-time tasks often exhibit correlated execution-time distributions due to common factors such as shared caches, resources, and inputs. Yet state-of-the-art probabilistic analysis still overlooks the impact of correlation, a gap that has been highlighted as a major open problem in the field. This paper responds to the open problem with the first correlation-aware analysis (CAA) of periodic tasks with stochastic execution times. The proposed analysis, which derives response-time distributions to infer upper bounds on deadline-failure probabilities, applies to a novel task model that incorporates information about both intra- and inter-task dependencies. In addition, the paper shows how to statistically infer the two model parameters using confidence intervals obtained via nonparametric bootstrapping. Notably, the inference method described is distribution-agnostic, meaning that it does not assume any particular probability distribution a priori, thereby eliminating a major risk of misclassifying the ground-truth execution behavior. By design, CAA dominates state-of-the-art correlation-tolerant analysis (CTA). The significantly better accuracy of CAA is demonstrated via experiments with synthetically generated workloads, while a case study based on the WATERS’ 17 industrial challenge provides a proof-of-concept of the statistical inference method.