Real-Time Systems
Worst-Case Execution Time
1996. Ariane 5, maiden flight. 37 seconds in - explosion. Cause: a 16-bit integer overflow in the inertial navigation software copied from Ariane 4. The code worked flawlessly for 10 years; Ariane 5 just flew faster. One worst-case scenario testing never covered. USD 500 million and decades of work, gone in 37 seconds. WCET analysis exists exactly so this scenario does not slip through.
- **Airbus:** every task in the Flight Control Computer undergoes formal WCET analysis via aiT; without this, the aircraft won't receive certification
- **Automotive (ISO 26262):** WCET analysis is mandatory for ASIL-D (highest safety level) - autopilots, ABS
- **SpaceX:** Falcon 9 uses Linux, but with careful profiling and margins for every task's timing
From Ariane 5 failure to industrial WCET standards
After the Ariane 5 disaster in 1996 and several other safety-critical incidents, the industry realized: testing provides no guarantees for hard RT. In 1999, Lunqvist and Stenstrom formally described timing anomalies - cache paradoxes that make simple component analysis incorrect. In the 2000s, industrial tools emerged: aiT (AbsInt, 2000), Bound-T, Chronos. DO-178C (2011) codified WCET analysis requirements for aviation. ISO 26262 (2011) - for automotive. Today, WCET analysis is a mandatory step in certifying any safety-critical system of class A/SIL-4.
Предварительные знания
What Is WCET
Schedulability analysis demands one answer: "what is the **maximum** time this task can take?" Not on average, not usually - the **absolute worst case**. That number is **WCET** (Worst-Case Execution Time) - an upper bound on a task's execution time for a given processor.
| Metric | Definition | How to obtain |
|---|---|---|
| BCET | Minimum execution time | Static analysis / measurement |
| Avg ET | Mean execution time | Profiling (useless for RT!) |
| HWMET | Highest observed execution time | Benchmark - lower bound of WCET |
| WCET | Upper bound (safe) | Static analysis - guaranteed >= actual |
**WCET hinges on input data and hardware state.** The same code finishes in 50 us (cache hot, branch predicted) or 500 us (cache cold, branch mispredicted, TLB miss). WCET is the max over ALL possible inputs and hardware states.
The measured maximum (HWMET) is **not WCET!** It is the lower bound of WCET. The real worst case can be far higher and surface once in a million runs - exactly when it matters most. Hard RT demands a guaranteed WCET, not "I ran it 1000 times and never saw worse".
A task ran 10,000 times. Maximum observed time: 150 us. Can 150 us be used as WCET?
Static WCET Analysis
**Static analysis** derives WCET without running the program. It dissects the code (which paths are reachable), the processor model (cycles per instruction), and memory state (cache, pipeline). The output: a **formally proven** upper bound.
| Analysis Component | What it does | Tool |
|---|---|---|
| Control Flow Analysis | Finds all execution paths, loop bounds | ILP, Abstract Interpretation |
| Cache Analysis | Predicts hit/miss for each access | Must/May analysis |
| Pipeline Analysis | Models processor pipeline stages | Microarchitectural model |
| IPET (Implicit Path Enumeration) | Finds worst-case path via ILP | Integer Linear Programming |
**aiT** (AbsInt) is the dominant industrial static WCET analysis tool. Used in aviation (Airbus), automotive (BMW, Daimler), and space (ESA). It models specific processors: ARM Cortex-M, PowerPC e500, LEON3. Output: "WCET of task X on processor Y <= 347 us" - a formal guarantee on paper.
Static analysis comes with a catch: it is **pessimistic**. WCET_analyzed >= WCET_real. The fancier the processor (out-of-order, speculative execution), the wider the gap. ARM Cortex-M sees ~10-20%; Intel x86 can stretch the gap to 5-10x.
Static analysis shows WCET = 500 us. All measurements show < 200 us. Is this a problem?
Measurement-Based Approach
Static analysis is expensive and finicky. The alternative is **measurement**: run the code many times across a range of inputs and time it. The output is HWMET (highest observed). The catch: no guarantee that the worst case was even seen. Pure measurement is a non-starter for hard RT.
| Approach | Guarantees | Cost | Application |
|---|---|---|---|
| Pure static analysis | Formal upper bound | Expensive (100K+ tool) | Aviation (DO-178C) |
| Pure measurement | No guarantees (only HWMET) | Cheap | Soft RT, prototypes |
| Hybrid (MBPTA) | Statistical guarantee | Medium | Automotive (ISO 26262) |
| Static + Measurement | Formal + validation | Maximum | Space (ESA, NASA) |
**MBPTA** (Measurement-Based Probabilistic Timing Analysis) splits the difference: measurements + extreme value theory (EVT). It extrapolates the tail to bound P(exec_time > T) < 10^-9. Used in ISO 26262 (automotive). Not a formal guarantee, but statistically defensible.
In real-world automotive RT, the answer is a hybrid: measurements for bulk estimation + static analysis for critical paths + safety margins. Pure formal analysis is reserved for the highest safety tiers (DAL-A in aviation).
For a soft RT system (video player), which approach to determining execution time is optimal?
Timing Anomalies in Modern Processors
Modern processors are loaded with optimizations that turn timing **unpredictable**: caches, pipelines, branch prediction, out-of-order execution, speculative execution. Each one is its own headache for WCET analysis.
| Optimization | Avg speedup | Problem for WCET |
|---|---|---|
| Cache (L1/L2/L3) | 10-100x | Miss: +100 ns; Hit: 1 ns. A 100x difference! |
| Branch Prediction | ~20% | Misprediction: +15 cycles; correct: 0 |
| Out-of-Order | ~30% | Timing depends on instruction order of neighboring tasks |
| Speculative Execution | ~10% | Speculation + rollback = unpredictable timing |
| TLB (Translation Lookaside Buffer) | ~20% | TLB miss: +100 ns each |
**Timing anomalies** are the paradoxes where speeding up one piece of a program drags the whole program down. Lunqvist and Stenstrom first described them in 1999. They wreck **component analysis** (WCET = sum of worst-case per instruction). Whole-system analysis is the only way out.
That is why critical RT systems run on **simple processors**: ARM Cortex-M (in-order, no cache) instead of Intel i7 (out-of-order, three cache levels, speculative). A simple processor is slower, but **analyzable**. Execution time stays predictable.
Watch the **WCET-aware hardware** trend: processors built for predictable timing. The PRET (PRecision-Timed) architecture nails fixed latency per instruction. Scratchpad memory replaces cache (the programmer decides what sits in fast memory). Still in the research phase, but autonomous systems are pulling it toward production.
The highest observed execution time equals WCET
The observed maximum (HWMET) is only a lower bound of WCET. The real WCET can be significantly higher and appear in scenarios not covered by tests.
Testing cannot cover ALL combinations: input data * cache state * pipeline state * interrupt timing * branch prediction history. HWMET from 10^6 runs may miss a scenario that occurs once in 10^9 - and that single occurrence will violate the deadline of a hard RT system. Formal static analysis examines ALL possible paths and states, guaranteeing a safe upper bound.
On a cached processor: BCET = 10 us, WCET = 200 us. WCET/BCET ratio = 20x. What does this mean?
Key Ideas
- **WCET** is the execution time upper bound; HWMET (observed maximum) is only a lower bound of WCET
- **Static analysis** gives a formally proven WCET, but pessimistic; requires a processor model
- **Measurement** is cheaper but provides no guarantees; MBPTA gives statistical guarantees
- **Timing anomalies** (cache, pipeline, speculation) create 5-20x spread; simple processors are more predictable
Related Topics
WCET is the bridge between hardware and RT scheduling:
- Scheduling: Rate Monotonic — WCET is the input parameter for schedulability analysis
- What Are RT Systems — WCET determines which deadlines are achievable
- Computer Architecture — Cache, pipeline, branch prediction are the sources of timing unpredictability
Вопросы для размышления
- Why is cache simultaneously a great invention for performance and a nightmare for RT systems?
- If static analysis gives WCET = 500 us but measurements max out at 100 us, is it worth 'compressing' the WCET? What are the risks?
- Back to the beginning: how does an Airbus engineer prove WCET for a program running on a processor with cache and branch prediction?
Связанные уроки
- rts-02 — Rate Monotonic schedulability uses WCET as its input parameter
- rts-01 — Hard/soft RT concepts determine the required strictness of WCET analysis
- ca-01 — Cache, pipeline, branch prediction are the sources of timing unpredictability
- par-01 — Parallel tasks and timing interference are a related problem
- alg-02-space