Priority Inversion
A version of this page is also available for
4/8/2010
Priority inversion occurs when a mutex or critical section held by a lower-priority thread delays the running of a higher-priority thread when both are contending for the same resource.
For mutexes and critical sections, to correct this situation and free the higher-priority thread, with priority inheritance, Windows Mobile enables the lower-priority thread to inherit the more critical thread's priority and run at the higher priority until it releases its use of the resource. Priority inheritance does not apply to semaphores, which do not have a specific owner associated with them.
Because an unbounded amount of time is needed to relinquish the inverted thread and it is out of the control of the kernel, the OEM loses control of the scheduling process. To guarantee real-time performance, OEMs should ensure that a priority inversion condition does not occur.
Consider an example that shows how a system without priority inheritance could lead to poor thread scheduling.
Suppose an application has three threads:
- Thread 1 has high priority.
- Thread 2 has medium priority.
- Thread 3 has low priority.
Thread 1 and thread 2 are sleeping or blocked at the beginning of the example. Thread 3 runs and enters a critical section.
At that moment, thread 2 starts running, preempting thread 3 because thread 2 has a higher priority. So, thread 3 continues to own a critical section.
Later, thread 1 starts running, preempting thread 2. Thread 1 tries to enter the critical section that thread 3 owns, but because it is owned by another thread, thread 1 blocks, waiting for the critical section.
At that point, thread 2 starts running because it has a higher priority than thread 3 and thread 1 is not running. Thread 3 nevers release the critical section that thread 1 is waiting for because thread 2 continues to run.
Therefore, the highest-priority thread in the system, thread 1, becomes blocked waiting for lower-priority threads to run.
To resolve this issue, Windows Mobile enables priority inheritance to a depth of one level.
In the preceding example, when thread 1 is blocked as it waits for thread 3 to complete, Windows Mobile increases the priority of thread 3. Therefore, thread 3 runs and eventually releases the shared resource to thread 1.
After the shared resource is released by thread 3, Windows Mobile restores thread 3 to its original priority, and thread 1 runs.
However, if thread 3 is blocked and waiting for another thread, X, to release an object, Windows Mobile does not boost the priority of thread X, which might be the lowest priority thread.
If the priority of a thread is inverted, the thread receives a fresh quantum, or slice, of execution time when its priority is no longer inverted.
Note
Abandon waiting for mutex causes threads blocking the mutex to keep the inherited priority. When a lower priority thread holds a mutex, and a higher priority thread that is waiting for the mutex stops waiting because it has timed out or another object signaled using the WaitForMultipleObjects function, the lower-priority thread inherits the priority of the higher-priority thread until it starts running again. This is usually not a problem, unless the lower priority thread is also blocked by another object when the wait is abandoned. Avoid priority inversion by keeping all threads waiting for the mutex at the same priority, or by setting the timeout to INFINITE for threads that are waiting for the mutex.
Threads run for a specific amount of time called a quantum, or slice, of execution time. This has a default value of 100 milliseconds.