Response-Time Analysis for Fixed-Priority Task Sets

The utilisation bound answers “is this set schedulable” for a narrow set of assumptions and gives a yes or a maybe. Response-time analysis answers the more useful question: what is the longest this task can take from release to completion, given everything that can interfere with it. The answer is a number that can be compared against the deadline and, when it is too large, decomposed into the tasks responsible so that the design can be changed.

The critical instant and what makes it critical

The analysis rests on one claim: a task’s worst case occurs when it is released at the same instant as all higher-priority tasks, and all of those tasks have been released periodically ever since. That instant is called the critical instant. If a task is released at the same moment as every higher-priority task, it waits for all of them to complete their first jobs, and then for each subsequent release of each of them that falls before its own completion.

The reasoning behind the critical instant is that any release offset that staggers the higher-priority tasks can only reduce the interference in that window, because staggering moves work out of the window rather than into it. The claim holds for tasks that are independent, periodic, and whose releases are not synchronised in some favourable way; for a set with a common release, the critical instant is exactly the synchronous release.

The pessimism begins here. Sporadic events with a minimum interarrival time are analysed as if they arrive at their minimum rate forever, which is a valid bound but often loose. Event streams with bursty arrival — a CAN bus that delivers a cluster of frames and then goes quiet — can violate the minimum interarrival time in ways the standard model does not capture, and the analysis then understates the interference rather than overstating it. Knowing which direction the model errs is the point of using it.

The recurrence

For task i, let $C_i$ be its worst-case execution time, $T_i$ its period or minimum interarrival time, and $D_i$ its deadline. Its response time $R_i$ satisfies:

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

where $hp(i)$ is the set of tasks with priority higher than i and $B_i$ is the blocking term contributed by lower-priority tasks that hold a resource i needs. The equation is implicit in $R_i$ on both sides, which is why it is solved iteratively: start with $R_i = C_i + B_i$, compute the right-hand side, and repeat until the value stops changing. The sequence is monotone non-decreasing and bounded above by $D_i$ or by a divergence, so it terminates after at most $D_i / \min(T_j)$ steps; in practice a handful.

from math import ceil

def response_time(i, tasks, blocking):
    """tasks sorted by descending priority; index i is the task of interest.
    Returns R, or None if it exceeds the deadline."""
    hp = tasks[:i]                       # only higher-priority tasks count
    R = tasks[i]['C'] + blocking[i]
    while True:
        interference = sum(ceil(R / t['T']) * t['C'] for t in hp)
        new_R = tasks[i]['C'] + blocking[i] + interference
        if new_R == R:
            break
        if new_R > tasks[i]['D']:
            return None                  # deadline already exceeded
        R = new_R
    return R

The ceiling function is the whole difficulty. Each higher-priority task contributes a whole job for every period that starts before $R$; a job that begins one tick before completion still contributes its full execution time to the window, even though only a fraction of it runs inside. This is the source of most of the analysis’s pessimism, and the reason the computed response time can exceed the measured one by a wide margin when periods are not harmonic.

The convergence test new_R == R is correct because the sequence is exact when it repeats: a fixed point of the recurrence is the answer. Floating-point arithmetic can make the test oscillate, so implementations keep integer time units or compare against a small tolerance.

The blocking term

$B_i$ is the longest time task i can be blocked by a lower-priority task, and it comes from the locking discipline rather than from execution times; priority inversion and blocking time is where the protocols that bound it are compared. Under priority inheritance without ceilings, a task can be blocked by each lower-priority task that holds a resource it needs, and the chain of blocking can extend through nested locks; under the priority ceiling protocol, the bound is the longest critical section among the lower-priority tasks whose ceiling is at least i’s priority.

Getting this term wrong is more common than getting the interference wrong, because the lock set is not visible in the timing data. A driver that takes a mutex inside a long conversion routine, called from a low-priority task, contributes that routine’s duration to every task above the ceiling. Auditing the lock set against the critical-section durations is a separate exercise from measuring execution times, and it should be redone whenever a lock is added.

Interrupt handlers contribute a fixed term that is the same for every task: the handler’s own execution plus the kernel’s interrupt entry and exit. On a system where handlers do not take locks, the term is simply the total handler time in the worst nesting configuration, and it can be measured by instrumenting the entry and exit points. On a system where handlers take locks, the analysis becomes considerably harder, and the usual answer is to move the work into a task.

Reading the result

The output is a table: for each task, the computed response time, the deadline, and the slack. Three patterns in that table drive design changes.

A response time just below the deadline means the set is technically schedulable with no margin, and any error in the execution times or jitter in the releases will break it. The margin has to absorb the gap between the analysis’s model and the target’s actual behaviour — cache effects, interrupt handler interference, clock tolerance — so its size is a property of the platform rather than a fixed percentage.

One task dominating the slack usually indicates that its intervention rate is the problem: its period is shorter than its work justifies. Merging two related tasks, or moving part of the work to a lower priority, often fixes a set that looks uniformly tight.

A response time that exceeds the deadline for a low-priority task while the high-priority ones are comfortable is a sign of an unbalanced priority assignment or of a task that should be split. Splitting a long task into a short hard part and a deferred soft part is the standard technique for keeping the hard part inside a tight deadline without moving the whole job up in priority. The general framework for choosing the split is covered in deferred interrupt work and task partitioning, which trades latency against load.

What the analysis cannot see

The recurrence assumes that the kernel itself is free. Every kernel operation, from the tick handler to the ready-list update, takes cycles that the analysis does not attribute to any task. The standard practice is to add the kernel overhead to each task’s execution time, or to add a fixed term per release and per block, and the values come from measurement of the kernel’s own paths, not from its documentation.

The analysis also assumes that a task cannot be delayed by another task’s memory accesses. On a core with caches and a memory bus shared with DMA or with a second core, a task’s execution time depends on what else is running. The measured worst-case execution time must include the interference from those sources, or the analysis is measuring a different system than the one that ships. This is why worst-case execution time analysis on modern parts is a research problem rather than a stopwatch exercise.

Preemption also costs cycles beyond the task’s own execution. Each preemption saves and restores the register file, and each restore may miss in the instruction cache. A set with many short tasks at high priority can spend a noticeable fraction of the processor in switch overhead, and the analysis of a set with a preemption every 50 microseconds should include that cost explicitly.

Finally, the analysis is per configuration. A mode change that alters periods or execution times, an over-the-air update that changes code, or a change to a shared library all invalidate the table. Keeping the analysis as an artefact that lives with the code, and re-running it when the code changes, is the difference between a schedule that is known to be safe and one that was safe at the time of the last review.