Priority Inversion (Windows CE 5.0)
Priority inversion occurs when a mutex, critical section, or semaphore resource held by a lower-priority thread delays the execution 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 CE 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. This mechanism does not work for semaphores, which do not have a specific owner associated with them. Therefore, priority inversion may occur when using semaphores.
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 then runs and enters a critical section.
At that moment, thread 2 begins running, preempting thread 3 because thread 2 has a higher priority. So, thread 3 continues to own a critical section.
Later, thread 1 begins running, preempting thread 2. Thread 1 tries to enter the same 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 would begin running because it has a higher priority than thread 3, and thread 1 is not running. Thread 3 would never release the critical section that thread 1 is waiting on because thread 2 would continue running.
So, the highest-priority thread in the system, thread 1, becomes blocked waiting for lower-priority threads to execute.
To resolve the threading issue, Windows CE 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 CE boosts the priority of thread 3. When the priority of thread 3 is boosted, it runs and eventually releases the shared resource to thread 1.
After the shared resource is released by thread 3, Windows CE restores thread 3 to its original priority and thread 1 then runs.
However, if thread 3 is blocked and waiting for another thread, X, to release an object, Windows CE 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 when its priority is no longer inverted.
Note Abandon waiting on 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 on the mutex abandons the wait (because it timed out or because 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 on another object when the wait is abandoned.
Microsoft recommends that you avoid priority inversion by keeping all threads waiting on the mutex at the same priority, or by setting the timeout to INFINITE for threads that are waiting for the mutex.
See Also
Send Feedback on this topic to the authors