worst-case execution time (WCET)
/ DUB-yoo-set /
If you must guarantee you can drive across town in time for an appointment, you do not plan around your luckiest run with every light green — you plan around the worst plausible traffic. For a piece of code that must meet a deadline, the equivalent question is: across ALL possible inputs and conditions, what is the LONGEST this function could ever take to run? That upper bound is the worst-case execution time, or WCET.
WCET is the maximum time a task or code block can take to execute on a specific processor, over every reachable input, path, and hardware state. It is the key ingredient that real-time scheduling analysis (rate-monotonic, EDF, response-time analysis) feeds on — those methods need each task's Ci, its worst-case time, to prove deadlines are met. Estimating WCET is genuinely hard because two things multiply the possibilities. First, the SOFTWARE: different inputs take different paths, loops may iterate a data-dependent number of times (so you need known upper bounds on every loop), and recursion must terminate within a bound. Second, the HARDWARE: modern processors make timing data-dependent through caches (a cache miss is far slower than a hit), branch prediction, pipelines, and out-of-order execution, so the SAME instruction can take wildly different times depending on history. There are two broad approaches: measurement-based (run many times and observe the maximum, which can MISS the true worst case) and static analysis (analyze the code and a model of the processor to derive a guaranteed upper bound, which tends to be safe but pessimistic). A safe WCET bound must be an over-estimate, never an under-estimate, or the guarantee is worthless.
It matters because without a trustworthy WCET you cannot honestly claim a hard real-time system will meet its deadlines — the whole schedulability analysis rests on it. The honest, important cautions: a purely measurement-based WCET is NOT a guarantee, because you may simply never have hit the worst-case path or cache state in testing; a 'segmentation fault never happened in our tests' style of reasoning is exactly the trap. Caches and speculative hardware that make average-case code FAST also make WCET harder to bound and more pessimistic, which is why deeply safety-critical systems sometimes disable caches or pick simpler, more predictable processors. And WCET is per-processor: the same code has a different WCET on a different chip or clock speed.
// WCET depends on inputs AND hardware history: int search(const int *a, int n, int key) { for (int i = 0; i < n; i++) // loop bound n must be KNOWN if (a[i] == key) return i; // best case: hit at i=0 return -1; // worst case: scan all n elements } // WCET ~ n iterations, EACH possibly a cache MISS -> bound is // (n * worst-case-iteration-time), not the fast measured average.
WCET assumes the longest path and the worst cache behavior, not the average measured run — every loop needs a known iteration bound.
Measurement-based WCET is not a guarantee: testing may never hit the true worst-case path or cache state. A safe bound must over-estimate, and caches/speculation that speed the average case make the worst case harder to bound.