Real-time scheduling theory

Measuring a system tells you what it did; scheduling theory tells you what it will do. Given each task's period, deadline and worst-case execution time, the results in this lesson decide in advance whether every job of every task will meet its deadline under a particular scheduling policy, even in the worst possible alignment of releases. The tests are short calculations, easy to automate and fast enough to rerun every time the firmware changes. They rest on assumptions that real systems only approximate, and part of this lesson is about what to add when those assumptions are broken by context switches, interrupts, blocking on shared resources and release jitter.

The task model

The classic model, due to Liu and Layland in 1973, describes each task \( \tau_i \) by three numbers: its worst-case execution time \( C_i \), its period \( T_i \) (or minimum inter-arrival time for sporadic tasks) and its relative deadline \( D_i \), often equal to \( T_i \). Its utilization is \( U_i = C_i / T_i \), and the task set's total utilization is

The basic model also assumes tasks are independent (no shared resources), run on one processor, can be preempted at any instant, and that kernel overheads are zero. These assumptions are relaxed later in the lesson. A first, obvious condition follows immediately: no scheduler can meet all deadlines on one processor if \( U > 1 \), because the tasks demand more than 100 % of the processor over the long run.

Fixed-priority scheduling and rate-monotonic priorities

Most RTOSes, and the interrupt controllers of most microcontrollers, schedule by fixed priority: each task has a priority that does not change, and the highest-priority ready task runs. The question is how to assign priorities. Liu and Layland proved that when deadlines equal periods, rate-monotonic (RM) assignment, giving higher priority to tasks with shorter periods, is optimal among fixed-priority schemes: if any fixed-priority assignment meets all deadlines, RM does. When deadlines are shorter than periods, deadline-monotonic assignment (shorter deadline, higher priority) is optimal instead. In practice this means the joint loop at 1 kHz should outrank the trajectory generator at 250 Hz, which should outrank telemetry at 50 Hz, regardless of which feels most important; importance is handled by giving important functions short enough periods and deadlines.

Liu and Layland also gave a simple sufficient test. Under RM, a set of n tasks with deadlines equal to periods is schedulable if

The bound is 1.0 for one task, 0.828 for two, 0.780 for three and falls toward \( \ln 2 \approx 0.693 \) as n grows. It is sufficient but not necessary: a task set above the bound may still be schedulable, and often is. Task sets with harmonic periods, where each period divides the longer ones (1, 2, 4, 8 ms), are schedulable under RM right up to U = 1, which is one reason designers choose harmonic rates.

Response-time analysis

Response-time analysis (RTA), developed by Joseph and Pandya and by Audsley and colleagues in the 1980s and 1990s, gives an exact test for fixed-priority scheduling. The worst-case response time of task i occurs when it is released at the same instant as every higher-priority task, the critical instant. Its response time is its own execution time plus the interference from every higher-priority task j released during that time:

Because \( R_i \) appears on both sides, the equation is solved by iteration: start with \( R_i^{(0)} = C_i \), substitute to get the next value, and repeat until the value stops changing (the task is schedulable if the converged \( R_i \le D_i \)) or exceeds the deadline (it is not). The ceiling counts how many times each higher-priority task can be released within the window.

import math

def rta(tasks):
    """tasks: list of (name, C, T, D), highest priority first. Returns response times."""
    out = []
    for i, (name, C, T, D) in enumerate(tasks):
        R = C
        while True:
            nxt = C + sum(math.ceil(R / Tj) * Cj for _, Cj, Tj, _ in tasks[:i])
            if nxt == R or nxt > D:
                R = nxt
                break
            R = nxt
        out.append((name, R, D, R <= D))
    return out

def ll_bound(n):
    return n * (2 ** (1 / n) - 1)

sets = {
    "example": [("t1", 1, 4, 4), ("t2", 2, 6, 6), ("t3", 3, 12, 12)],
    "tight":   [("t1", 2, 5, 5), ("t2", 4, 7, 7)],
}
for label, ts in sets.items():
    U = sum(C / T for _, C, T, _ in ts)
    print("%s: U = %.3f, LL bound = %.3f" % (label, U, ll_bound(len(ts))))
    for name, R, D, ok in rta(ts):
        print("   %s: R = %d, D = %d, %s" % (name, R, D, "meets" if ok else "MISSES"))

example: U = 0.833, LL bound = 0.780
   t1: R = 1, D = 4, meets
   t2: R = 3, D = 6, meets
   t3: R = 10, D = 12, meets
tight: U = 0.971, LL bound = 0.828
   t1: R = 2, D = 5, meets
   t2: R = 8, D = 7, MISSES

The second task set has utilization 0.971. Under fixed priorities its lower-priority task needs 8 ms but has only 7, so no fixed-priority assignment works (the other order fails too). The next section shows a scheduler that handles it.

Earliest deadline first

Earliest deadline first (EDF) is a dynamic-priority policy: at each moment, the ready job whose absolute deadline is soonest runs. Liu and Layland showed that for independent preemptible tasks with deadlines equal to periods, EDF meets every deadline if and only if \( U \le 1 \). It is optimal on one processor: if any scheduler can meet all deadlines, EDF can. The 'tight' task set above, with U = 0.971, is schedulable under EDF.

If EDF is so good, why do most RTOSes use fixed priorities? Several reasons. Fixed priorities map directly onto interrupt controllers and simple kernels. Their overload behavior is predictable: when the system is overloaded, the lowest-priority tasks miss deadlines and the important high-rate tasks keep running, whereas under EDF an overload can cause a cascade of misses across many tasks. And fixed-priority systems are easier to reason about during debugging. EDF is available in some kernels, including Linux's SCHED_DEADLINE policy (lesson 9), and is attractive when utilization must be pushed close to 100 %.

Making the model realistic

Real systems break the textbook assumptions in predictable ways, and RTA extends to cover each of them.

• Kernel overheads: add the cost of two context switches (and any scheduler work) to each task's C, or model the tick interrupt as an extra highest-priority task.
• Interrupts: interrupt routines effectively run above every task. Include each one in the interference sum with its own C and minimum inter-arrival time.
• Blocking: when a task waits for a resource held by a lower-priority task, its response time grows by a blocking term \( B_i \). With the priority ceiling or inheritance protocols of lesson 6, \( B_i \) is bounded by the longest critical section of a lower-priority task that can block it.
• Release jitter: if a task's release can be delayed by up to \( J_j \) after its nominal time, more of its releases can fall inside a window. The interference term uses \( \lceil (R_i + J_j)/T_j \rceil \), and the response time measured from the nominal release becomes \( R_i + J_i \).

Putting these together gives the response-time equation most practitioners use:

Multicore scheduling

Modern robot computers have several cores, and multicore scheduling is considerably harder. In partitioned scheduling, each task is assigned to one core and each core is scheduled independently, so the single-core tests apply per core; the difficulty moves to the bin-packing problem of assigning tasks to cores. In global scheduling, any task can run on any core, which can use capacity better but brings timing anomalies and much weaker tests, and makes WCET harder to bound because tasks migrate between caches. Most hard real-time robot software uses partitioning: the control tasks are pinned to dedicated cores, and lesson 9 shows how Linux supports this with CPU affinity and isolation.