Priority inversion, mutexes and deadlock

A preemptive priority scheduler makes one promise: the highest-priority ready task runs. The promise says nothing about tasks that are blocked — and a high-priority task blocked on a lock held by a low-priority task is not ready. From that gap come the bugs this lesson is about: priority inversion (a high-priority task waits for lower-priority ones), and deadlock (tasks wait for each other forever). Both are interview staples for firmware roles, and both have caused real field failures.

You've met tasks, priorities, queues and timeouts in rtos-tasks-and-queues. Here the shared thing is a resource that one task at a time may use — a bus, a peripheral, a buffer — and the question is what guards it.

Every snippet runs FreeRTOS V11 on the emulated Cortex-M4 (mps2-an386), with a 1 kHz tick. The emulator runs with -icount, so tick counts are deterministic: the same program prints the same schedule every time, which makes schedules easy to reason about and to test. That is emulated time, not a hardware deadline — it says nothing about a real board's interrupt latency, flash wait states or caches, and running here is not hardware-in-the-loop testing.

The snippets use one helper: work(n) burns n ticks of running time — CPU-bound work, like a computation or a bus transfer that polls. If the task is preempted, the ticks it spends waiting don't count.

1. Bounded and unbounded inversion

Three tasks: L (priority 1) uses a shared bus for 10 ticks; H (priority 3) needs the bus briefly; M (priority 2) doesn't use the bus at all but computes for 30 ticks. The bus is guarded by a binary semaphore.

#include "FreeRTOS.h"
#include "semphr.h"
#include "task.h"
#include <cstdio>
#include <cstdlib>

static SemaphoreHandle_t bus;
static TickType_t base;
static TickType_t now() { return xTaskGetTickCount() - base; }
static void work(TickType_t n) {  // n ticks of running time
    TickType_t last = xTaskGetTickCount();
    while (n) {
        TickType_t t = xTaskGetTickCount();
        if (t != last) { last = t; --n; }
    }
}

static void low(void*) {
    TickType_t w = base; xTaskDelayUntil(&w, 1);
    xSemaphoreTake(bus, portMAX_DELAY);
    std::printf("%2lu L takes the bus\n", now());
    work(10);
    std::printf("%2lu L gives it (priority %lu)\n", now(), uxTaskPriorityGet(nullptr));
    xSemaphoreGive(bus);
    vTaskDelete(nullptr);
}
static void med(void*) {
    TickType_t w = base; xTaskDelayUntil(&w, 4);
    std::printf("%2lu M starts computing\n", now());
    work(30);
    std::printf("%2lu M done\n", now());
    vTaskDelete(nullptr);
}
static void high(void*) {
    TickType_t w = base; xTaskDelayUntil(&w, 3);
    std::printf("%2lu H wants the bus\n", now());
    xSemaphoreTake(bus, portMAX_DELAY);
    std::printf("%2lu H takes it\n", now());
    work(2);
    xSemaphoreGive(bus);
    std::printf("%2lu H done\n", now());
    std::exit(0);
}

int main() {
    bus = xSemaphoreCreateBinary();
    xSemaphoreGive(bus);  // a binary semaphore starts empty
    xTaskCreate(low, "L", 512, nullptr, 1, nullptr);
    xTaskCreate(med, "M", 512, nullptr, 2, nullptr);
    xTaskCreate(high, "H", 512, nullptr, 3, nullptr);
    vTaskStartScheduler();
}

It prints:

 1 L takes the bus
 3 H wants the bus
 4 M starts computing
34 M done
41 L gives it (priority 1)
41 H takes it
43 H done

Two kinds of waiting are mixed here:

• Bounded inversion — H waiting for L to finish its critical section. That's inherent in sharing a resource, and it is bounded by the length of L's critical section. Ticks 3–4 and 34–41 are this kind.
• Unbounded inversion — H waiting for M, a task that doesn't even use the resource, just because M outranks L. Ticks 4–34. Its length depends on how much medium-priority work happens to arrive, so no analysis of the bus code can bound it. Give M 300 ticks of work and H waits 300 ticks.

The schedule is perfectly legal — at every instant, the highest-priority ready task runs — and it's still wrong, because H's deadline now depends on M.

2. Mars Pathfinder, 1997

The best-known case. Pathfinder landed on Mars on 4 July 1997; a few days later it started resetting itself, losing data each time. Its flight software ran on the VxWorks RTOS. Mike Jones summarised a talk by Wind River's David Wilner about it, and Glenn Reeves, who led the spacecraft's software team at JPL, replied with a detailed account. In Jones's simplified version:

• An information bus — shared memory for passing data between components — was guarded by a mutex.
• A high-priority bus management task ran frequently, moving data in and out of the bus.
• A low-priority meteorological task published its data through the bus, holding the mutex while it wrote.
• A medium-priority communications task ran for long stretches.

Rarely, the communications task became ready in the short window while the bus task was blocked on the mutex held by the meteorological task — the schedule from section 1. The bus task then missed its deadline; a timing check noticed that the bus cycle hadn't completed and reset the whole spacecraft. (Reeves's account adds detail: the high-priority task was the one distributing 1553-bus data, the mutex was inside VxWorks' select() mechanism for the pipes the tasks communicated through, and the reset came from the bus scheduler task finding that the distribution task hadn't finished its cycle.)

The engineers reproduced it on an identical replica in the lab with VxWorks' event trace enabled, and the trace showed the inversion. The mutex had been created with priority inheritance off — a creation option in VxWorks. The fix was to turn it on: the parameters were global variables, and a short C program uploaded to the spacecraft and run by VxWorks' on-board interpreter changed them. The resets stopped.

The lessons are the ones you'll be asked about in interviews:

1. It was found from a trace, not by inspection: record who held what, and when.
2. The fix was a lock property, not a scheduling change.
3. It needed load to appear. Reeves writes that it only showed when meteorological data was being collected while medium-priority tasks were heavily loaded, and that pre-launch testing hadn't covered the higher data rates seen on the surface. Per Wilner's talk, one or two unexplained resets in pre-flight testing had been put down to hardware glitches. An unexplained reset is a bug report.

3. Binary semaphore or mutex?

In FreeRTOS both are made by xSemaphoreCreate… and used with xSemaphoreTake / xSemaphoreGive, so they look interchangeable. They are not:

A binary semaphore is the right tool when the giver and the taker are different parties — an interrupt handler telling a task that data arrived (where a direct-to-task notification is usually lighter still). For guarding a resource, use a mutex: inheritance only works because the kernel knows who holds the lock, and only a mutex records that.

4. Priority inheritance

Change one line — bus = xSemaphoreCreateMutex();, without the initial give — and run the same three tasks:

#include "FreeRTOS.h"
#include "semphr.h"
#include "task.h"
#include <cstdio>
#include <cstdlib>

static SemaphoreHandle_t bus;
static TickType_t base;
static TickType_t now() { return xTaskGetTickCount() - base; }
static void work(TickType_t n) {
    TickType_t last = xTaskGetTickCount();
    while (n) {
        TickType_t t = xTaskGetTickCount();
        if (t != last) { last = t; --n; }
    }
}

static void low(void*) {
    TickType_t w = base; xTaskDelayUntil(&w, 1);
    xSemaphoreTake(bus, portMAX_DELAY);
    std::printf("%2lu L takes the bus\n", now());
    work(10);
    std::printf("%2lu L gives it (priority %lu)\n", now(), uxTaskPriorityGet(nullptr));
    xSemaphoreGive(bus);
    vTaskDelete(nullptr);
}
static void med(void*) {
    TickType_t w = base; xTaskDelayUntil(&w, 4);
    std::printf("%2lu M starts computing\n", now());
    work(30);
    std::printf("%2lu M done\n", now());
    std::exit(0);
}
static void high(void*) {
    TickType_t w = base; xTaskDelayUntil(&w, 3);
    std::printf("%2lu H wants the bus\n", now());
    xSemaphoreTake(bus, portMAX_DELAY);
    std::printf("%2lu H takes it\n", now());
    work(2);
    xSemaphoreGive(bus);
    std::printf("%2lu H done\n", now());
    vTaskDelete(nullptr);
}

int main() {
    bus = xSemaphoreCreateMutex();
    xTaskCreate(low, "L", 512, nullptr, 1, nullptr);
    xTaskCreate(med, "M", 512, nullptr, 2, nullptr);
    xTaskCreate(high, "H", 512, nullptr, 3, nullptr);
    vTaskStartScheduler();
}

 1 L takes the bus
 3 H wants the bus
11 L gives it (priority 3)
11 H takes it
13 H done
13 M starts computing
43 M done

When H blocks on the mutex, the kernel raises the holder's priority to H's. L now runs at 3; at tick 4 M becomes ready but no longer outranks L, so it waits. L gives the mutex at tick 11, drops back to 1 in the same call, and H — now the highest ready task — takes over. H finishes at 13 instead of 43. M still does all its work; it just does it after H, which is what the priorities asked for.

How FreeRTOS does it (it's all in tasks.c: xTaskPriorityInherit, xTaskPriorityDisinherit, vTaskPriorityDisinheritAfterTimeout):

• A task that blocks on a held mutex raises the holder to its own priority if that is higher.
• When the holder gives the mutex back, it returns to its base priority — but only once it holds no mutexes at all. A task holding two mutexes keeps an inherited priority until it has released both (a simplification that can keep it high for longer than needed).
• If the waiter's timeout expires, the holder is lowered again to the highest priority among the tasks still waiting (or its base). You'll predict this one in the check items.

5. What inheritance doesn't fix

Inheritance turns unbounded inversion into bounded inversion. It is not a cure-all — the FreeRTOS book's own advice is that it lessens inversion's impact but complicates timing analysis, and that it isn't good practice to rely on it for correct operation:

• The bound is the critical-section length. H still waits for the whole of L's section. A section that does a slow transfer, logs with printf, or blocks on something else while holding the lock makes that bound long. Keep sections short — section 8.
• Chains. If L holds A, M holds B and waits for A, and H waits for B, the real bound is the sum of both sections, and the boost must travel along the chain. FreeRTOS's implementation is deliberately simple and doesn't propagate it:

#include "FreeRTOS.h"
#include "semphr.h"
#include "task.h"
#include <cstdio>
#include <cstdlib>

static SemaphoreHandle_t a, b;
static TaskHandle_t lh, mh;

static void low(void*) {                 // priority 1
    xSemaphoreTake(a, portMAX_DELAY);
    vTaskDelay(5);                       // holds A for a while
    xSemaphoreGive(a);
    vTaskDelete(nullptr);
}
static void mid(void*) {                 // priority 2
    vTaskDelay(1);
    xSemaphoreTake(b, portMAX_DELAY);
    xSemaphoreTake(a, portMAX_DELAY);    // blocks: L holds A, L inherits 2
    xSemaphoreGive(a);
    xSemaphoreGive(b);
    vTaskDelete(nullptr);
}
static void high(void*) {                // priority 4
    vTaskDelay(2);
    xSemaphoreTake(b, portMAX_DELAY);    // blocks: M holds B, M inherits 4
    xSemaphoreGive(b);
    vTaskDelete(nullptr);
}
static void spy(void*) {                 // priority 5: looks while H waits
    vTaskDelay(3);
    std::printf("H (4) waits for M, M waits for L: M runs at %lu, L at %lu\n",
                uxTaskPriorityGet(mh), uxTaskPriorityGet(lh));
    std::exit(0);
}

int main() {
    a = xSemaphoreCreateMutex();
    b = xSemaphoreCreateMutex();
    xTaskCreate(low, "L", 512, nullptr, 1, &lh);
    xTaskCreate(mid, "M", 512, nullptr, 2, &mh);
    xTaskCreate(high, "H", 512, nullptr, 4, nullptr);
    xTaskCreate(spy, "spy", 512, nullptr, 5, nullptr);
    vTaskStartScheduler();
}

H (4) waits for M, M waits for L: M runs at 4, L at 2

L, whose section H is really waiting for, still runs at 2: any task at priority 3 could preempt it and delay H without bound. The fix isn't a smarter kernel — it's not nesting locks in code that high-priority tasks depend on.

• Deadlock. Inheritance changes priorities, not who holds what; a cycle of waits stays a cycle — section 6.
• Interrupts. An ISR can't take a mutex, so nothing an ISR waits on can inherit.

The priority ceiling idea

The alternative is to decide priorities before anyone blocks. Give each lock a ceiling: the highest priority of any task that ever uses it. Under the immediate ceiling protocol (also called highest locker), a task that takes the lock is raised to the ceiling at once and stays there until it releases. In section 1, L would run at 3 from tick 1: M can never preempt a holder, H is delayed by at most one critical section, chains can't form, and on a single core — if holders never block while holding a lock — locks sharing a ceiling can't deadlock either. The price: the holder is boosted even when nobody is waiting, and the ceiling must be maintained as tasks change.

FreeRTOS mutexes don't implement ceilings. You can get the effect by hand:

// Every user of the bus has priority <= kBusCeiling.
void with_bus(void (*fn)()) {
    UBaseType_t mine = uxTaskPriorityGet(nullptr);
    vTaskPrioritySet(nullptr, kBusCeiling);   // from here on, no other bus user can preempt us
    if (xSemaphoreTake(bus, pdMS_TO_TICKS(20)) == pdTRUE) {
        fn();
        xSemaphoreGive(bus);
    }
    vTaskPrioritySet(nullptr, mine);
}

— or remove the shared lock altogether with a gatekeeper task: one task owns the bus, and everyone else sends it requests through a queue. Only the gatekeeper touches the hardware, so there's nothing to invert or deadlock on; the gatekeeper's priority decides how quickly requests are served. The Mastering the FreeRTOS Real Time Kernel book describes the pattern, with a gatekeeper that owns standard output as its example.

6. Deadlock

Deadlock needs four conditions at once (Coffman et al., 1971): mutual exclusion (the resource has one user), hold and wait (a task holds one lock while waiting for another), no preemption (locks can't be taken away), and a circular wait. Break any one and deadlock is impossible. The practical lever is the last one:

Lock ordering: give every lock a rank and always take locks in increasing rank. A task waiting for a lock then only waits for tasks holding higher locks than everything it holds, so the waits can't close into a cycle. Here both tasks run the same code, once with opposite orders and once with one order:

#include "FreeRTOS.h"
#include "semphr.h"
#include "task.h"
#include <cstdio>
#include <cstdlib>

static SemaphoreHandle_t a, b, done;
static TickType_t base;
struct Order { const char* name; SemaphoreHandle_t first, second; };

static void worker(void* p) {
    auto* o = static_cast<Order*>(p);
    xSemaphoreTake(o->first, portMAX_DELAY);
    vTaskDelay(1);  // something slow while holding the first lock
    if (xSemaphoreTake(o->second, pdMS_TO_TICKS(50)) == pdTRUE) {
        std::printf("%3lu %s: got both\n", xTaskGetTickCount() - base, o->name);
        xSemaphoreGive(o->second);
    } else {
        std::printf("%3lu %s: timed out waiting for its second lock\n", xTaskGetTickCount() - base, o->name);
    }
    xSemaphoreGive(o->first);
    xSemaphoreGive(done);
    vTaskDelete(nullptr);
}

static void run(Order* x, Order* y) {
    base = xTaskGetTickCount();
    xTaskCreate(worker, "x", 512, x, 3, nullptr);
    xTaskCreate(worker, "y", 512, y, 3, nullptr);
    xSemaphoreTake(done, portMAX_DELAY);
    xSemaphoreTake(done, portMAX_DELAY);
}

static void main_task(void*) {
    Order ab{"T1 (a, b)", a, b}, ba{"T2 (b, a)", b, a}, ab2{"T2 (a, b)", a, b};
    std::puts("opposite orders:");
    run(&ab, &ba);
    std::puts("one global order:");
    run(&ab, &ab2);
    std::exit(0);
}

int main() {
    a = xSemaphoreCreateMutex();
    b = xSemaphoreCreateMutex();
    done = xSemaphoreCreateCounting(2, 0);
    xTaskCreate(main_task, "main", 1024, nullptr, 2, nullptr);
    vTaskStartScheduler();
}

opposite orders:
 51 T1 (a, b): timed out waiting for its second lock
 51 T2 (b, a): got both
one global order:
  1 T1 (a, b): got both
  2 T2 (a, b): got both

With opposite orders each task holds one lock and waits for the other; only the timeout breaks the cycle, 50 ticks later, by making T1 give up and release a. Timeouts don't prevent deadlock — they turn a silent hang into a failure you can report, retry or escalate (a stuck system is exactly what a watchdog then resets). With one global order, T2 simply waits for a and runs right after T1.

Practical rules:

• Rank locks (by layer, by an id, by address for instances of one class) and document the order.
• Release in the reverse order, and on a failed second take, release the first before returning.
• Don't call out to unknown code (callbacks, other modules' APIs) while holding a lock: you don't know what it locks.
• Prefer designs that hold one lock at a time — or a gatekeeper task that owns the resource.

7. Recursive mutexes

A FreeRTOS mutex taken twice by the same task blocks on itself: the second take waits for the holder — the caller — to give it, which can't happen. (With a timeout, it fails after the timeout.) That shows up when a locked public function calls another locked public function on the same object.

A recursive mutex (xSemaphoreCreateRecursiveMutex, xSemaphoreTakeRecursive, xSemaphoreGiveRecursive) counts: the holder may take it again, and it is released when the number of gives matches the takes. It keeps priority inheritance.

#include "FreeRTOS.h"
#include "semphr.h"
#include "task.h"
#include <cstdio>
#include <cstdlib>

static SemaphoreHandle_t plain, rec;

static void t(void*) {
    xSemaphoreTake(plain, 0);
    TickType_t t0 = xTaskGetTickCount();
    BaseType_t again = xSemaphoreTake(plain, 5);
    std::printf("plain mutex, second take: %ld after %lu ticks\n", again, xTaskGetTickCount() - t0);

    xSemaphoreTakeRecursive(rec, 0);
    t0 = xTaskGetTickCount();
    again = xSemaphoreTakeRecursive(rec, 5);
    std::printf("recursive mutex, second take: %ld after %lu ticks\n", again, xTaskGetTickCount() - t0);
    xSemaphoreGiveRecursive(rec);
    std::printf("after one give, holder is still me: %d\n", xSemaphoreGetMutexHolder(rec) == xTaskGetCurrentTaskHandle());
    xSemaphoreGiveRecursive(rec);
    std::printf("after two gives, held: %d\n", xSemaphoreGetMutexHolder(rec) != nullptr);
    std::exit(0);
}

int main() {
    plain = xSemaphoreCreateMutex();
    rec = xSemaphoreCreateRecursiveMutex();
    xTaskCreate(t, "t", 512, nullptr, 1, nullptr);
    vTaskStartScheduler();
}

Recursive mutexes are a convenience, not a design: they hide how long the lock is really held and make lock ordering harder to see. The usual alternative is to split each class into public functions that lock and private …_locked helpers that assume the lock is held, and have public functions call only the helpers. The take and give functions must match: a recursive mutex is taken with …TakeRecursive, never with plain xSemaphoreTake.

8. Keep critical sections short

FreeRTOS gives you three ways to keep other code out, from blunt to precise:

Use the critical section for a few instructions on shared data (and never call FreeRTOS API functions or block inside one), and a mutex for anything longer. Then keep the mutex section short: copy the shared data out under the lock and process the copy outside; do slow I/O, logging and printf outside; never vTaskDelay or wait on a queue while holding a lock. The length of the longest section protecting a resource is the inversion bound for every higher-priority user — and in the build task, the number that decides whether a deadline holds.

9. Seeing it: traces and deadline monitors

Pathfinder's bug was found by a trace, and that's how you find these in your own systems: log lock requests, acquisitions and releases with the tick and the task's current priority, and log each job's arrival, start, finish and deadline. A missed deadline plus a trace showing the holder at its base priority while a medium task ran is the signature of unbounded inversion.

The build task makes you do exactly that: a SharedBus guard used by three tasks, a BusTrace recording who held the bus and at what priority, and a DeadlineMonitor recording each job's start, finish and misses. The starter guards the bus with a binary semaphore and the high-priority job misses its deadline; you fix it, and the tests check the schedule tick by tick. A bridge that holds two buses at once has to take them in a fixed order.

On real hardware

What carries over unchanged is the logic: who can preempt whom, which waits are bounded and by what. What changes:

• Time is real. The tick comes from a hardware timer (SysTick or a low-power timer), and the length of a critical section depends on clock speed, flash wait states, caches and the interrupts that land in the middle. The exact tick counts here become ranges you measure.
• Measuring. Toggle a GPIO pin when a task takes and gives a lock (or when a job starts and finishes) and watch the pins on a logic analyser or oscilloscope — it shows the inversion directly, with the board's real timing. Trace tools such as SEGGER SystemView or Percepio Tracealyzer record context switches, lock operations and priority changes through FreeRTOS's trace hooks, which is the same evidence Pathfinder's engineers used.
• Watchdogs. A hardware watchdog resets the chip when the code stops kicking it — the Pathfinder resets were that kind of mechanism doing its job. It recovers from the symptom; the trace finds the cause.
• Worst cases, not typical ones. Inversion bugs live in rare interleavings. A thousand clean test runs don't show a bound; an analysis of the longest critical section per lock (plus the measurement above) does.