WCET (Worst Case Execution Time) analysis: Question bank

Before we start, some symbols and words that MUST be sharp, because every trap leans on them.

Several items below use the response-time inequality from the parent note. Here is every symbol in it, in plain words, before we lean on any of them. Picture a single task (call it task $i$ ) as a job that must finish before a stopwatch runs out:

Definition The response-time symbols

Consider one task, task $i$ , running among other tasks. Four quantities describe whether it "makes it in time":

$C_{i}$ = the ==worst-case execution time (WCET) of task $i$ itself== — how long its own code takes on the longest path, counting no interruptions. This is the number the whole page is about.
$I_{i}$ = the ==interference== — the total time task $i$ is pushed aside while higher-priority tasks run instead of it. It is computed by summing how often each higher-priority task can preempt task $i$ within its window, times that task's own WCET.
$R_{i}$ = the ==response time== — the total wall-clock time from when task $i$ is released until it finishes, i.e. its own work plus all the interference: $R_{i} = C_{i} + I_{i}$ .
$D_{i}$ = the ==deadline== — the stopwatch limit; the moment by which task $i$ must be done. The task is safe to schedule when the response time never crosses the deadline: $R_{i} = C_{i} + I_{i} \leq D_{i}$ . Look at Figure s01 to see these four laid out on a timeline.

Two acronyms also recur in the traps; define them once here:

Figure s02 shows, at a glance, why a safe bound must sit at or above the true worst case while a tight one hugs it — the mental picture behind almost every trap on this page.

True or false — justify

The maximum observed time in a test campaign is a safe WCET bound.

False. Measurement only samples the inputs and hardware states you happened to hit; the true worst case may need an untested input, cache layout, or interrupt timing you never triggered, so the observed max can sit below the real WCET.

Adding a fixed safety margin to the measured maximum makes measurement-based WCET provably safe.

False. The margin is a guess. Nothing proves the true worst case is within that margin of what you saw, so the result is more likely safe, not guaranteed safe.

WCET is a property of the program alone.

False. WCET is program + hardware + compiler. The identical C function has a different WCET on a Cortex-M0 versus an out-of-order Cortex-A, and again after a compiler flag change.

A loop with a fixed bound of 100 iterations always contributes exactly 100 × (body time).

False. Iterations can differ: the first iteration often misses the cache while later ones hit, and data-dependent branches inside the body may take different sub-paths. You bound the sum, not 100 identical copies.

Static analysis gives the exact WCET of your real system.

False. It gives the exact answer for its model. If the model of the cache or pipeline is conservative (as it must be to stay safe), the number is safe but pessimistic — exact for the model, an over-estimate for reality.

If you optimise a program to run faster on average, its WCET must also drop.

False. Optimisations like caching, branch prediction, or speculative work can widen the gap between best and worst case; the worst path may even get slower while the average improves.

Turning off the cache always makes WCET analysis easier and the WCET smaller.

Mostly true for easier, false for smaller. Disabling the cache removes hit/miss uncertainty so analysis is simpler and tighter, but every access now pays memory latency, so the actual WCET usually grows.

The response-time formula

R_{i} = C_{i} + I_{i} \leq D_{i}

needs the WCET only for task

i

False. The interference term

I_{i}

is built from the WCETs (the

C

values) of every higher-priority task, so under-estimating any task's WCET can falsely "prove" a schedule that actually misses deadlines.

Extreme Value Theory (EVT) turns measurements into a mathematically safe bound.

False. EVT fits a tail distribution to observed data; it estimates a rare-event bound but rests on statistical assumptions (independence, that the tail is representative). It gives a probabilistic bound, not a guaranteed safe one.

A tighter WCET is always better than a looser one.

False — only if it stays safe. A tighter number that quietly drops below the true worst case is worse than a loose safe one, because it can make an unschedulable system look schedulable.

Spot the error

"We measured every function in isolation and summed the maxima, so our total WCET is safe."

The per-function maxima may occur under incompatible states — the input that makes A slow may leave the cache in a state that also makes B slow, but they might not co-occur. Summing isolated maxima can be over-pessimistic; worse, it can miss cross-function timing effects (pipeline, cache) entirely, so it is neither guaranteed tight nor guaranteed safe.

"Our loop is data-dependent, so we let the ILP solver figure out the iteration count from the source."

An ILP-based WCET solver cannot invent loop bounds; it needs a supplied flow constraint. Without a bound the CFG has a cycle of unbounded weight and the solver returns infinity (or refuses). Loop bounds come from human annotation or a separate value analysis.

"We built the CFG from the C source, so it exactly represents what runs."

The compiler inlines, unrolls, reorders and merges blocks, so the machine-code CFG differs from the source CFG. WCET must be analysed on the compiled binary, not the source.

"WCET plus interference equals response time, and if that's under the deadline we're done — no need to consider interrupts."

Interrupts add extra, often asynchronous, execution and can inflate the interference term. If they aren't modelled inside

I_{i}

(or bounded separately), the response-time proof is unsound.

"Cache miss = 200 cycles, our block has 3 accesses, so worst-case block time = base + 600."

Assuming all accesses miss is safe but usually far too loose. Proper cache analysis classifies accesses (Always-Hit / Always-Miss / First-Miss); e.g. a small array reused in a loop is "first-miss then always-hit", so only the first pass pays 200.

"Path complexity is

2^{branches}

, so we must enumerate every path to find the longest."

You do not enumerate paths. That's why WCET tools reduce the longest-path search to an ILP over block execution counts with flow-conservation constraints — polynomial-sized, not exponential-enumerated.

Why questions

Why does the WCET formula take a max over paths rather than an average or a sum?

Because a task will, on some run, follow its single longest path, and safety means covering that run. Averaging under-counts it; summing all paths counts runs that never happen simultaneously.

Why is finding the longest program path NP-hard in general, yet WCET tools still scale?

The general longest-path problem with arbitrary constraints is NP-hard, but real CFGs are structured (reducible loops, bounded nesting) and the ILP formulation with flow constraints solves the practical cases quickly.

Why do we need flow constraints (loop bounds, mutually-exclusive branches) at all?

Without them the analyser assumes the worst on every branch and an unbounded loop, yielding infinite or absurdly large WCET. Constraints inject the semantic facts the raw CFG can't express.

Why can two consecutive iterations of the same loop have different execution times?

Cache and pipeline state carries over: the first iteration may miss and fill the cache, later iterations hit; branch predictors also "warm up". The instructions are identical but the hardware context is not.

Why prefer hybrid analysis over pure static or pure measurement?

Static analysis handles control flow and loop bounds soundly but models complex hardware pessimistically; measurement captures real hardware timing but can't exhaustively cover control flow. Hybrid uses static for structure and measured times for small basic blocks.

Why does safety-critical certification usually demand static (or hybrid) analysis over pure measurement?

Certification needs a provable upper bound (soundness), and pure measurement can only offer statistical confidence, never a guarantee that the worst input was hit.

Why does making the WCET too loose cause real harm, not just waste?

An over-pessimistic

C_{i}

inflates every response time in the schedulability test, so a system that would actually meet its deadlines is wrongly declared unschedulable, forcing costlier hardware or dropped features.

Edge cases

What is the WCET of a loop whose bound depends on an input the analyser cannot bound?

If no bound can be established, the sound answer is unbounded (infinite) WCET — the code is not WCET-analysable as written. The fix is to enforce a hardware/software cap on the iteration count.

What happens to WCET analysis for a purely straight-line program with no branches or loops?

The CFG is a single path, so path analysis is trivial; WCET is just the sum of block times under worst-case hardware state — the hardware modelling is the only remaining difficulty.

If a function is never called on the worst-case path, does its WCET contribute to the caller's WCET?

No — the ILP assigns that block/call an execution count of zero on the winning path, so its time drops out. Only code on the longest feasible path counts.

For a task with zero interference (

I_{i} = 0

, highest priority, no interrupts), does

R_{i} = C_{i}

Yes — with no higher-priority work and no interrupt or blocking delay, response time collapses to the task's own WCET. This is the ideal isolated case scheduling analysts start from.

What if the true worst-case input is infeasible — logically impossible for the real system to produce?

Then the safe-but-untight WCET counts a run that can never occur, over-estimating. Extra flow constraints (infeasible-path elimination) tell the solver to exclude it, tightening the bound without breaking safety.

Two builds of the same code with different optimisation levels — can -O2 have a larger WCET than -O0?

Yes, occasionally. Aggressive optimisation may reorder or speculate in a way that worsens the worst path (e.g. added misprediction or code-layout cache effects) even while typical runs speed up. WCET must be re-analysed per build.

If measured max = 612 and 99.9th percentile = 580, is a bound of 600 acceptable for a hard real-time deadline?

No. 600 sits below an already-observed value (612), so it is demonstrably unsafe — never mind the untested worst case. Any hard bound must exceed all observations and account for the unseen tail.

Recall One-line self-test

Give the two properties every WCET bound must trade off, in order of priority. ::: Safety (soundness) first — never below the true worst case; then tightness — as close to it as possible.