Worst-case execution time, or WCET, is a provable upper bound on the time a task can take to execute. It is not the average running time or even the slowest time anyone has happened to observe; it is a bound that the task is guaranteed never to exceed, across all possible inputs and execution conditions. WCET is the input that turns scheduling theory into a guarantee: a real-time scheduler can only prove that every deadline will be met if it knows, for each task, the longest the task could ever take. Without a sound WCET, a claim that a hard real-time system meets its deadlines is unsupported.
The authoritative survey of the field is Reinhard Wilhelm and colleagues’ “The Worst-Case Execution-Time Problem — Overview of Methods and Survey of Tools,” published in ACM Transactions on Embedded Computing Systems in 2008. The paper opens by stating that “the determination of upper bounds on execution times, commonly called worst-case execution times (WCETs), is a necessary step in the development and validation process for hard real-time systems.” It catalogs the methods and the commercial and research tools that compute these bounds.
The two broad strategies are measurement and static analysis. Measurement-based methods run the program, or fragments of it, on the real hardware or a cycle-accurate simulator and record execution times, then combine those measurements into an end-to-end estimate. The danger is coverage: if the slowest possible execution path or hardware state was never exercised, the measured maximum underestimates the true worst case, which is unsafe for a hard deadline. Static analysis, by contrast, computes a bound from the program and a model of the processor without running it, reasoning about every path so that the result is a guaranteed upper bound — at the cost of possible pessimism, where the proven bound exceeds any time that can actually occur.
The difficulty of the problem comes from modern processors. The survey emphasizes that bounding execution time is hard when the hardware has “caches, pipelines, branch prediction, and other speculative components,” because these make an instruction’s timing depend on the history of execution rather than on the instruction in isolation. A cache hit and a cache miss for the same memory access can differ by orders of magnitude, so a sound analysis must account for the architectural state, not just the instruction stream. The paper describes the structure-based, path-based, and implicit path enumeration (IPET) techniques developed to combine local timing information into a whole-program bound.
WCET sits at the foundation of real-time engineering: scheduling analyses such as rate-monotonic schedulability tests consume WCET values as their basic inputs, and the soundness of any deadline guarantee is only as good as the soundness of those numbers. This is why, in safety-critical embedded systems, computing a trustworthy WCET is treated not as an optimization but as a required step in certification.