In Search of Butterflies: Exceedance Analysis for Real-Time Systems under Transient Overload

In theory, real-time systems are provisioned based on provably sound worst-case execution times (WCETs), but in practice often only empirically derived, unsound execution-time estimates—i.e., nominal execution times (NETs)—are available since WCETs are difficult to obtain on modern hardware. NETs pose two significant challenges: First, since NETs may be exceeded at runtime, any response-time bounds derived from NETs are transitively unsound and may be violated. Second, even a minuscule NET violation can result in large, nonlinear response-time increases due to hard-to-predict, cascading scheduling effects. To explore the risk NET exceedance poses to a system’s temporal correctness, this paper provides the first general, systematic, and explainable methodology for exceedance analysis. The proposed approach supports fixed-priority (FP), earliest-deadline first (EDF), and first-in first-out (FIFO) scheduling on a uniprocessor or within a partitioned multiprocessor platform, and the full spectrum of preemption models from fully preemptive to fully non-preemptive workloads. Additionally, it produces explainable evidence in the form of tunable example traces that engineers can adjust to take system-specific expertise into account. The proposed methodology is evaluated with synthetic task sets and workloads based on an automotive benchmark, and in a case study applied to parts of the WATERS’17 industrial challenge.