Lune

RTSS2025Top-tier venue

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.

Questions to start from

Lune can draw on

its abstract · related work

Get the answer

Free to start. No credit card required.

Related papers

  1. Monte Carlo Response-Time AnalysisSergey Bozhko, Georg von der Brüggen, Björn B. BrandenburgRTSS 2021 · 28 citations
  2. Towards Principled Budget Enforcement in Real-Time SystemsJoseph Goh, James H. AndersonRTSS 2024 · 1 citation
  3. 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
  4. Analytical Approximations in Probabilistic Analysis of Real-Time SystemsFilip Markovic, Thomas Nolte, Alessandro Vittorio PapadopoulosRTSS 2022 · 9 citations
  5. Suspension-Aware Fixed-Priority Schedulability Test with Arbitrary Deadlines and Arrival CurvesMario Günzel, Niklas Ueter, Jian-Jia ChenRTSS 2021 · 10 citations
Dusk over the sea between two cliffs drawn in fine vertical lines