WCET (Worst Case Execution Time) analysis: Foundations

This page assumes you know nothing. Before you can read the parent note, you must be able to read every symbol it throws at you without flinching. So we build each one from a picture. Read top to bottom — each idea is a rung on a ladder that leans on the one below it.

1. What is "execution time"? (cycles)

Before any subscript or sum, we need the raw material: how do we even measure how long code takes?

Picture a metronome clicking. Every click, the CPU may finish a tiny piece of work. If a job takes 12,994 clicks, we say it takes 12,994 cycles.

Figure — WCET (Worst Case Execution Time) analysis

Why we need this: every number in WCET analysis — 5 cycles, 100 cycles, 12,994 cycles — is counted in these ticks. It is the "inch" of our ruler. Prerequisites live in Compiler Optimizations and Cache Memory Architecture, but at heart a cycle is just one tick.

2. What is a "task"? And its subscript $i$

The parent writes $R_{i}$ , $C_{i}$ , $I_{i}$ , $D_{i}$ . That little $i$ scares people. It shouldn't.

Picture a numbered to-do list. $D_{3}$ = "the deadline written next to item 3". That's all a subscript is: an address label.

Why we need this: the scheduling formula talks about one task at a time. The subscript lets us write one formula that works for every task instead of copying it out for each.

3. Deadline $D_{i}$ — the finish line

Picture a running track. The gun fires at cycle 0; the finish line is painted at $D_{i}$ . Cross it late → you failed, and in a safety-critical system "failed" can mean a crash.

Why we need this: WCET only matters relative to something. A task taking 12,994 cycles is fine if its deadline is 20,000 and a catastrophe if its deadline is 10,000. The deadline is the goalpost.

4. Worst-case execution time $C_{i}$ — the star of the show

Now the main character. Notice the parent uses $C_{i}$ and the word WCET for the same thing.

Look at the figure: many measured runs cluster low (the histogram), but WCET is the far-right wall — the value nothing can exceed. That wall is $C_{i}$ .

Two words you must keep straight (the parent stresses both):

Think of a ceiling: safe means the ceiling is above your head (you never bump it); tight means it isn't uselessly 40 metres up.

5. Interference $I_{i}$ — being pushed aside

Picture a queue at a counter where VIPs keep cutting in line. Your own service takes $C_{i}$ , but the VIPs cutting in cost you $I_{i}$ of waiting. This waiting comes from scheduling and from interrupts.

Why we need this: you don't run in a vacuum. Meeting a deadline depends on your work plus the delays others impose.

6. Response time $R_{i}$ and the schedulability formula

Now every piece clicks into the parent's key equation:

$R_{i}$ — response time: the real moment task $i$ crosses the finish line.
The $\le$ symbol means less-than-or-equal: "at or before". At exactly the deadline is still a pass.

The figure stacks the two blocks — waiting ( $I_{i}$ ) then working ( $C_{i}$ ) — and shows whether the total reaches the deadline line. If the bar ends left of the line: schedulable. If it pokes past: fails.

Why this is the whole point: the entire subject exists to feed a trustworthy $C_{i}$ into this inequality. Garbage $C_{i}$ → garbage guarantee.

7. The summation symbol $\sum$ — "add up a list"

The parent's WCET decomposition uses $\sum$ . This is not scary either.

Picture a cash register totalling receipts one by one. That's a $\sum$ .

Why we need this: a program's time is the total of many small blocks' times. Writing $5 + 3 + 4 + 6 + \dots$ for hundreds of blocks is madness; $\sum$ says "add every block's time" in one clean symbol.

8. Block, path, and $max$ over paths

This is exactly the parent's decomposition, now readable: $WCET = max_{path} (\sum_{blocks in path} T_{block})$ "For each path, add up its blocks' times; then keep the biggest path total." The Control Flow Graph (CFG) is the map of all these paths; Static Program Analysis is how we search them.

9. Reading the example's arithmetic

The parent computes, for find_max with loop body 3+4+6 cycles: $WCET = 5 + (n - 1) \times (3 + 4 + 6) + 2 = 13 n - 6$

Decoded with everything above:

5 and 2: blocks A and E, each run once (entry/exit — the boundary cases).
(n-1): the loop runs from i=1 to i<n, i.e. $n - 1$ times — a loop bound the analyzer must be told.
(3+4+6): the worst path through the loop — the if taken every time, block D a cache miss (worst hardware mood).

How it all feeds the topic

Read it upward from the top: cycles build block times, block times build paths, the biggest path is the WCET, and the WCET plugs into the deadline test that is the reason the whole subject exists.

Equipment checklist

Cover the right side. If you can answer each, you're ready for the parent note.

What is a clock cycle?

One tick of the CPU's clock — the smallest unit of time we count code in.

What does the subscript

i

C_{i}

mean?

"of task number

i

" — a label pointing at one particular task.

What is

D_{i}

The deadline of task

i

— the moment by which it must finish.

Define

C_{i}

(WCET) in one sentence.

The longest time task

i

could ever take to run on its own, over all inputs and hardware states.

What's the difference between "safe" and "tight"?

Safe = never below the true worst; tight = not needlessly far above it.

What is interference

I_{i}

Extra waiting forced on task

i

by higher-priority tasks cutting ahead.

State the schedulability test and read it in words.

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

— own work plus waiting must land at or before the deadline.

What does

\sum

tell you to do?

Go through a list and add every item up.

What does

max_{path}

mean?

Among all possible routes through the code, keep the one with the largest total time.

Why worst-case and not average time?

Averages hide rare slow runs that will eventually happen and can cause a deadline miss.

In for(i=1;i<n;i++), how many iterations run?

n - 1

, not

n

— mind the off-by-one.