Resource sharing and priority inversion

The task models so far assumed independent tasks. Real tasks share things: buffers, queues, device registers, buses, files. Shared data must be protected so that one task never sees another's half-finished update, and the usual protection is mutual exclusion: a task locks a mutex before entering a critical section and unlocks it afterwards, and any other task that tries to lock the same mutex in the meantime waits. In a priority-scheduled system, that waiting has a nasty consequence. A high-priority task can find itself waiting for a low-priority one, and, worse, the low-priority task can itself be kept off the processor by unrelated medium-priority work. This is priority inversion, and in its unbounded form it has brought down systems as carefully engineered as a Mars lander. Mutexes, semaphores, race conditions and deadlock in general were covered in CMP-320 Operating Systems, also offered as CMPUT-379; here the focus is on their timing. This lesson explains how inversion arises, the protocols that bound it, how to compute the resulting blocking time, and how to include it in response-time analysis.

The NS-5 firmware shares three resources between tasks: the frame-buffer descriptors written by RADAR and read by CLASS, the detection queue written by CLASS and read by CANTX, and the I²C bus used by LOG to write the ferroelectric memory and by HOUSE to read the temperature sensor. Jonah's task is to choose a locking protocol and add the blocking it causes to the analysis.

How priority inversion happens

Consider three tasks, H, M and L, in decreasing order of priority, where H and L share a mutex S and M does not use it. L runs and locks S. H is released, preempts L, and runs until it tries to lock S, which L holds. H blocks, and L resumes, which is unavoidable and expected: H must wait for L to finish its critical section. That bounded wait is called direct blocking. Now M is released. It has higher priority than L and does not need S, so it preempts L and runs for as long as it likes. H, the highest-priority task, is waiting for L, which is waiting for M. For the whole of M's execution, a medium-priority task is effectively running at higher priority than H. If there are several medium-priority tasks, the delay to H has no bound at all.

The simulation below plays out this scenario tick by tick. L is released at 0, computes for one tick, then holds S for three ticks and computes one more. H is released at 2, computes for one tick, holds S for two and computes one more. M is released at 3 and computes for six ticks without touching S. The simulation runs the scenario three times: with no protocol, with priority inheritance and with an immediate priority ceiling.

# Three tasks share one mutex S. Each task is a list of steps: ("run", n) or ("S", n),
# where ("S", n) means lock S, compute n ticks inside the critical section, unlock.
TASKS = {                      # name: (priority, release, steps); a larger number is more urgent
    "H": (3, 2, [("run", 1), ("S", 2), ("run", 1)]),
    "M": (2, 3, [("run", 6)]),
    "L": (1, 0, [("run", 1), ("S", 3), ("run", 1)]),
}
CEILING = 3                    # highest priority of any task that uses S

def simulate(protocol, horizon=20):
    state = {n: dict(step=0, left=steps[0][1], done=None) for n, (_, _, steps) in TASKS.items()}
    owner, line = None, ""
    for t in range(horizon):
        def eff(n):                                   # effective priority under the protocol
            p = TASKS[n][0]
            if n == owner and protocol == "inherit":
                waiting = [TASKS[m][0] for m in TASKS if blocked(m, t)]
                p = max([p] + waiting)
            if n == owner and protocol == "ceiling":
                p = max(p, CEILING)
            return p
        def wants_lock(n):
            s = state[n]
            return s["done"] is None and TASKS[n][2][s["step"]][0] == "S" \
                and s["left"] == TASKS[n][2][s["step"]][1]
        def blocked(n, t):
            return TASKS[n][1] <= t and wants_lock(n) and owner not in (None, n)
        ready = [n for n in TASKS if TASKS[n][1] <= t and state[n]["done"] is None and not blocked(n, t)]
        if not ready:
            line += "."
            continue
        n = max(ready, key=lambda m: (eff(m), m == owner))   # ties go to the lock holder
        s = state[n]
        kind = TASKS[n][2][s["step"]][0]
        if kind == "S" and owner is None:
            owner = n
        s["left"] -= 1
        line += n.lower() if kind == "S" else n
        if s["left"] == 0:
            if kind == "S":
                owner = None
            s["step"] += 1
            if s["step"] == len(TASKS[n][2]):
                s["done"] = t + 1
            else:
                s["left"] = TASKS[n][2][s["step"]][1]
    return line, {n: state[n]["done"] - TASKS[n][1] for n in TASKS}

print("time      " + "".join(str(t % 10) for t in range(20)))
for protocol in ("none", "inherit", "ceiling"):
    line, resp = simulate(protocol)
    print(f"{protocol:9s} {line}   response H={resp['H']} M={resp['M']} L={resp['L']}")
print("capital letter: normal execution, small letter: inside the critical section on S")

time      01234567890123456789
none      LlHMMMMMMllhhHL.....   response H=12 M=6 L=15
inherit   LlHllhhHMMMMMML.....   response H=6 M=11 L=15
ceiling   LlllHhhHMMMMMML.....   response H=6 M=11 L=15
capital letter: normal execution, small letter: inside the critical section on S

With no protocol, H's response time is 12 ticks: it waits through all six ticks of M's execution, which has nothing to do with S. With priority inheritance, L inherits H's priority as soon as H blocks, so M cannot preempt it. L finishes its critical section, H runs and finishes, and only then does M run. H's response time falls to 6 ticks, of which 2 are the unavoidable wait for L's critical section. M's response time grows from 6 to 11, which is correct: M has lower priority than H. With the immediate ceiling protocol, L runs at the ceiling priority of S as soon as it locks, so H does not even start until L has unlocked; H's response time is again 6 ticks, but it is blocked once, before it starts, rather than in the middle of its execution, which saves a context switch.

The Mars Pathfinder resets

The best-known case of priority inversion happened on Mars. A few days after Mars Pathfinder landed in July 1997, its flight computer began resetting itself, losing data each time. The spacecraft ran a commercial real-time kernel. An information bus, a shared memory area used to pass data between tasks, was protected by a mutex. A high-priority bus management task used the bus frequently. A low-priority meteorological data task occasionally locked it to publish its data. A medium-priority communications task, which did not use the bus, ran for comparatively long periods. When the communications task preempted the meteorological task while it held the mutex, the bus management task could not run, a watchdog noticed that it had not completed, concluded that something had gone badly wrong and reset the computer.

Engineers on the ground reproduced the resets on a replica of the spacecraft, with the kernel's trace facility turned on, and found the inversion within hours of trying. The kernel's mutex had an option to enable priority inheritance, which had been left off. The fix was to turn it on by uploading a small patch that changed the mutex's initialization parameter, and the resets stopped. The episode has become a standard case study because every part of it is instructive: the inversion was rare and missed by pre-launch testing, the watchdog turned a timing fault into a safe if disruptive recovery, the trace facility made diagnosis possible, and the ability to patch the software in flight saved the mission.

Priority inheritance protocol

Under the priority inheritance protocol (PIP), formalized by Sha, Rajkumar and Lehoczky in 1990, a task that holds a mutex and blocks a higher-priority task temporarily inherits the higher priority of the blocked task. When it unlocks the mutex, its priority returns to what it would have been without that blocking. Inheritance is transitive: if L blocks M, which blocks H through a second mutex, L inherits H's priority.

Priority inheritance bounds the inversion. A task can be blocked at most once by each lower-priority task, for the duration of one critical section, and at most once for each mutex it uses. That bound can still be large: a high-priority task that uses several mutexes, each held at various times by different lower-priority tasks, can suffer a chain of blocking, one critical section after another. PIP also does not prevent deadlock: two tasks that lock two mutexes in opposite orders can still each wait for the other forever. It is nevertheless widely used, because it is simple, needs no static information about which tasks use which mutexes, and is the protocol behind the POSIX PTHREAD_PRIO_INHERIT mutex attribute.

Priority ceiling protocols

The priority ceiling protocol (PCP), from the same 1990 paper, uses static information to do better. Each mutex is given a ceiling, the highest priority of any task that ever locks it. A task may lock a mutex only if its priority is higher than the ceilings of all mutexes currently locked by other tasks; otherwise it blocks, and the task holding the mutex with the highest such ceiling inherits its priority. The rule looks strange, since a task can be refused a mutex that is free, but it has two strong consequences. A task is blocked for at most the duration of one critical section of one lower-priority task, however many mutexes it uses. And deadlock is impossible, because the ceiling rule prevents the circular waits that cause it.

The immediate ceiling priority protocol, also called the highest locker protocol, is a simpler variant with the same worst-case bound. As soon as a task locks a mutex, its priority is raised to the mutex's ceiling, and it returns to its normal priority when it unlocks. A task that could be blocked by the mutex cannot even start until the mutex is free, so blocking always happens before a job starts, never in the middle. This is easy to implement, causes fewer context switches than inheritance, and is the basis of the POSIX PTHREAD_PRIO_PROTECT mutex attribute and of the ceiling locking policy in the Ada language. Baker's stack resource policy, published in 1991, generalizes the same idea to EDF and to tasks that share a single run-time stack.

Computing the blocking term

Lesson 4 left a term B_i in the response-time equation for blocking. Under either ceiling protocol, B_i is the length of the longest critical section, belonging to any task of lower priority than τ_i, on any resource whose ceiling is at least the priority of τ_i. Note the second condition: a resource used only by low-priority tasks cannot block a high-priority task, but a resource used by a higher-priority task and a lower-priority one can block every task in between, through the inherited or ceiling priority. This is called push-through blocking, and it is why CANTX, which never touches the frame buffer, can still be blocked by CLASS's critical section on it.

Here cs_(k,r) is the longest critical section of task τ_k on resource r, π is the priority and ceil(r) is the ceiling of r. The NS-5's measured critical sections are: on the frame-buffer descriptors, 60 µs in RADAR and 150 µs in CLASS; on the detection queue, 40 µs in CLASS and 50 µs in CANTX; on the I²C bus, 400 µs in LOG and 300 µs in HOUSE. The code below computes the ceilings and blocking terms and repeats the response-time analysis of the 11 ms classifier variant with blocking included.

from math import ceil

# tasks in priority order (index 0 highest): name, C, T, D in microseconds
tasks = [("RADAR", 1_200, 6_250, 6_250), ("CANTX", 800, 10_000, 10_000),
         ("CLASS", 11_000, 25_000, 25_000), ("LOG", 8_000, 100_000, 100_000),
         ("HOUSE", 20_000, 1_000_000, 1_000_000)]
# longest critical section of each task on each shared resource, microseconds
cs = {"framebuf": {"RADAR": 60, "CLASS": 150},
      "detq":     {"CLASS": 40, "CANTX": 50},
      "i2c":      {"LOG": 400, "HOUSE": 300}}

prio = {name: i for i, (name, *_) in enumerate(tasks)}           # smaller index = higher
ceiling = {r: min(prio[t] for t in users) for r, users in cs.items()}

def blocking(name):
    """priority ceiling protocol: one critical section of a lower-priority task
    on a resource whose ceiling is at least the task's priority"""
    cands = [length for r, users in cs.items() if ceiling[r] <= prio[name]
             for t, length in users.items() if prio[t] > prio[name]]
    return max(cands, default=0)

for r in cs:
    print(f"ceiling of {r:8s} = priority of {tasks[ceiling[r]][0]}")
print("task    B (us)   R (ms)   D (ms)")
for i, (name, c, t, d) in enumerate(tasks):
    b = blocking(name)
    r = c + b
    while True:
        nxt = c + b + sum(ceil(r / tj) * cj for _, cj, tj, _ in tasks[:i])
        if nxt == r or nxt > d:
            break
        r = nxt
    print(f"{name:6s}  {b:6d}   {nxt/1000:6.2f}   {d/1000:6g}  {'met' if nxt <= d else 'MISSED'}")

ceiling of framebuf = priority of RADAR
ceiling of detq     = priority of CANTX
ceiling of i2c      = priority of LOG
task    B (us)   R (ms)   D (ms)
RADAR      150     1.35     6.25  met
CANTX      150     2.15       10  met
CLASS        0    16.20       25  met
LOG        300    42.70      100  met
HOUSE        0    99.20     1000  met

RADAR and CANTX can each be blocked for 150 µs by the classifier's critical section on the frame buffer, CANTX through push-through blocking. CLASS cannot be blocked at all, because the only resources with lower-priority users are the I²C bus, whose ceiling is LOG's priority, below CLASS. LOG can be blocked by HOUSE's 300 µs I²C transaction, and HOUSE, the lowest-priority task, has no one below it to block it. The response times grow by at most 0.3 ms, and every deadline is still met. The analysis also tells Jonah where to look if the margin ever becomes tight: the 400 µs I²C write in LOG, for example, is the longest critical section in the system, and it is harmless only because no task above LOG uses the bus.

Alternatives to locking

Critical sections are not the only way to share data. For very short updates, disabling interrupts, or raising the interrupt priority mask, is the cheapest form of mutual exclusion on a single processor, and it is effectively an immediate ceiling at the top priority. It adds its length to the blocking of every task and to the interrupt latency, so it must be kept to a few microseconds. Message passing through kernel queues avoids shared state altogether, at the cost of copying. Lock-free structures such as a single-producer, single-consumer ring buffer, which CMP-315 used between an interrupt handler and a task, need no lock because each index is written by only one side; on a multiprocessor they need memory barriers. Double buffering, as the NS-5 radar DMA does, lets the writer and the reader work on different copies and swap them at a known point. Each of these choices should be visible in the design so that reviewers know which data can be accessed by whom and when.

Whichever mechanism is used, critical sections should be short, should never contain a blocking call such as a delay or a wait for I/O, and should never be nested unless the nesting order is fixed and documented. A critical section that waits for an I²C transaction to complete, as LOG's 400 µs write does, is acceptable only because the analysis shows its effect; replacing it with a queued request to a bus manager task would remove the blocking from LOG altogether.