Worst-Case Execution Time Analysis and What the Bound Is Worth

Every schedulability argument in a safety case rests on a number that is harder to obtain than it looks. The response-time analysis that decides whether a periodic task meets its deadline needs each task’s worst-case execution time, and the analysis is only as trustworthy as that input. Measuring the slowest observed run of a task on a test bench produces a maximum, not a worst case, and the difference between the two is the subject of a whole field. A measured maximum is a statement about the inputs and the hardware state that happened to occur; a worst case is a statement about all inputs and all hardware states the task can encounter.

Why measurement cannot close the gap

Measurement has an obvious appeal: it uses the real hardware, it accounts for everything the hardware does, and it produces a number without a model. Its deficiency is coverage. The execution time of a piece of code depends on the values it processes, on the path it takes through its branches, on the state of the caches and the pipeline, and on interference from other bus masters sharing the resources. A test campaign samples that space; it does not enumerate it.

The path problem alone is enough to break the method. A routine with a loop whose trip count depends on an input has an execution time proportional to the trip count, and the maximum trip count may be reached only by an input that no test generated. A routine whose timing depends on a data-dependent branch has an execution time that varies with the data, and the slow path may be the one taken for a value the test suite never produced. A routine whose worst case involves an unlucky sequence of cache conflicts may require a specific interleaving of preceding code that the bench never arranged.

The hardware state problem is worse, because it is invisible in the source. Two runs of the same function with the same input can differ in execution time by a factor of several depending on whether the instructions were in the instruction cache, whether the data was in the data cache, and whether the pipeline was drained by an interrupt. A measurement campaign that reports the maximum over many runs is reporting the maximum over the states that occurred, and the states that did not occur are exactly the ones the analysis needs.

Measurement still has a role, and the standards recognise it. It is used to validate a static analysis: the analysis produces a bound, and measurement confirms that observed executions do not exceed it. A bound that is violated by a measurement is wrong, and the discrepancy points to a modelling error. The converse is not true, which is why measurement alone cannot establish a bound.

Static analysis as a path problem plus a timing problem

Static analysis decomposes the question into two parts, and the decomposition is the field’s central idea.

The first part is the path problem: which sequences of instructions can the task execute, and how long is the longest such sequence in terms of instruction count? This is answered on the control-flow graph, with loop bounds derived from the source structure or supplied as annotations, and with infeasible paths excluded by analysis. A loop whose bound is a constant is easy; a loop whose bound is a function of a parameter requires the analysis to propagate the parameter’s range, and a loop whose bound depends on a value read from a sensor requires the programmer to supply the bound as an annotation that the analysis then checks for consistency.

The second part is the timing problem: given a sequence of instructions, how many cycles does each take on this processor? This is answered by a model of the microarchitecture, and the model’s fidelity determines whether the bound is useful. A processor with a simple pipeline, no caches, and no speculation has a timing model that can be exact, which is why such processors remain attractive for the highest integrity levels. A processor with a deep out-of-order pipeline, speculative execution, and a shared last-level cache has a timing model that is either very pessimistic or not sound, and the choice between those two failures is the practical dilemma.

The two parts are not independent, which is what makes the problem hard. The path determines the instruction sequence, the instruction sequence determines the cache behaviour, and the cache behaviour determines the timing of the instructions. Analyses therefore iterate: a path analysis proposes a candidate, a cache analysis computes the memory behaviour along it, a timing analysis computes the cost, and the result feeds back into the path analysis to prune or reorder the candidates. The iteration terminates because the candidate set shrinks, but the fixed point it reaches is not necessarily the true worst case unless the abstractions are conservative at every step.

Abstract interpretation and the cache-state join

The standard technique for the cache part is abstract interpretation over the set of possible cache states. The analysis associates each program point with an abstract cache state that records, for each memory block, whether it is definitely cached, definitely not cached, or unknown. The transfer function for a memory access updates the state according to the cache’s replacement policy, and at a control-flow join the states from the incoming edges are combined by taking the meet: a block is definitely cached only if it is definitely cached on every incoming path.

The classification that results is what the timing analysis consumes. An access to a block that is definitely cached costs a hit; an access that is definitely not cached costs a miss; an access that is unknown must be charged as a miss to remain sound. The fraction of accesses in the unknown category is the pessimism of the analysis, and reducing it is the whole art. Loop unrolling, path-sensitive analysis at the join points, and the classification of the replacement policy’s behaviour all serve to move blocks from unknown to definite.

The replacement policy matters more than it seems. A fully associative cache with an LRU policy has an abstract semantics that is well understood: a block survives in the cache if the number of distinct blocks accessed since its last use is less than the associativity. A set-associative cache with a pseudo-LRU or a random replacement policy does not have that property, so the analysis must be more conservative, and the achievable precision drops. This is one reason certification-oriented processors often provide cache control: the ability to lock a region, to configure a way as scratchpad, or to disable the cache entirely for a critical routine, which converts an unknown into a definite.

The features that make the bound unusable

Three microarchitectural features are the usual culprits when a timing analysis produces a bound so large that the schedulability test fails.

Speculative execution is the first. A processor that predicts branches and executes ahead does work that may be discarded, and the discarded work still consumes cycles. A misprediction costs the pipeline refill, and the analysis must either bound the number of mispredictions along a path or charge the refill to every branch. Processors with branch target buffers and return address stacks have prediction behaviour that depends on history, which is a state the analysis would have to track. Some safety-oriented cores allow the predictor to be disabled, which trades average performance for analysability, and that trade is often the right one.

Out-of-order execution is the second. When instructions can issue in any order subject to dependencies, the execution time of a sequence is not the sum of the individual latencies but a function of the dependency graph and the available execution units. The bound requires a model of the reorder buffer, the reservation stations, and the issue policy, and the resulting analysis is both complex and pessimistic. In-order pipelines with a documented stall behaviour are far easier to bound.

Shared resources are the third, and in a multicore device they are unavoidable. A last-level cache, a memory controller, and a system bus are shared between cores, so a core’s execution time depends on the other cores’ access patterns. The interference can be bounded by treating the shared resource as a server with a defined service policy, but that requires the hardware to implement a policy the analysis can model. Devices without such a policy, where any core can monopolise the bus, produce bounds that are effectively the sum of all cores’ demands, which is why multicore certification arguments often resort to time partitioning or to running only one core in a safety mode.

Feature	Effect on the bound	Mitigation
Branch prediction	History-dependent, hard to bound	Disable, or bound mispredictions per path
Out-of-order issue	Dependency-graph model needed	Use in-order cores for critical code
Shared last-level cache	Inter-core interference	Partition, lock, or bypass
Variable-latency memory	Access-time spread	Use scratchpad with fixed latency
Interrupts	Arbitrary preemption points	Bound the handler and the masking

From execution time to response time

The worst-case execution time is an input to a larger calculation, not a result in itself. For a periodic task under fixed-priority preemptive scheduling, the response-time analysis computes the interference from higher-priority tasks over the task’s own execution window, and iterates because the interference depends on the window length. The recurrence converges when the window stops growing, and the fixed point is the response time. If the fixed point exceeds the deadline, the task set is not schedulable under the assumptions, and the assumptions include the execution times, the periods, and the blocking from shared resources.

The blocking term is where a timing analysis and a locking design meet. A task can be delayed by a lower-priority task holding a resource, and the delay is bounded by the longest critical section among the lower-priority tasks that share that resource. A ceiling-based locking protocol makes that bound computable statically, because the longest critical section is fixed at design time; without such a protocol the blocking term is unbounded and the response-time analysis has no fixed point to find. The same reasoning governs the sharing of redundant channels, where a task on one channel waiting for a resource held by the other becomes part of the response time that the Voting Redundancy and Average Probability of Failure on Demand calculation assumes is bounded.

The interaction with interrupts is the other place the analysis is often incomplete. An interrupt handler executes at a priority above every task, so its execution time is added to every task’s response time, and its own execution time is subject to the same analysis problem. A handler whose duration depends on the number of pending devices, or on a queue length, needs its own bound. Handlers that are allowed to nest multiply the interference, and the standard advice to keep handlers short and defer work is as much a timing argument as a design one.

What the certification frameworks require

ISO 26262-6 requires that the timing behaviour of the software be verified against the timing requirements, and it lists methods including static analysis and measurement, with the recommendation depending on the level. It does not mandate a particular technique, and it does not require a bound to be sound in the mathematical sense; it requires that the argument for the timing be made and that the evidence support it.

The consequence is that the practical standard is the weakest argument a reviewer will accept, which varies by domain. Airborne software at the highest level generally requires a deterministic timing argument with a static analysis and a validation by measurement, and the processor is usually chosen for its analysability. Automotive software at the highest level increasingly requires similar rigour, but the volume of code and the use of multicore devices make the analysis harder, and the common practice is a combination of measurement, a documented budget, and a partitioning scheme that isolates the critical tasks from the rest.

Where the communication path is time-triggered, part of the timing argument is already made by the schedule, as described in Time-Triggered Buses, Global Time, and Bus Guardians. The slot boundaries bound the delivery jitter without any analysis of the software, and what remains for the execution-time analysis is the software’s own work plus the interrupt handlers that the protocol’s timing requires.

The honest position is that a bound is only as good as its assumptions, and the assumptions must be written down. A bound that assumes no cache misses from a shared region, a fixed interrupt latency, and a loop bound supplied by the programmer is a bound on a model of the system, not on the system. The model’s assumptions are themselves verification obligations, and a safety case that quotes the number without the assumptions is quoting a figure whose validity cannot be checked. That is the same failure as a diagnostic coverage percentage quoted without its fault model, and it is why the numbers in a safety case are always accompanied by the argument that produced them.