Towards Principled Budget Enforcement in Real-Time Systems
Joseph Goh, James H. Anderson
Abstract
The increasing complexity and parallelization of hardware and applications in embedded systems have brought unavoidable uncertainty in determining the worst-case execution times (WCETs) of real-time tasks. While budget enforcement can address this uncertainty by limiting an overrunning task from affecting the rest of the system, less explored is how to determine the rate and pattern of failures resulting from budget overruns. For analysis using probabilistic techniques, one must first consider potential dependence relations across different tasks or jobs of the same task. As a result, prior work on probabilistic WCET (pWCET) distributions seeking to enable independence assumptions has suffered from excessive pessimism and intricate derivation processes. In contrast, industry designs have opted for relatively simple heuristics such as “fudge factors,” budgets set by scaling mean or observed worst-case execution times by a constant factor. However, such heuristics do not have a strong analytical foundation. This paper addresses this gap in theory and practice, presenting analysis of a budgeted real-time system’s failure rate not reliant on extensive knowledge of a task’s execution behavior or independence assumptions, only requiring approximations of the mean execution time and standard deviation. This analysis bounds the rate of deadline failures, particularly those which would violate weakly-hard robustness specifications, to efficiently and optimally allocate budget and to evaluate industry heuristics.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
1 top-tier paper has cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
Cited by top-tier papers1
Builds on3
- What Really is pWCET? A Rigorous Axiomatic ProposalSergey Bozhko, Filip Markovic, Georg von der Brüggen, Björn B. BrandenburgRTSS 2023 · 16 citations
- CTA: A Correlation-Tolerant Analysis of the Deadline-Failure Probability of Dependent TasksFilip Markovic, Pierre Roux, Sergey Bozhko, Alessandro V. Papadopoulos et al.RTSS 2023 · 8 citations
- Holistically Budgeting Processing GraphsZelin Tong, Shareef Ahmed, James H. AndersonRTSS 2023 · 6 citations
Related papers
- Efficiently Approximating the Worst-Case Deadline Failure Probability Under EDFGeorg von der Brüggen, Nico Piatkowski, Kuan-Hsun Chen, Jian-Jia Chen et al.RTSS 2021 · 18 citations
- A Distribution-Agnostic and Correlation-Aware Analysis of Periodic TasksFilip Markovic, Georg von der Brüggen, Mario Günzel, Jian-Jia Chen et al.RTSS 2024 · 5 citations
- Monte Carlo Response-Time AnalysisSergey Bozhko, Georg von der Brüggen, Björn B. BrandenburgRTSS 2021 · 28 citations
- Reducing Worst-Case Deadline Failure Probability for EDF SchedulingFei Guan, Xu Jiang, Weipeng Jing, Nan GuanRTSS 2025
- WCDFP Analysis for Real-Time Tasks with Stochastic Release Patterns using Chernoff BoundShining Sun, Chaohai Yu, Xu Jiang, Qingxu Deng et al.RTSS 2025
