Deadlines, Execution Budgets, and Timing Analysis

Real-time analysis describes each periodic task $i$ by three numbers:

• $C_i$, its worst-case execution time (WCET): the longest it can run for one activation, without being interrupted;
• $T_i$, its period (or minimum time between activations, for sporadic tasks such as a button handler);
• $D_i$, its relative deadline: how soon after activation it must finish. Often $D_i = T_i$.

Its utilisation is the fraction of the CPU it needs, and the total over all tasks is

$$U = \sum_i \frac{C_i}{T_i}$$

If $U > 1$, no scheduler can meet every deadline on one CPU: there is more work than time. $U \le 1$ is necessary but, for fixed priorities, not sufficient.

Every number in the analysis rests on $C_i$. Measure it as unit 6, lesson 6 showed: a GPIO toggled at the start and end of the task’s work and a logic analyser, or a cycle counter read before and after. Record the maximum over long runs with realistic inputs, not the average. FreeRTOS can also accumulate each task’s run time when given a counter at least ten times faster than the tick; its report disables interrupts while it runs, so it is a debugging aid, not something to call from a task with a deadline.

A measured maximum is a lower bound on the true worst case, not a proof; a proven bound needs static or hybrid WCET analysis of the code on the actual hardware. Code paths that the tests never took, flash wait states and cache misses (unit 3, lesson 6), interrupts that happened to be quiet and bus contention from DMA all make the real worst case longer. Add a margin, and turn each $C_i$ into a budget: a number the design promises, which testing then checks is never exceeded. Treat interrupt handlers as the most urgent tasks of all, with their own $C$ and minimum inter-arrival time: they preempt every task.

For fixed priorities, the worst case happens when a task is released at the same moment as every more urgent task. Its worst response time $R_i$ is its own execution, plus the longest time a less urgent task can block it through a shared lock (lesson 5), plus every execution of each more urgent task $j$ that is released within the window:

$$R_i = C_i + B_i + \sum_{j \in hp(i)} \left\lceil \frac{R_i}{T_j} \right\rceil C_j$$

$R_i$ appears on both sides, so it is found by iteration: start from $R_i = C_i + B_i + \sum C_j$, evaluate the right-hand side, and repeat until the value stops changing (the task meets its deadline if $R_i \le D_i$) or exceeds $D_i$ (it does not).

↑ This step uses the figure at the top of the page.

The analysis gives a verdict for every task, including those above the utilisation bound, and it shows where the time goes: which higher-priority task preempts how often, and how much a critical section costs everyone above it. Interrupts enter as the highest-priority terms of the sum, and the blocking $B_i$ is where the locking protocol matters: under a priority ceiling it is the longest single lower-priority critical section, under inheritance it can be the sum of several, and without inheritance, a ceiling or non-preemptive critical sections it must include all medium-priority work. The analysis assumes deadlines no longer than periods, independent tasks apart from $B_i$, no release jitter, and context-switch overhead folded into each $C$; it is exact without blocking and a safe (sufficient) test with it.

Analysis rests on budgets; the running system should check them. A periodic FreeRTOS task written with xTaskDelayUntil() gets an overrun detector for free: the function returns pdFALSE when the next wake time is already due (at or before the current tick), that is, when the activation finished after its next release. The measure is tick-granular and includes preemption, and after a long overrun the following calls also return pdFALSE while the task catches up, so record the maximum execution time separately with a cycle counter.

TickType_t last = xTaskGetTickCount();
for (;;) {
    control_step();
    if (xTaskDelayUntil(&last, pdMS_TO_TICKS(10)) == pdFALSE)
        overruns++;                    /* this activation finished after its next release */
}

Count overruns, log the longest execution time seen, and check stack high-water marks (uxTaskGetStackHighWaterMark()) in long tests. What the system does when a budget is exceeded, from a watchdog reset to a safe state, is the subject of unit 14.

Three tasks, most urgent first: τ1 needs 1 ms every 5 ms, τ2 2 ms every 8 ms, τ3 10 ms every 20 ms, with $D = T$ and no blocking. The utilisation is

$$U = \frac{1}{5} + \frac{2}{8} + \frac{10}{20} = 0.95 > 3\left(2^{1/3} - 1\right) = 0.780$$

so the quick test is inconclusive. Response-time analysis for τ3 starts from $10 + 1 + 2 = 13$:

$$R = 10 + \left\lceil \tfrac{13}{5} \right\rceil 1 + \left\lceil \tfrac{13}{8} \right\rceil 2 = 10 + 3 + 4 = 17$$ $$R = 10 + \left\lceil \tfrac{17}{5} \right\rceil 1 + \left\lceil \tfrac{17}{8} \right\rceil 2 = 10 + 4 + 6 = 20$$ $$R = 10 + \left\lceil \tfrac{20}{5} \right\rceil 1 + \left\lceil \tfrac{20}{8} \right\rceil 2 = 10 + 4 + 6 = 20$$

It converges at exactly 20 ms: τ3 meets its deadline with no margin at all. τ1 responds in 1 ms and τ2 in 2 + ⌈3/5⌉·1 = 3 ms. A simulation of the synchronous release gives the same 20 ms. With 11 ms for τ3 ($U = 1.0$), the iteration goes 14, 18, 21 and passes the deadline. If τ3 held a lock for up to 4 ms that τ1 and τ2 also need, their responses would become 1 + 4 = 5 ms and 2 + 4 + 2·1 = 8 ms, exactly their deadlines: the whole margin is gone.