In 1997, a spacecraft on Mars kept resetting itself. A high-priority task needed a shared resource held by a low-priority task, and the low-priority task could not finish because medium-priority tasks kept running ahead of it. The high-priority task stopped making progress until a watchdog reset the whole system. The same pattern appears in hardware, wherever a shared resource can be held while priorities decide who runs.
How can a high-priority requester end up waiting behind a low-priority one, and how is it prevented?
The obvious defence for urgent traffic is high priority: give it precedence at every arbiter and it can never be held up for long. That works as long as the urgent requester only competes for arbitration. As soon as it needs a resource that someone else already holds (a locked bus, a semaphore, a buffer slot, an open burst), priority at the arbiter no longer helps. It must wait for the holder, and the holder runs at its own, low priority.
The effect is that high priority waits for medium priority, the inversion. The wait is unbounded if medium traffic can keep winning.
Held resource | Inversion |
|---|---|
A locked bus sequence | A low-priority master holds the bus for a read-modify-write; the processor's urgent accesses wait for the whole sequence |
A shared buffer or tracker slot | Low-priority requests fill a target's queue; a high-priority request must wait for them to drain, at their priority |
An in-progress burst | A long low-priority burst holds a link; urgent traffic waits for it to finish (lesson 8.5) |
A software lock in shared memory | The classic case, as in the opening story |
Fix | How it works | Cost |
|---|---|---|
Priority inheritance | While a high-priority requester waits on a holder, the holder runs at the high priority | Tracking who waits on whom |
Priority escalation (QoS promotion) | In a fabric, raise the priority of transactions ahead of urgent ones in a queue, so the queue drains faster | Logic to detect the urgent waiter |
Bounded holds | Limit lock length, burst length and queue share per requester, so any hold ends in bounded time | Some throughput |
No holds | Replace locks with exclusive accesses or far atomics, which never hold the path (lesson 5.13) | Retries, or atomic logic at the target |
Reserved resources | Keep queue slots or buffers that only urgent traffic may use | Some capacity idle |
AXI4 removed locked transfers, so a requester cannot hold the interconnect for a read-modify-write; exclusive accesses detect interference instead.
Real-time operating systems provide mutexes with priority inheritance; the opening spacecraft was fixed by enabling it on the mutex involved.
QoS-aware interconnects can promote the priority of transactions that block urgent ones, and reserve queue slots for high-priority classes (lesson 8.7).
The Mars Pathfinder lander (1997): a low-priority meteorological task held a mutex that the high-priority bus-management task needed, while medium-priority communications tasks kept running. The bus task missed its deadline, a watchdog noticed, and the system reset, repeatedly. Priority inheritance had been switched off on that mutex. Engineers reproduced the fault on a ground replica, found it in the trace, and enabled inheritance with an update.
Because it is waiting for a resource that is already held, not for arbitration; the holder must finish first, and it runs at its own lower priority.
They never hold the path or target: an exclusive pair either succeeds or fails and retries, so nobody waits behind a holder.
Priority inversion: an urgent requester waits on a low-priority holder, which waits behind medium traffic.
It appears in hardware wherever a resource can be held: locks, bursts, queue slots, trackers.
Fix with inheritance or escalation, bounded holds, reserved resources, or by removing holds altogether.