Aperiodic work, servers and mixed criticality

A real-time system does not only run periodic tasks. Operators send commands, technicians plug in service tools, network messages arrive in bursts and faults trigger diagnostic routines. This aperiodic work has no minimum interarrival time, so it cannot be given a guarantee of its own, but it should be served quickly, and above all it must never endanger the periodic tasks that do have guarantees. The standard answer is a server: a scheduling entity with a budget of processor time per period, which runs aperiodic requests within that budget and is itself analyzed as if it were a periodic task. The same idea of budgets, applied to whole groups of tasks of different importance, leads to mixed-criticality scheduling, where the guarantees given to a task depend on how critical it is. This lesson covers both.

Two new demands land on Jonah's desk. Dev Okafor, the field technician, wants the service port to answer diagnostic commands within a few milliseconds instead of the second or so it takes now. And the City of Kingston's traffic office wants per-lane statistics from every NS-5 at its intersections, computed on the node every 20 ms. The second task is useful but not safety-related; the first must not delay the radar.

Background service

The simplest way to run aperiodic work is in the background, at a priority below every periodic task, so it uses only idle time. Background service is perfectly safe for the periodic tasks, which cannot even tell it exists, and it needs no analysis. Its weakness is response time: aperiodic requests wait until every periodic job has finished, which at high utilization can take a very long time. On the NS-5, the service port is currently handled this way, below HOUSE, and a command can wait for the whole 99 ms of HOUSE's response time plus whatever else is pending.

Running aperiodic work at the highest priority is the opposite extreme: excellent response, but no guarantee for anyone else, because the amount of aperiodic work is unbounded. Servers sit between the two. They run aperiodic work at a chosen priority, but only up to a budget, so that the interference they cause is bounded and can be included in the analysis.

Polling and deferrable servers

A polling server is a periodic task with budget C_s and period T_s. At each release it checks the aperiodic queue; if requests are waiting, it serves them until the queue is empty or the budget runs out. If the queue is empty at the release, the budget is lost until the next period. In the analysis, a polling server is exactly a periodic task with C = C_s and T = T_s, so response-time analysis applies unchanged. Its weakness is that a request arriving just after an empty poll waits for the whole period.

A deferrable server, described by Strosnider, Lehoczky and Sha in 1995, fixes this by keeping its budget for the whole period: if no request is waiting at the release, the budget is preserved and can be used whenever a request arrives, until the next replenishment restores it to C_s. Response is much better, but the analysis changes. A deferrable server can use its budget at the very end of one period and again at the very start of the next, delivering 2C_s of interference in a short interval. This back-to-back execution makes it behave like a periodic task with release jitter of T_s − C_s, which is how it is included in response-time analysis using the jitter term of lesson 4.

The simulation below compares the three approaches on a small task set: task A with C = 2, T = 6 and task B with C = 3, T = 12, in milliseconds, and a server with budget 1 ms and period 4 ms at the highest priority. Three aperiodic requests arrive: 2 ms of work at t = 1, 1 ms at t = 9 and 2 ms at t = 14.

# Periodic tasks and one aperiodic server under fixed priority, simulated in 1 ms ticks.
PERIODIC = [("A", 2, 6), ("B", 3, 12)]          # name, C, T; A has the higher priority
SERVER_C, SERVER_T = 1, 4                        # budget and period; the server is highest priority
REQUESTS = [(1, 2), (9, 1), (14, 2)]             # aperiodic arrivals: (time, work in ms)
HORIZON = 24

def simulate(kind):
    rem = {n: 0 for n, _, _ in PERIODIC}
    queue, budget, line, done = [], 0, "", {}
    for t in range(HORIZON):
        for n, c, per in PERIODIC:
            if t % per == 0:
                rem[n] += c
        for at, work in REQUESTS:
            if at == t:
                queue.append([at, work])
        if t % SERVER_T == 0:
            if kind == "deferrable":
                budget = SERVER_C                       # replenished, kept while idle
            elif kind == "polling":
                budget = SERVER_C if queue else 0       # lost if nothing is waiting now
        if kind != "background" and queue and budget > 0:
            run = "server"
        else:
            ready = [n for n, _, _ in PERIODIC if rem[n] > 0]
            run = ready[0] if ready else ("background" if kind == "background" and queue else None)
        if run in ("server", "background"):
            queue[0][1] -= 1
            line += "s"
            if run == "server":
                budget -= 1
            if queue[0][1] == 0:
                done[queue[0][0]] = t + 1 - queue[0][0]
                queue.pop(0)
        elif run:
            rem[run] -= 1
            line += run
        else:
            line += "."
        if kind == "polling" and not queue:
            budget = 0                                  # a polling server gives up unused budget
    return line, done

print("time        " + "".join(str(t % 10) for t in range(HORIZON)))
for kind in ("background", "polling", "deferrable"):
    line, done = simulate(kind)
    resp = ", ".join(f"arrival {a}: {r} ms" for a, r in sorted(done.items()))
    print(f"{kind:11s} {line}   {resp}")
print("s = aperiodic work, A and B = periodic tasks, . = idle")

time        012345678901234567890123
background  AABBBsAAss..AABBBsAAs...   arrival 1: 8 ms, arrival 9: 1 ms, arrival 14: 7 ms
polling     AABBsBAAs...sAABsBAAsB..   arrival 1: 8 ms, arrival 9: 4 ms, arrival 14: 7 ms
deferrable  AsABsBAABs..AAsBsBAAB...   arrival 1: 4 ms, arrival 9: 1 ms, arrival 14: 3 ms
s = aperiodic work, A and B = periodic tasks, . = idle

In the background, the first and third requests take 8 and 7 ms because they wait for idle time; the second happens to arrive when the processor is idle and takes 1 ms. The polling server is no better here. The first request arrives at t = 1, just after the empty poll at t = 0, waits for the poll at t = 4 and then needs a second period for its second millisecond. The second request arrives at t = 9, just after the poll at t = 8 found the queue empty, and waits until t = 12. The deferrable server serves the first request immediately with its unused budget, finishing it at t = 5 for a response of 4 ms, serves the second at once in 1 ms and the third in 3 ms. In every case, A and B meet all their deadlines, because the server's interference is bounded by its budget.

Sporadic servers and bandwidth servers

The sporadic server, introduced by Sprunt, Sha and Lehoczky in 1989, keeps the good response of the deferrable server without the back-to-back penalty. Instead of restoring its budget at fixed instants, it replenishes each chunk of budget it consumes exactly one period after that chunk started to be used. This rule ensures that in any window of length T_s the server never uses more than C_s, so it can be analyzed exactly like a periodic task with C_s and T_s. The POSIX standard defines a sporadic server scheduling policy, SCHED_SPORADIC, based on this rule, although few kernels implement it, and its correct implementation proved subtle enough that errors in the original specification were found and corrected later.

Under EDF, servers take a slightly different form. The total bandwidth server assigns each aperiodic request a deadline as if it were a periodic task with utilization U_s, so that a request of size a arriving at time r gets deadline max(r, previous deadline) + a/U_s, and then lets EDF schedule it with everything else. The constant bandwidth server (CBS), proposed by Abeni and Buttazzo in 1998, adds a budget so that a request that runs longer than declared has its deadline postponed rather than stealing time from other tasks. CBS gives temporal isolation: each task served by its own CBS receives its reserved bandwidth whatever the others do. It is the basis of the deadline scheduling class in Linux, SCHED_DEADLINE, in which each thread declares a runtime, a deadline and a period.

Slack stealing takes yet another approach. It computes, at run time, how much the periodic tasks could be delayed without missing any deadline, and gives that slack to aperiodic work immediately. Slack stealing gives the best possible aperiodic response for a fixed-priority system but needs offline tables or significant run-time computation, so it is rarely used outside research and specialized systems.

Mixed criticality

A modern embedded processor often hosts functions of different importance. On the NS-5 the radar, CAN service and classifier are safety-related: they feed signal timing. The new statistics task, the logger and housekeeping are not. A classical analysis must use one execution-time estimate per task, and the conservative estimates demanded by safety standards for high-criticality tasks can be much larger than the measured values, which would waste much of the processor if applied to everything. Vestal proposed in 2007 that each task have several execution-time estimates, one per criticality level, with more conservative estimates at higher levels, and that the guarantee given to a task depend on its criticality.

In the dual-criticality model, each task has a criticality, LO or HI, and an execution-time estimate C(LO). HI tasks also have a larger, more conservative estimate C(HI). The system starts in LO mode, where every task is expected to run within C(LO). If any HI task executes beyond its C(LO) without finishing, the system switches to HI mode, and LO tasks are dropped or suspended, freeing the processor so that HI tasks can run up to C(HI). The guarantee is: in LO mode all tasks meet their deadlines; in HI mode, including across the switch, all HI tasks meet theirs.

The adaptive mixed-criticality scheme (AMC), analyzed by Baruah, Burns and Davis in 2011, implements this with fixed priorities. Its response-time bound for each HI task, called AMC-rtb, has three parts: the task's own C(HI), interference from higher-priority HI tasks at their C(HI) values, and interference from higher-priority LO tasks only up to the LO-mode response time R_i(LO), because LO tasks are stopped once the switch occurs, which must happen before R_i(LO).

Jonah applies this to the NS-5 with the statistics task, STATS, added at C = 4 ms and T = D = 20 ms, which in rate-monotonic order sits between CANTX and CLASS. The safety assessor requires C(HI) values of 1.6 ms for RADAR, 1.0 ms for CANTX and 9 ms for CLASS, from a static timing analysis with margins, against measured C(LO) values of 1.2, 0.8 and 6 ms.

from math import ceil

# name, criticality, C(LO), C(HI), T = D, in microseconds; rate-monotonic priority order
tasks = [("RADAR", "HI", 1_200, 1_600, 6_250), ("CANTX", "HI", 800, 1_000, 10_000),
         ("STATS", "LO", 4_000, 4_000, 20_000), ("CLASS", "HI", 6_000, 9_000, 25_000),
         ("LOG", "LO", 8_000, 8_000, 100_000), ("HOUSE", "LO", 20_000, 20_000, 1_000_000)]

def fixpoint(start, f, limit):
    r = start
    while True:
        nxt = f(r)
        if nxt == r or nxt > limit:
            return nxt
        r = nxt

def amc_rtb():
    out = []
    for i, (n, crit, clo, chi, t) in enumerate(tasks):
        hp = tasks[:i]
        rlo = fixpoint(clo, lambda r: clo + sum(ceil(r / tj) * cj for _, _, cj, _, tj in hp), t)
        rhi = None
        if crit == "HI":
            hph = [x for x in hp if x[1] == "HI"]
            hpl = [x for x in hp if x[1] == "LO"]
            lo_part = sum(ceil(rlo / tk) * ck for _, _, ck, _, tk in hpl)   # LO work only until the switch
            rhi = fixpoint(chi, lambda r: chi + lo_part + sum(ceil(r / tj) * cj for _, _, _, cj, tj in hph), t)
        out.append((n, crit, rlo, rhi, t))
    return out

def all_at_hi():
    out = []
    for i, (n, crit, clo, chi, t) in enumerate(tasks):
        c = chi
        r = fixpoint(c, lambda r: c + sum(ceil(r / tj) * cj for _, _, _, cj, tj in tasks[:i]), t)
        out.append((n, r, t))
    return out

ulo = sum(clo / t for _, _, clo, _, t in tasks)
uhi = sum(chi / t for _, c, _, chi, t in tasks if c == "HI")
uall = sum(chi / t for _, _, _, chi, t in tasks)
print(f"U(LO mode, all tasks) = {ulo:.3f}   U(HI mode, HI tasks only) = {uhi:.3f}   U(every task at C(HI)) = {uall:.3f}")
print("AMC-rtb                       |  every task budgeted at C(HI)")
for (n, crit, rlo, rhi, t), (_, r2, _) in zip(amc_rtb(), all_at_hi()):
    ok = rlo <= t and (rhi is None or rhi <= t)
    hi = f"{rhi/1000:6.2f}" if rhi is not None else "     -"
    print(f"{n:6s} {crit}  R_LO {rlo/1000:6.2f}  R_HI {hi}  {'ok  ' if ok else 'MISS'}  |  R {r2/1000:7.2f}  {'ok' if r2 <= t else 'MISS'}")

U(LO mode, all tasks) = 0.812   U(HI mode, HI tasks only) = 0.716   U(every task at C(HI)) = 1.016
AMC-rtb                       |  every task budgeted at C(HI)
RADAR  HI  R_LO   1.20  R_HI   1.60  ok    |  R    1.60  ok
CANTX  HI  R_LO   2.00  R_HI   2.60  ok    |  R    2.60  ok
STATS  LO  R_LO   6.00  R_HI      -  ok    |  R    8.20  ok
CLASS  HI  R_LO  15.20  R_HI  22.40  ok    |  R   26.40  MISS
LOG    LO  R_LO  39.60  R_HI      -  ok    |  R   99.60  ok
HOUSE  LO  R_LO  99.20  R_HI      -  ok    |  R 1016.00  MISS

In LO mode every task meets its deadline at a utilization of 0.812, and in HI mode the three HI tasks meet theirs, CLASS with a worst-case response time of 22.4 ms against its 25 ms deadline. Budgeting every task at its HI estimate instead would raise utilization to 1.016, over 100 %, and CLASS and HOUSE would miss deadlines. Mixed criticality lets the product carry the statistics feature on the same processor without weakening the guarantee for the safety-related tasks. The price is that in a HI-mode episode, which the assessor expects to be extremely rare, statistics, logging and housekeeping pause until the system returns to LO mode at the next idle instant.

Mixed criticality is an active research area, and its industrial use is more cautious than the theory. Certification standards, discussed in lesson 12, traditionally demand that lower-criticality software be unable to affect higher-criticality software at all, which is usually achieved by partitioning in time and space, as in the ARINC 653 architecture of lesson 6, rather than by mode switches. Practical systems therefore combine the ideas: strict partitions between criticality levels, budget enforcement within them, and analysis that uses realistic estimates for low-criticality work and conservative ones for high-criticality work.

Enforcement makes analysis true

Every technique in this lesson depends on budgets being enforced at run time. A server whose budget is not enforced is just a high-priority task with unbounded execution. A mixed-criticality system that cannot detect a HI task overrunning C(LO) cannot switch modes. Kernels therefore provide execution-time monitoring, using a timer armed with the remaining budget when a task or server is dispatched and disarmed when it is preempted or finishes. On the NS-5, Jonah configures the kernel's budget timers for the service-port server and for STATS, and adds a check that raises a fault if CLASS exceeds its C(LO), which triggers the switch to HI mode and is logged for later analysis.