Race Conditions, Deadlocks, and Priority Inversion

Preemption can switch tasks between any two instructions, so every shared variable that more than one task writes has the same problem as the handler and main loop of unit 9, lesson 5: count++ is a load, an add and a store, and a switch in the middle loses one update. Two patterns cause most task races:

• read-modify-write of shared data: counters, flags packed into one word, linked lists;
• check-then-act: if (buffer_has_space()) buffer_put(x); where another task fills the buffer between the check and the act.

The fixes are the ones from lesson 4: make the whole sequence one critical section or one mutex-protected region, give the data a single owner (a gatekeeper task), or pass it through a queue so no two tasks ever touch the same copy. Declaring the variable volatile fixes none of them.

A mutex makes a task wait for the lower-priority task that holds it. That is priority inversion, and a short amount of it is unavoidable: the high-priority task H waits for the rest of the low-priority task L’s critical section. The Linux documentation accepts that “most of the time it can't be helped” and names the dangerous case unbounded priority inversion: while H waits for L, a medium-priority task M becomes ready. M does not use the resource, but it is more urgent than L, so it preempts L; and since L cannot run, H cannot run either. H now waits for as long as M, and every other medium-priority task, wants to run.

↑ This step uses the figure at the top of the page.

With a plain binary semaphore, H’s blocking time contains M’s entire execution. Nothing in H’s or L’s code is wrong; the failure appears only when the three tasks line up, which is why it shows up rarely and in the field.

Priority inheritance removes the medium task from the picture: while H waits for a mutex, the owner L runs at H’s priority, so M can no longer preempt it. When L releases the mutex it drops back to its own priority, and H takes the mutex and runs. H’s blocking is then bounded by the rest of L’s critical section, whatever M does.

FreeRTOS mutexes (xSemaphoreCreateMutex()), Zephyr mutexes and Linux rt-mutexes all use it, with differences in detail:

• FreeRTOS raises the holder to the priority of the waiting task and, on release, returns it to its base priority only when it holds no other mutexes; binary semaphores get no inheritance at all.
• Zephyr tracks every mutex a thread holds and recalculates its priority from the remaining waiters on each unlock, and propagates the boost along chains of owners up to a limit.
• Linux rt-mutexes propagate the boost when a boosted owner itself blocks on another rt-mutex, and remove it “immediately” on unlock.

Inheritance bounds the inversion; it does not make it small. H still waits for the longest critical section of any lower-priority task that shares a lock with it, possibly several in a chain. As the Linux documentation puts it, priority inheritance “is not a magic bullet for poorly designed applications”. Keep critical sections short, and do not block on anything else while holding a lock.

A priority ceiling protocol goes further: each lock is given the priority of its most urgent user, and a task that takes it runs at that priority at once. H can then be blocked by at most one lower-priority critical section, and lock-order deadlocks between those tasks cannot occur. (Zephyr’s CONFIG_PRIORITY_CEILING only caps how far inheritance may raise a priority; it is not this protocol.)

A third option in the figure is to disable preemption (or interrupts) inside L’s critical section: no other task can run while L holds the resource, so M cannot preempt it and the inversion is bounded too. The price is that every task, including ones that never touch the resource, waits for the whole critical section. It suits sections of a few microseconds, not milliseconds.

L takes the lock at t = 1 ms and needs 3 ms of work inside it. H becomes ready at t = 2 ms, runs for 1 ms, and requests the lock at t = 3 ms, when L still has 2 ms to go. M, which needs 8 ms, becomes ready at t = 3 ms. With a binary semaphore:

$$t_{\text{H done}} = 3 + \underbrace{8}_{\text{M}} + \underbrace{2}_{\text{rest of L}} + \underbrace{1}_{\text{H inside}} = 14\ \text{ms}$$

a response of 14 − 2 = 12 ms after H became ready, past its 10 ms deadline. With a priority-inheritance mutex, L runs at H’s priority from t = 3 to t = 5, H finishes at 6 ms, and M runs afterwards:

$$R_{\text{H}} = 1 + 2 + 1 = 4\ \text{ms}$$

H’s blocking is now 2 ms, the remaining part of L’s critical section, whatever M does. The scheduler-lock version gives the same 4 ms here, but H also cannot start its first, unrelated millisecond until L leaves the critical section.