Priority Inversion

Priority inversion occurs when two or more threads with different priorities are in contention to be scheduled. Consider a simple case with three threads: thread 1, thread 2, and thread 3. Thread 1 is high priority and becomes ready to be scheduled. Thread 2, a low-priority thread, is executing code in a critical section. Thread 1, the high-priority thread, begins waiting for a shared resource from thread 2. Thread 3 has medium priority. Thread 3 receives all the processor time, because the high-priority thread (thread 1) is waiting for shared resources from the low-priority thread (thread 2). Thread 2 won't leave the critical section, because does not have the highest priority and won't be scheduled.

• Windows NT/2000: The scheduler solves this problem by randomly boosting the priority of the ready threads (in this case, the low priority lock-holders). The low priority threads run long enough to exit the critical section, and the high- priority thread can enter the critical section. If the low-priority thread doesn't get enough CPU time to exit the critical section the first time, it will get another chance during the next round of scheduling.
• Windows 95: If a high-priority thread is dependent on a low-priority thread that will not be allowed to run because a medium priority thread is getting all of the CPU time, the system recognizes that the high-priority thread is dependent on the low-priority thread. It will boost the low-priority thread's priority up to the priority of the high-priority thread. This will allow the thread that formerly had the lowest priority to run and release the high-priority thread that was waiting for it.