Concurrency, synchronization and priority inversion

As soon as two tasks share anything, a sensor bus, a buffer of joint targets, a log file, a counter, the order in which they touch it starts to matter. Preemptive scheduling, which lesson 5 relied on to give high-priority tasks fast responses, is exactly what makes sharing dangerous: a task can be interrupted in the middle of updating a structure, and another task can read it half-written. Synchronization primitives prevent that, but they introduce their own timing hazards, the most famous being priority inversion, which nearly ended NASA's Mars Pathfinder mission in 1997. This lesson covers race conditions, critical sections, mutexes and semaphores, priority inversion and the protocols that bound it, deadlock, and lock-free alternatives used in robot software.

Race conditions

A race condition is a bug whose effect depends on the timing of concurrent activities. The textbook case is incrementing a shared counter. 'count = count + 1' compiles to three steps: load count into a register, add one, store it back. If task A loads the value 41, is preempted, task B loads 41, adds one and stores 42, and then A resumes and stores its own 42, one increment is lost. On a robot, the shared item might be a joint target written by the trajectory task and read by the control task: if the control task reads three of six joint values from the new trajectory point and three from the old one, the arm receives a target that was never planned. Such bugs may appear once a week, never in the lab, and leave no trace.

The cure is to make each access to shared data atomic, meaning it completes as one indivisible step from the point of view of other tasks. A sequence of operations that must be atomic is a critical section. Critical sections can be protected by disabling interrupts briefly (suitable only for a few instructions, and covered in lesson 7), by a mutex, or by designs that avoid sharing mutable data at all.

Mutexes and semaphores

A mutex (mutual exclusion lock) is a kernel object that only one task can hold at a time. A task takes the mutex before entering a critical section and gives it back afterwards; if another task holds it, the requester blocks until it is released. Mutexes have an owner, which lets the kernel apply priority inheritance (below) and detect errors such as a task releasing a mutex it does not hold. A semaphore is a counter with take and give operations; a binary semaphore is a signaling device (an interrupt gives it, a task waits for it), and a counting semaphore tracks a pool of identical resources. A common mistake is to use a binary semaphore as a lock: it works functionally, but without ownership the kernel cannot apply priority inheritance.

/* Protecting a shared joint target with a FreeRTOS mutex */
static SemaphoreHandle_t target_mtx;      /* created with xSemaphoreCreateMutex() */
static joint_target_t shared_target;

void trajectory_publish(const joint_target_t *t)          /* 250 Hz task */
{
    if (xSemaphoreTake(target_mtx, pdMS_TO_TICKS(1)) == pdTRUE) {
        shared_target = *t;                                /* short copy   */
        xSemaphoreGive(target_mtx);
    } else {
        fault_report(FAULT_TARGET_LOCK_TIMEOUT);
    }
}

void control_get_target(joint_target_t *out)              /* 1 kHz task */
{
    xSemaphoreTake(target_mtx, portMAX_DELAY);
    *out = shared_target;                                  /* copy, then release */
    xSemaphoreGive(target_mtx);
}

Two rules keep mutex use safe in real-time code. Keep critical sections short and bounded: copy data in and out under the lock, and do the computation outside it. And use timeouts where blocking indefinitely would be worse than reporting a fault. The longest critical section of each lower-priority task becomes the blocking term \( B_i \) in the response-time analysis of lesson 5, so long critical sections directly lengthen high-priority response times.

Priority inversion

Priority inversion happens when a high-priority task waits for a resource held by a low-priority task, and a medium-priority task, which needs neither, preempts the low-priority holder. The high-priority task is now effectively waiting for the medium-priority task, for as long as the medium-priority task runs. If several medium-priority tasks are active, the delay is unbounded.

The Mars Pathfinder lander, which touched down on 4 July 1997 running the VxWorks RTOS, suffered exactly this. A low-priority meteorological data task held a mutex protecting a shared information bus; a high-priority bus management task needed the same mutex; and medium-priority communications tasks preempted the low-priority holder. The high-priority task could not finish in time, a watchdog detected the missed deadline, and the spacecraft reset itself repeatedly, losing data. Engineers at the Jet Propulsion Laboratory reproduced the fault on a ground replica using the system's trace facility, found that the mutex had been created with priority inheritance turned off, and fixed it by uploading a small change that switched inheritance on. The episode became the standard illustration of why real-time engineers treat locking and priorities as one design problem.

Priority inheritance and priority ceiling

Two protocols bound priority inversion.

• Priority inheritance: when a high-priority task blocks on a mutex, the task holding it temporarily inherits the blocked task's priority until it releases the mutex. Medium-priority tasks can no longer preempt the holder, so the high-priority task waits only for the remainder of the critical section. FreeRTOS and Zephyr mutexes inherit priority by default; POSIX mutexes do so when created with the PTHREAD_PRIO_INHERIT protocol.
• Priority ceiling: each mutex is given a ceiling equal to the highest priority of any task that uses it. In the immediate ceiling variant, a task that locks the mutex is raised to the ceiling at once, before anyone else asks. This prevents deadlock between ceiling-protected mutexes and limits each task to being blocked at most once, for the length of one critical section, per job. POSIX offers it as PTHREAD_PRIO_PROTECT, and the Ada and OSEK/AUTOSAR worlds use it widely.

With either protocol, the blocking term for task i is bounded: under the ceiling protocol, \( B_i \) is the longest single critical section of any lower-priority task that uses a mutex whose ceiling is at least task i's priority. Under basic inheritance the bound is a little larger, because a task can be blocked once per mutex it needs.

# Discrete-time simulation of priority inversion with and without inheritance
def simulate(inherit):
    # name: (priority, release, plan); plan steps: 'c' compute, 'k' needs lock
    tasks = {"L": (1, 0, "kkkkc"), "M": (2, 2, "cccccccc"), "H": (3, 1, "ckkc")}
    pos = {n: 0 for n in tasks}; done = {}; owner = None
    for t in range(40):
        def prio(n):
            p = tasks[n][0]
            if inherit and owner == n:
                waiting = [tasks[m][0] for m in tasks if m != n and m not in done
                           and tasks[m][1] <= t and tasks[m][2][pos[m]] == "k"]
                p = max([p] + waiting)
            return p
        ready = [n for n in tasks if n not in done and tasks[n][1] <= t
                 and not (tasks[n][2][pos[n]] == "k" and owner not in (None, n))]
        if not ready:
            continue
        run = max(ready, key=prio)
        if tasks[run][2][pos[run]] == "k":
            owner = run
        pos[run] += 1
        plan = tasks[run][2]
        if pos[run] == len(plan) or plan[pos[run]] != "k":
            if owner == run:
                owner = None
        if pos[run] == len(plan):
            done[run] = t + 1
    return {n: done[n] - tasks[n][1] for n in tasks}

for inherit in (False, True):
    r = simulate(inherit)
    print("inheritance" if inherit else "no protocol", " response times:",
          ", ".join("%s=%d" % (n, r[n]) for n in "HML"))

no protocol  response times: H=15, M=8, L=17
inheritance  response times: H=7, M=14, L=17

Without a protocol, the high-priority task takes 15 ticks, because its wait includes the whole of the medium task's execution. With inheritance it takes 7: its own work plus the rest of the low task's critical section. The medium task, which does not need the resource, finishes later instead, rising from 8 ticks to 14, and the low task is unaffected. That trade, making unrelated lower-priority work wait so that urgent work is bounded, is exactly what fixed-priority scheduling is supposed to do.

Deadlock

Deadlock occurs when tasks wait for each other in a cycle: task A holds mutex 1 and waits for mutex 2, while task B holds mutex 2 and waits for mutex 1. Neither can proceed, ever. Four conditions are all needed for deadlock: mutual exclusion, holding a resource while waiting for another, no preemption of resources and a circular wait. Breaking any one prevents it. The most practical rule is a global lock order: number every mutex and always acquire them in increasing order, which makes a circular wait impossible. Other defenses are to avoid holding one lock while taking another, to use timeouts that turn a hang into a reportable fault, and, under the immediate priority ceiling protocol, to rely on its built-in deadlock freedom on a single core.

Lock-free communication

Locks are not the only way to share data. Several lock-free patterns are standard in real-time robot code because they never block the faster task.

• Single-producer single-consumer ring buffer: one task only writes the head index, the other only writes the tail index, and on a single core (or with appropriate memory barriers on multicore) no lock is needed. This is the usual way to pass samples from an interrupt to a task, or log entries from a control task to a logging task.
• Double buffering: the writer fills an inactive buffer and then switches a single pointer or index, which is one atomic store, to publish it. The reader always sees a complete buffer. A triple buffer adds a third slot so the writer never has to wait for the reader to finish.
• Sequence locks: the writer increments a counter before and after writing; the reader reads the counter, copies the data, reads the counter again and retries if it changed or was odd. Readers never block the writer, which suits a fast writer and occasional readers.
• Atomic operations: modern processors provide atomic increment, compare-and-swap and load-linked/store-conditional instructions, accessible from C11 and C++11 atomics, for counters and flags.

Lock-free code is harder to write correctly than it looks, especially on multicore processors with weakly ordered memory, so it is best taken from well-tested libraries or kept to the simple single-producer single-consumer patterns.