Response-Time Analysis: A Step-by-Step Worked Example

Utilization bounds tell you quickly whether a task set is certainly schedulable, but they cannot tell you how close to the edge you are, and they often give up on perfectly good designs. Response-time analysis (RTA) answers a more useful question: what is the longest time each task can take from release to completion, under the worst possible combination of interference? If that worst-case response time is within the deadline for every task, the system is schedulable. If not, you know exactly which task fails and by how much.

This article walks through RTA for fixed-priority preemptive scheduling with a fully computed example, showing every iteration. It then extends the analysis to blocking and release jitter, shows how to do a quick sensitivity analysis, and ends with code you can reuse. For background on priority assignment, see our comparison of Rate Monotonic and EDF.

The model and the core idea

We assume a single processor with fully preemptive fixed-priority scheduling. Each task τi has a worst-case execution time Ci, a period or minimum inter-arrival time Ti and a relative deadline Di ≤ Ti. Tasks have unique priorities, and hp(i) denotes the set of tasks with higher priority than τi. Initially we also assume tasks are independent (no shared locks) and released without jitter. Definitions of all terms are collected in our glossary.

The critical instant

Liu and Layland showed that, under these assumptions, the worst-case response time of a task occurs when it is released at the same instant as all higher-priority tasks, and those tasks then recur as quickly as allowed. This critical instant maximizes the interference the task suffers. RTA therefore only needs to analyze one scenario per task rather than every possible phasing.

The recurrence

Within a window of length R starting at the critical instant, each higher-priority task τj is released ⌈R/Tj⌉ times and each release can consume up to Cj of processor time. The response time of τi must therefore satisfy

Ri = Ci + Σ_{j ∈ hp(i)} ⌈Ri / Tj⌉ · Cj

This equation, introduced by Joseph and Pandya (1986) and developed by Audsley, Burns, Tindell and colleagues at the University of York, has Ri on both sides. Because the right-hand side is a non-decreasing step function of Ri, the smallest solution can be found by iteration:

1. Start with Ri(0) = Ci (or the sum of Ci and all higher-priority Cj, which converges faster).
2. Compute Ri(k+1) = Ci + Σ ⌈Ri(k)/Tj⌉ Cj.
3. If Ri(k+1) = Ri(k), stop: this is the worst-case response time.
4. If Ri(k+1) > Di, stop: the task can miss its deadline.

The sequence is monotonically non-decreasing, so it always terminates at one of the two stopping conditions.

The example task set

Consider four periodic tasks with implicit deadlines, prioritized Rate Monotonic (shorter period, higher priority). Times are in milliseconds.

First, the quick tests. The Liu and Layland bound for four tasks is 4(2^(1/4) − 1) ≈ 0.757, well below 0.958. The hyperbolic bound gives 1.25 × 1.333 × 1.25 × 1.125 ≈ 2.34 > 2. Both are inconclusive, and the periods are not fully harmonic (4 does not divide 6). We need RTA.

Computing the response times step by step

τ1: highest priority

τ1 has no higher-priority tasks, so R1 = C1 = 1. Since 1 ≤ 4, τ1 is schedulable.

τ2: interference from τ1

R2 = 3 ≤ 6: schedulable.

τ3: interference from τ1 and τ2

R3 = 10 ≤ 12: schedulable, with 2 ms of slack. Each iteration discovers that the window has grown enough to include another release of a higher-priority task: at R = 6 a second job of τ1 (released at 4) fits in, at R = 7 a second job of τ2 (released at 6), and at R = 9 a third job of τ1 (released at 8).

τ4: interference from all other tasks

R4 = 23 ≤ 24: schedulable, with only 1 ms of slack. The whole task set is therefore schedulable at 95.8% utilization, far above the 75.7% the utilization bound could guarantee.

Sensitivity analysis: how much margin is there?

A single yes/no answer is rarely enough. Engineers want to know how much a WCET can grow before the system breaks. Re-running the analysis while increasing C4:

The breakdown point for τ4 is C4 = 4. Interestingly, the set remains schedulable at exactly 100% utilization even though the periods are not all harmonic; this is a property of these particular numbers, not something to rely on in general. In practice you would never accept zero slack, because WCET estimates, overheads and future changes all consume margin.

Extending the analysis: blocking and jitter

Real tasks share resources and are not always released precisely on time. The standard extended recurrence (Audsley et al., 1993; Tindell, Burns and Wellings, 1994) is

wi = Ci + Bi + Σ_{j ∈ hp(i)} ⌈(wi + Jj) / Tj⌉ · Cj
Ri = wi + Ji

where Bi is the maximum blocking from lower-priority tasks and Jj is the release jitter of each higher-priority task. Jitter increases interference because two releases of τj can be squeezed closer together than Tj.

Adding blocking

Suppose τ3 and τ4 share a data buffer protected by a mutex using the priority ceiling protocol, and τ4 holds it for at most 1 ms. The ceiling of the mutex equals τ3’s priority, so only τ3 can be blocked by τ4, at most once per job: B3 = 1. Tasks τ1 and τ2 never touch the mutex and are unaffected. Without a ceiling or inheritance protocol, blocking could be unbounded; see priority inversion and the priority ceiling protocol.

R3 = 11 ≤ 12: still schedulable.

Adding release jitter

Now remove the blocking and instead assume τ2 is triggered by a polled sensor, giving it release jitter J2 = 3. For τ3, the τ2 term becomes ⌈(w + 3)/6⌉ · 2.

R3 = 12 ≤ 12: schedulable with zero slack. τ2 itself now has R2 = w2 + J2 = 3 + 3 = 6 ≤ 6, also exactly at its deadline.

Combining both effects

With both B3 = 1 and J2 = 3, the iteration for τ3 runs 4, 9, 11, 13. At 13 it exceeds D3 = 12: τ3 can miss its deadline. Neither effect alone breaks the system, but together they do. This is precisely why piecemeal reasoning (“the jitter is small, the critical section is short”) is dangerous and why the full analysis must be repeated after every design change.

Reusable implementation

The following Python function implements the extended recurrence. Tasks are listed in priority order, highest first.

import math

def response_times(tasks):
    """tasks: list of dicts with C, T, D, and optional B, J (priority order)."""
    results = []
    for i, t in enumerate(tasks):
        B, J = t.get("B", 0), t.get("J", 0)
        w = t["C"] + B
        while True:
            w_next = t["C"] + B + sum(
                math.ceil((w + h.get("J", 0)) / h["T"]) * h["C"]
                for h in tasks[:i])
            if w_next + J > t["D"]:
                results.append(None)        # deadline miss
                break
            if w_next == w:
                results.append(w + J)       # worst-case response time
                break
            w = w_next
    return results

tasks = [dict(C=1, T=4, D=4), dict(C=2, T=6, D=6),
         dict(C=3, T=12, D=12), dict(C=3, T=24, D=24)]
print(response_times(tasks))                # [1, 3, 10, 23]

Assumptions, limits and next steps

• Constrained deadlines only. If Di > Ti, several jobs of the same task can be pending, and the worst case is not necessarily the first job. Use the busy-period extension (Lehoczky, 1990; Tindell et al., 1994), which checks every job in the level-i busy period.
• WCET quality. An optimistic Ci invalidates the result; a grossly pessimistic one wastes hardware. See WCET analysis methods.
• Uniprocessor. On multicore hardware, partitioned scheduling allows per-core RTA, but global scheduling needs different tests, discussed in multicore real-time scheduling.
• Distributed systems. Holistic analysis chains task and message response times across nodes, with the jitter of each stage feeding the next; the same idea underlies CAN bus analysis covered in real-time networking.

If you would like a second pair of eyes on a production task set, including overheads and blocking, our real-time schedulability audit delivers a documented analysis.

Frequently asked questions

Why does response-time analysis use the ceiling function?

A higher-priority task released anywhere inside the window, even at its last instant, can execute its full WCET within the window in the worst case. Counting partial periods as full releases with ⌈R/T⌉ captures this.

Is response-time analysis exact or only sufficient?

For independent, fully preemptive tasks with constrained deadlines on one processor, it is exact: a task set passes if and only if it is schedulable. With blocking, jitter and overheads it is generally sufficient, because the worst-case terms may not all occur together.

Which starting value should I use for the iteration?

Any value not larger than the true response time works. Ci is the simplest. Starting from Ci plus the sum of all higher-priority Cj is also safe and usually converges in fewer steps.

Does RTA work for EDF scheduling?

Not in this form. EDF response times depend on absolute deadlines and require a different analysis (Spuri’s method). For EDF schedulability, the processor demand criterion is normally used instead.

What if the iteration never converges?

It always terminates if you stop when the value exceeds the deadline. If total utilization is at least 1 and you did not bound the iteration, the value can grow without limit, so always include that stopping condition.

References and further reading

1. Joseph, M. and Pandya, P. (1986). “Finding Response Times in a Real-Time System.” The Computer Journal, 29(5).
2. Audsley, N., Burns, A., Richardson, M., Tindell, K. and Wellings, A. (1993). “Applying New Scheduling Theory to Static Priority Pre-emptive Scheduling.” Software Engineering Journal, 8(5).
3. Tindell, K., Burns, A. and Wellings, A. (1994). “An Extendible Approach for Analyzing Fixed Priority Hard Real-Time Tasks.” Real-Time Systems, 6(2).
4. Lehoczky, J. (1990). “Fixed Priority Scheduling of Periodic Task Sets with Arbitrary Deadlines.” Proceedings of the IEEE Real-Time Systems Symposium.
5. Sha, L., Rajkumar, R. and Lehoczky, J. (1990). “Priority Inheritance Protocols: An Approach to Real-Time Synchronization.” IEEE Transactions on Computers, 39(9).
6. Burns, A. and Wellings, A. (2009). Real-Time Systems and Programming Languages, 4th ed. — Addison-Wesley
7. Rate-monotonic scheduling — Wikipedia