WCET (Worst Case Execution Time) analysis: Worked examples

Everything here uses one made-up but consistent cost model so numbers are checkable by hand. Read the model once:

The scenario matrix

Every WCET puzzle is really one (or a mix) of these cells. The examples below are tagged with the cell(s) they cover, and together they fill the whole grid.

Cell	Case class	What makes it tricky	Covered by
C1	Fixed loop, no branch	Baseline: multiply body cost by iteration count	Ex 1
C2	Branch inside loop	Which side is longer? Worst case takes the long side every time	Ex 2
C3	Zero-iteration loop	Loop that may run 0 times — boundary condition	Ex 3
C4	Cache: cold vs warm	First access misses, rest hit — miss happens once, not every time	Ex 4
C5	Nested loops	Inner count multiplies outer count	Ex 5
C6	Data-dependent bound + infeasible path	Two branches that can't both be taken → naive sum over-counts	Ex 6
C7	Interrupt interference	External time added on top of your own code	Ex 7
C8	Word problem / schedulability	Turn a WCET number into a pass/fail deadline decision	Ex 8
C9	Exam twist: average ≠ worst	Measurement-based trap; the mean lies	Ex 9

Example 1 — Fixed loop, no branch (cell C1)

Worked example Statement

void clear(int buf[], int n) {   // n is FIXED at 20
    for (int i = 0; i < n; i++)  // Block B: loop test = 1 cycle
        buf[i] = 0;              // Block C: store = 1 cycle
}

Block A (set i=0) = 1 cycle, runs once. What is the WCET in cycles?

Forecast: guess a number now. (Hint: how many times does the test run vs the body?)

Count how many times each block runs. Why this step? WCET = (cost of a block) × (times it executes). We must nail the counts first.
- Block A: once → 1 execution.
- Block B (the test i < n): it runs once before each body and one extra time to detect the loop is over. For n = 20 that is $20 + 1 = 21$ executions.
- Block C (the body): runs exactly n = 20 times.
Multiply cost × count and sum. Why this step? This is the core WCET formula for a straight loop with no branches — no path choice exists, so the longest path is the only path. $WCET = A 1 + B 21 \times 1 + C 20 \times 1 = 1 + 21 + 20 = 42 cycles$

Verify: Sanity-check the loop-test count. A for loop that does 20 bodies always evaluates its condition 21 times (the last one fails and exits). Units: cycles + cycles = cycles. ✓ 42 cycles.

Example 2 — Branch inside the loop (cell C2)

Worked example Statement

for (int i = 0; i < 10; i++) {   // B: test = 1 cycle
    if (data[i] > threshold) {   // C: compare = 1 cycle
        big_work(data[i]);       // D: this branch = 8 cycles
    } else {
        small_work();            // E: this branch = 2 cycles
    }
}

Block A (init) = 1 cycle. WCET?

Forecast: which branch does the worst case take — and how often?

Pick the worst side of the branch. Why this step? WCET asks for the longest route. Block D (8) beats Block E (2). The worst case is when the if is true on every single iteration — nothing in the problem forbids that. $worst body cost = C 1 + max (D 8, E 2) = 1 + 8 = 9 cycles$
Count executions with the fixed bound = 10. Why this step? Same counting rule as Ex 1: test runs $10 + 1 = 11$ times, body runs 10 times. $WCET = A 1 + B 11 \times 1 + worst body 10 \times 9 = 1 + 11 + 90 = 102 cycles$

Verify: Compare against the best case (else every time): $1 + 11 + 10 \times (1 + 2) = 42$ . Worst (102) > best (42), as it must be. ✓ 102 cycles.

Example 3 — The loop that might not run (cell C3)

Worked example Statement

void process(int n) {            // n can be 0..50
    setup();                     // A: 4 cycles, always
    for (int i = 0; i < n; i++)  // B: test = 1 cycle
        step();                  // C: body = 3 cycles
    finish();                    // F: 2 cycles, always
}

WCET across all allowed n? (Recall 0..50 means every integer from 0 through 50.)

Forecast: does n = 0 give the worst case, or the best?

Find which n maximises time. Why this step? Here n is a range, not a fixed number. WCET is the max over the whole range. Each iteration adds cost, so more iterations = more time → the worst case is the largest allowed n, which is 50.
But first check the degenerate n = 0 case so we know the floor. Why this step? Boundary conditions are where bugs hide. If n = 0, the loop body never runs; the test runs once (fails immediately). $T (n = 0) = A 4 + B 1 + F 2 = 7 cycles (this is the BEST case)$
Now the worst case, n = 50. Why this step? Plug the maximising n into the loop formula: test runs $50 + 1 = 51$ , body runs 50. $WCET = A 4 + B 51 \times 1 + C 50 \times 3 + F 2 = 4 + 51 + 150 + 2 = 207 cycles$

Verify: $T (0) = 7 < WCET = 207$ , and the general formula $T (n) = 4 + (n + 1) + 3 n + 2 = 4 n + 7$ gives $T (0) = 7$ ✓ and $T (50) = 207$ ✓. Monotone increasing in $n$ , so max is at $n = 50$ . ✓ 207 cycles.

Example 4 — Cache: cold miss once, warm hits after (cell C4)

Look at the figure: it shows the same array being touched 8 times, and how the miss only strikes on the very first touch of each cache line.

Figure — WCET (Worst Case Execution Time) analysis

Figure — Cache line mapping for arr[0..7]. The 8 array cells are drawn left to right as boxes labelled arr[0] … arr[7]. They are grouped into two cache lines of 4: cache line 0 covers arr[0..3], cache line 1 covers arr[4..7] (blue double-arrows above each group). The first box of each line — arr[0] and arr[4] — is coloured red and marked "MISS 10 cyc", because touching it for the first time forces a fetch from slow memory that pulls the whole line in. The remaining six boxes — arr[1..3] and arr[5..7] — are coloured green and marked "hit 1 cyc", since the line is already resident. The yellow summary line reads: 2 misses + 6 hits → 20 + 6 = 26 memory cycles.

Forecast: 8 misses? 2 misses? Something in between?

Count the memory lines, not the accesses. Why this step? A miss loads a whole line into cache. arr[0] misses and drags arr[0..3] in; then arr[1], arr[2], arr[3] are hits. arr[4] misses (new line), and arr[5..7] hit. So misses = number of distinct lines = $8/4 = 2$ .
- Misses: 2 accesses × 10 cycles = 20.
- Hits: 6 accesses × 1 cycle = 6.
Add the plain per-iteration work. Why this step? The 2-cycle work happens on all 8 iterations regardless of cache. $memory = 20 + 6 = 26, work = 8 \times 2 = 16$ $WCET = 26 + 16 = 42 cycles$

Verify: Cross-check the two extreme (wrong) guesses. "All miss" = $8 \times 10 + 16 = 96$ (too pessimistic — a safe but loose bound). "All hit" = $8 \times 1 + 16 = 24$ (unsafe — ignores cold cache). Our 42 sits between, and matches the line-based "First-Miss" classification. ✓ 42 cycles.

Example 5 — Nested loops (cell C5)

Worked example Statement

for (int i = 0; i < 4; i++)        // B_out: test = 1
    for (int j = 0; j < 5; j++)    // B_in: test = 1
        work();                    // C: body = 3

Init blocks: outer init A_out = 1 (once), inner init A_in = 1 (once per outer iteration). WCET?

Forecast: the body runs 4×5 = 20 times — but how many times does each test run?

Body count = product of bounds. Why this step? The inner body runs inner times for each of the outer passes. $body executions = 4 \times 5 = 20 \Rightarrow cost = 20 \times 3 = 60$
Inner test and inner init counts. Why this step? For each outer pass the inner test runs $5 + 1 = 6$ times, and the inner init runs once. There are 4 outer passes.
- Inner tests: $4 \times 6 = 24$ → 24 cycles.
- Inner inits: $4 \times 1 = 4$ → 4 cycles.
Outer test and outer init. Why this step? Outer test runs $4 + 1 = 5$ times; outer init once.
- Outer tests: 5 cycles. Outer init: 1 cycle.
Sum everything. $WCET = A_{o u t} 1 + B_{o u t} 5 + A_{in} 4 + B_{in} 24 + C 60 = 94 cycles$

Verify: Body alone is 60; the loop scaffolding adds 34. Plausible — control overhead is a fraction of real work. ✓ 94 cycles.

Example 6 — Data-dependent bound + infeasible path (cell C6)

This is the case where the naive "worst branch every time" over-counts, because two expensive branches cannot both happen.

Worked example Statement

if (mode == FAST) {      // path P: 3 cycles
    quick();             // Q: 4 cycles
} else {                 // path R: 3 cycles
    slow();              // S: 40 cycles
}
log();                   // L: 5 cycles, always
 
if (mode == FAST) {      // second test, 3 cycles
    tidy();              // T: 30 cycles
} else {
    nop();               // N: 1 cycle
}

A static analyzer knows mode is the SAME in both ifs. WCET?

Forecast: naive answer adds the biggest branch of each if. Is that reachable?

Naive (wrong, loose) bound: pick the max of each if independently. Why this step? To expose the trap. First if max = slow() = $3 + 40 = 43$ . Second if max = tidy() = $3 + 30 = 33$ . Naive total $= 43 + 5 + 33 = 81$ .
Spot the infeasible path. Why this step? slow() runs only when mode != FAST. tidy() runs only when mode == FAST. They contradict — no single value of mode triggers both. The naive 81 counts an impossible route. This is exactly what flow constraints in the ILP forbid.
Evaluate the two real possibilities. Why this step? Only two feasible worlds exist; take the larger.
- mode == FAST: $quick 3 + 4 + L 5 + tidy 3 + 30 = 7 + 5 + 33 = 45$ .
- mode != FAST: $slow 3 + 40 + L 5 + nop 3 + 1 = 43 + 5 + 4 = 52$ . $WCET = max (45, 52) = 52 cycles$

Verify: True WCET 52 < naive 81. The naive bound is safe (never below reality) but loose; the infeasible-path constraint tightens it. ✓ 52 cycles.

Example 7 — Interrupt interference (cell C7)

Forecast: the interrupt fires a bounded number of times — how many, and does its time push the window longer, letting even more interrupts in?

Turn cycles into wall-clock time so the units make sense. Why this step? A "cycle" is a count; a deadline is a real time. The bridge is the clock rate: cycles per second. At 2 million cycles per second, one cycle lasts $1/ (2, 000, 000)$ second $= 0.5$ microseconds (µs), because 1 second = 1,000,000 µs so $1, 000, 000/2, 000, 000 = 0.5$ µs per cycle. $200 cycles \times 0.5 \frac{µs}{cycle} = 100 µs$ So the raw code occupies a 100 µs window — this is where the "100 µs" comes from; it is just 200 cycles measured in time.
Count max interrupt arrivals over the base window. Why this step? Interference is bounded by arrival rate. Over 200 cycles, at most one every 40 cycles → $⌈ 200/40 ⌉ = 5$ arrivals. (The ⌈ ⌉ brackets mean "round up to the next whole number" — you can't have a fraction of an interrupt.)
Add interference to your own WCET. Why this step? The parent's response-time formula is $R_{i} = C_{i} + I_{i}$ . Here $C_{i} = 200$ (your own code) and $I_{i} = 5 \times 30 = 150$ (interrupts). $R = C_{i} + I_{i} = 200 + 150 = 350 cycles$

Verify: Without interrupts, 200 cycles. Interference adds 150 — a 75% inflation, which is why interrupts are treated as a first-class term in response-time analysis, never ignored. And 200 cycles × 0.5 µs/cycle = 100 µs confirms the time conversion. ✓ 350 cycles (100 µs of raw code).

Example 8 — Word problem: does it meet the deadline? (cell C8)

Forecast: total worst-case response vs 500 µs — pass or fail?

Sum the interference from every higher-priority task. Why this step? Interference $I = \sum (cost per preemption \times max preemptions)$ across all tasks that can steal time. Interferer 1 contributes $60 \times 2 = 120$ µs; interferer 2 contributes $20 \times 1 = 20$ µs. $I = (60 \times 2) + (20 \times 1) = 120 + 20 = 140 µs$
Compute the response time. Why this step? Apply the parent's schedulability formula $R = C + I$ : your own worst-case work plus every cycle stolen from you. $R = C + I = 350 + 140 = 490 µs$
Compare the response time to the deadline. Why this step? A task is schedulable exactly when its worst-case response fits inside its deadline: $R \leq D$ . $R = 490 µs \leq D = 500 µs \Rightarrow schedulable.$

Verify: Slack $= D - R = 500 - 490 = 10$ µs $> 0$ , so it passes — but barely. If the WCET estimate were even 3% looser (about 15 µs) the response would exceed 500 µs and flip to a failure. This razor-thin margin is exactly why tight WCET matters in safety-critical systems: a life depends on the pacemaker firing before its deadline. ✓ R = 490 µs, PASS, 10 µs slack.

Example 9 — Exam twist: the average lies (cell C9)

The figure shows the shape of a measurement histogram: a tall clump near the mean and a long thin tail reaching the true worst case.

Figure — Histogram of 10,000 measured run-times (blue bars): the horizontal axis is execution time in cycles, the vertical axis is how many runs landed there. Most runs pile up around 250 cycles (the mean, green dashed line). To the right the bars thin into a long tail; a yellow arrow labels it "long thin tail = rare slow runs". Three more vertical markers climb rightward: the 99.9th percentile at 580 (yellow), the observed maximum at 612 (red), and finally the reported WCET at 662 (white), which sits to the right of every single bar — a safe upper bound must dominate all measurements.

Forecast: which of 250, 580, 612 do you build on?

Reject the mean. Why this step? The mean (250) is where the code usually lands. A deadline missed 0.1% of the time still kills a patient. WCET must bound the tail, so 250 is disqualified immediately.
Reject the 99.9th percentile too. Why this step? 580 is exceeded 1 run in 1000 — still a case that is guaranteed to be missed eventually. A safe bound must sit at or above every observed value, not 99.9% of them.
Build on the observed maximum, then pad it. Why this step? We only tested 10,000 of a near-infinite input space; the true worst case may be higher than anything we saw. The margin covers untested inputs and rare cache/pipeline events (Extreme Value Theory formalises this padding). $WCET_{report} = max + Δ = 612 + 50 = 662 cycles$

Verify: $662 > 612 > 580 > 250$ — the reported bound dominates every measurement, as a safe upper bound must. ✓ 662 cycles.

Recall

Recall WCET is an average of the branch costs. True or false?

False — it takes the longest branch every time, never an average. (Ex 2)

Recall A

for loop with body count N evaluates its test how many times? $N + 1$ ::: N times before each body plus one final failing test to exit. (Ex 1)

Recall 8 array reads, cache line = 4 elements, cold start — how many misses?

Distinct lines = 8/4 ::: 2 misses; the other 6 accesses hit. (Ex 4)

Recall Why can the naive "max branch of every if" over-count?

Some expensive branches are on infeasible paths ::: they contradict each other and can't all run in one execution. (Ex 6)

Recall Schedulability test in one line?

$R = C + I \leq D$ ::: worst-case response = own WCET + interference, must fit inside the deadline. (Ex 8)

Recall Why report observed-max + margin instead of the mean?

Mean is typical, not worst ::: a safe bound must sit above every observed value and pad for untested inputs. (Ex 9)