Towards Principled Budget Enforcement in Real-Time Systems

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.