Timing, measurement and worst-case execution time

A timing requirement is only as good as the numbers used to check it. This lesson is about getting those numbers: how long code takes to run, how much that varies, and what the longest possible time is. The longest time is called the worst-case execution time, or WCET, and it is the single most important number in real-time analysis, because every schedulability test in lesson 5 starts from it. Getting it wrong in the optimistic direction means a system that passes every analysis and still misses deadlines in the field. Getting it badly wrong in the pessimistic direction means buying a processor three times larger than needed.

Execution time is not a fixed property of a piece of code. It depends on the input data, which branches are taken, the state of the caches and pipelines when the code starts, what other cores are doing to shared memory and buses, and whether interrupts arrive mid-way. A measurement taken on a quiet bench with warm caches is a best case, not a worst case. The skill is to measure under conditions that push execution time up and to understand which effects the measurement may have missed.

Three ways to bound execution time

There are three broad approaches, and serious projects often use more than one.

• Measurement-based: run the code many times under stress and record the maximum. This is cheap and realistic, but it only finds the worst case that happened to occur. Engineers add a safety factor, often 20 to 50 %, to cover cases not exercised.
• Static analysis: tools model the processor's pipeline and caches and analyze every path through the compiled code to compute a guaranteed upper bound. This gives a safe number, but it needs a detailed processor model, struggles with complex multicore chips, and can be pessimistic. It is common in aerospace and automotive certification.
• Hybrid: measure execution times of small code segments on the target, then combine them along the worst path found by analyzing the program structure. This reduces pessimism while keeping some of the safety of analysis.

Whatever the method, the result should be written down with its conditions: compiler version and optimization level, clock frequency, cache configuration, and the load present during measurement. A WCET without conditions cannot be reused when anything changes.

Measuring with a GPIO pin and an oscilloscope

The simplest and most trustworthy measurement uses a spare output pin. Set the pin high at the start of the code under test and low at the end, then watch it on an oscilloscope or logic analyzer. The pulse width is the execution time, the spacing between pulses is the actual period, and the oscilloscope's persistence or histogram mode accumulates thousands of cycles so that the longest pulse and the widest spacing stand out. Toggling a pin costs only a few processor cycles, so it disturbs the timing very little, and the measurement is made by independent hardware rather than by the software being measured.

/* Bracket the control step with a GPIO pin for oscilloscope timing */
void control_isr(void)
{
    GPIOB->BSRR = PIN_DEBUG;          /* pin high: start of step  */
    read_encoder();
    compute_control();
    write_pwm();
    GPIOB->BSRR = PIN_DEBUG << 16;    /* pin low: end of step     */
}

Two refinements help. Use separate pins for different tasks so their interaction is visible, for example a pin that goes high whenever an interrupt is running. And measure from the hardware event rather than from the start of the code: triggering the oscilloscope on the timer or sensor signal and measuring to the end of the output write captures the interrupt latency and wake-up time too, which is the latency the controller actually experiences.

Cycle counters and software timestamps

Most modern processors include a free-running cycle counter. On ARM Cortex-M3 and higher cores it is the DWT CYCCNT register in the debug unit; on x86 it is the time-stamp counter read by RDTSC; RISC-V defines a cycle CSR. Reading the counter before and after a block and subtracting gives its execution time in cycles, which divided by the clock frequency gives seconds. Software timestamps make it easy to collect statistics over millions of runs and to store a histogram on the target, but the measurement itself takes time and the code that records it can disturb caches. Keep the bookkeeping tiny: update a running maximum and a histogram bin, and send the results out slowly from a low-priority task.

/* Cortex-M: measure a function with the DWT cycle counter */
CoreDebug->DEMCR |= CoreDebug_DEMCR_TRCENA_Msk;   /* enable trace unit   */
DWT->CYCCNT = 0;
DWT->CTRL  |= DWT_CTRL_CYCCNTENA_Msk;             /* start counting      */

uint32_t t0 = DWT->CYCCNT;
compute_control();
uint32_t cycles = DWT->CYCCNT - t0;               /* wrap-safe subtract  */
if (cycles > max_cycles) max_cycles = cycles;      /* running maximum     */
hist[cycles >> 6]++;                               /* 64-cycle bins       */

Why execution time varies

Understanding the sources of variation helps an engineer design measurements that find the true worst case.

A useful distinction is between execution time, the processor time a job needs if it runs alone, and response time, the elapsed time from release to completion including time spent waiting for or preempted by other work. WCET is about the first; lesson 5 builds response time from it. Measurements made with a debug pin around the whole task capture response time unless interrupts are disabled, so label measurements carefully.

Statistics of execution time

Execution-time distributions are not normal. They usually have a sharp lower edge, a main hump and a long thin tail to the right, where the rare slow cases live. The mean and standard deviation say almost nothing about the tail, and the tail is what causes deadline misses. Report the maximum, high percentiles such as the 99.9th and 99.999th, and a histogram on a logarithmic count axis that makes the tail visible. The number of runs matters: a one-in-a-million slow path will not appear in a ten-thousand-run test. For a 1 kHz loop, one hour of operation is 3.6 million cycles, so a soak test of several hours is a minimum for a hard real-time task.

import random
random.seed(7)
# Synthetic execution times (us): a main hump plus a rare slow path
samples = []
for i in range(2_000_000):
    t = 60 + random.gammavariate(4, 3)           # typical path
    if random.random() < 2e-5:                    # rare cache-cold case
        t += random.uniform(40, 70)
    samples.append(t)
first = max(samples[:10000])
samples.sort()
n = len(samples)
def pct(p):
    return samples[min(n - 1, int(p / 100 * n))]
mean = sum(samples) / n
print("mean     %.1f us" % mean)
for p in (50, 99, 99.9, 99.999):
    print("p%-7s %.1f us" % (p, pct(p)))
print("max      %.1f us" % samples[-1])
print("first 10,000 samples only, max %.1f us" % first)

mean     72.0 us
p50      71.0 us
p99      90.2 us
p99.9    99.3 us
p99.999  126.1 us
max      146.4 us
first 10,000 samples only, max 110.7 us

The mean is 72 µs and the 99th percentile is 90 µs, but the maximum over two million runs is 146 µs, twice the mean. A ten-thousand-sample test tops out at about 111 µs: it sees the long tail of the normal path but none of the rare cache-cold cases. This is why a short bench test that 'never goes above 90 µs' is not evidence of a 90 µs WCET.

Tracing tools

Pins and counters time one thing at a time. Tracing tools record a timeline of everything: every task switch, interrupt entry and exit, lock acquisition and user-defined event, each with a timestamp. Hardware trace units such as ARM's Embedded Trace Macrocell stream instruction-level trace off the chip with almost no overhead. Software tracers built into operating systems record events into a memory buffer: FreeRTOS has trace hooks used by commercial and open-source viewers, Zephyr has a tracing subsystem, and Linux has ftrace, perf and the LTTng toolkit, with kernelshark and Trace Compass to view the results. ROS 2 has ros2_tracing, built on LTTng, which records callback start and end times so that end-to-end latency through a chain of nodes can be reconstructed.

A trace answers questions a single number cannot: which interrupt delayed the control task, which lower-priority task held a mutex, whether a periodic task drifted. The cost is data volume and some overhead, so traces are usually captured for short windows triggered by an anomaly, for example 'record continuously in a ring buffer and freeze it when the control task overruns'.

Measuring periods and jitter

Execution time is half the story; the other half is whether tasks start when they should. Measure the actual period by timestamping each release and taking differences. Release jitter is the spread of start times relative to the ideal schedule, usually reported as the maximum deviation or as the difference between the largest and smallest observed periods. A periodic task should be released by a hardware timer, not by a software loop that sleeps for a fixed time after finishing its work, because sleeping a fixed time after variable work makes the period drift by the execution-time variation every cycle. Lesson 4 shows the correct RTOS call for absolute-time periodic waits, and lesson 9 shows the Linux equivalent.

On Linux, the standard tool for measuring how late the system wakes a high-priority thread is cyclictest from the rt-tests package. It runs threads that sleep until absolute times and records how late they actually wake. Lesson 9 uses its histograms to compare a standard kernel with a real-time one.