WCDFP Analysis for Real-Time Tasks with Stochastic Release Patterns using Chernoff Bound
Shining Sun, Chaohai Yu, Xu Jiang, Qingxu Deng, Nan Guan
Abstract
Most existing research in probabilistic real-time scheduling analysis has primarily focused on systems with only stochastic execution times, neglecting the stochastic nature of task release patterns in many real-world applications. Current approaches for handling stochastic release times rely on computationally expensive convolution-based methods, which has poor scalability, especially when both execution and release times are stochastic. This paper presents novel techniques to apply the Chernoff Bound approach to the analysis of systems with both stochastic execution and release times. The key challenge lies in adapting the Chernoff Bound, which traditionally operates on a fixed number of random variables, to handle the stochastic job counts resulting from stochastic release patterns. Our main contribution is a new technique for bounding convolutions involving random numbers of random variables using Chernoff principles. Through comprehensive evaluation, we demonstrate that our approach achieves several orders of magnitude speedup compared to state-of-the-art convolution-based methods while simultaneously improving analysis precision.
Ask Lune
Know where this paper stands in minutes, not an afternoon.
Lune can read the top-tier papers that cite it and the ones closest to it, and tells you what it claims, what came after and where it falls short, each point cited to the paper it comes from. No skimming, no AI slop.
Related papers
- Monte Carlo Response-Time AnalysisSergey Bozhko, Georg von der Brüggen, Björn B. BrandenburgRTSS 2021 · 28 citations
- Towards Principled Budget Enforcement in Real-Time SystemsJoseph Goh, James H. AndersonRTSS 2024 · 1 citation
- Critical Instant for Probabilistic Timing Guarantees: Refuted and RevisitedKuan-Hsun Chen, Mario Günzel, Georg von der Brüggen, Jian-Jia ChenRTSS 2022 · 15 citations
- Analytical Approximations in Probabilistic Analysis of Real-Time SystemsFilip Markovic, Thomas Nolte, Alessandro Vittorio PapadopoulosRTSS 2022 · 9 citations
- Suspension-Aware Fixed-Priority Schedulability Test with Arbitrary Deadlines and Arrival CurvesMario Günzel, Niklas Ueter, Jian-Jia ChenRTSS 2021 · 10 citations
