CSE Roadmap

Common tier · about 5 hours · 8 parts

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?