Part 5 of 8 · 2 min read
Priority inversion
In plain words: Priority inversion appears when threads of different priorities share a lock. A low-priority thread L holds a lock. A high-priority thread H needs it, and waits. A medium-priority thread M, which does not use the lock, becomes ready and takes the processor from L, since M outranks L. Now H waits for L, and L cannot run because of M. The medium thread has indirectly delayed the high one, and the priorities are inverted.
The test below used real-time priorities (SCHED_FIFO), all threads pinned to one processor. L (priority 10) takes the lock and needs 0.2 s of processor time inside it. H (priority 30) asks for the lock 0.05 s later. M (priority 20) becomes ready at 0.1 s and uses 1 s of processor time. Measured:
| Mutex type | How long H waited for the lock |
|---|---|
| Normal | 1.200 s and 1.213 s (two runs) |
PTHREAD_PRIO_INHERIT |
0.157 s and 0.180 s (two runs) |
Without inheritance, L could not finish its last 0.1 s of work until M was done, so H waited more than a second for a lock that is held for 0.2 s of work. With priority inheritance, the kernel raises the priority of the lock holder to that of the highest waiting thread. L ran at priority 30 while H waited, M could not preempt it, and H waited only for the remaining 0.15 s of L's work. The setting is one line, pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_INHERIT).
The case became famous in July 1997, when the Mars Pathfinder lander began to reset itself a few days after landing. A low-priority weather task held a mutex that a high-priority bus-management task needed, and medium-priority tasks kept the weather task from running. A watchdog saw the bus task miss its deadline and reset the computer. The engineers reproduced it on an identical machine on Earth, and fixed it by sending a command that turned on priority inheritance for that mutex.
Priority inversion
Priority inversion is a situation in which a high-priority thread is delayed by a lower-priority thread that holds a lock it needs, and a thread of medium priority delays the lock holder, so that the effective order of priorities is reversed.
Example: thread H waited 1.2 s for a lock that was held by thread L while thread M used the processor.
Check yourself:
1. In the test, why could L not run while M was ready?
2. What does priority inheritance do while H waits?
3. Which line of code switches it on for a POSIX mutex?