Priority Inversion and Windows NT Scheduler (96418)

SUMMARY

The kernel schedules a thread with the real-time process priority class ahead of every thread with another priority class (nearly all user-mode threads). Windows NT does not alter the priority of real-time threads. The system trusts that the programmer will avoid priority inversion. The remainder of this article talks about the scheduling of threads that are not real-time priority class and how the system solves the problem of priority inversion.

Threads are scheduled according to their priority. When the kernel is choosing which thread will execute on a processor, the highest dynamic (variable) priority thread is picked. 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 is high priority and becomes ready to be scheduled, while thread 2, a low-priority thread, is executing in a critical section. Thread 1, the high-priority thread, begins waiting for a shared resource from thread 2. A third thread has medium priority. The third thread receives all the processor time, because the high-priority thread (thread 1) is busy waiting for shared resources from the low-priority thread (thread 2). Thread 2 won't leave the critical section, because it isn't the highest priority thread and won't be scheduled.

The Windows NT scheduler solves this problem by randomly boosting the priority of threads that are ready to run (in this case the low priority lock-holders). The low priority threads run long enough to let go of their lock (exit the critical section), and the high- priority thread gets the lock back. If the low-priority thread doesn't get enough CPU time to free its lock the first time, it will get another chance on the next scheduling round.

Priority inversion is handled differently in Windows 95. If a high priority thread is dependent on a low priority thread which 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 and will boost the low priority thread's priority up to the priority of the high priority thread. This will allow the formerly low priority thread to run and unblock the high priority thread that was waiting on it.

MORE INFORMATION

Each Process has a base priority. Each thread has a base priority that is a function of its process base priority. A thread's base priority is settable to:

1 or 2 points above the process base
equal to the process base
1 or 2 points below the process base

Priority setting is exposed through the Win32 API. In addition to a base priority, all threads have a dynamic priority. The dynamic priority is never less than the base priority. The system raises and lowers the dynamic priority of a thread as needed.

All scheduling is done strictly by priority. The scheduler chooses the highest priority thread which is ready to run. On a multi-processor (MP) system, the highest N runnable threads run (where N is the number of processors). The thread priority used to make these decisions is the dynamic priority of the thread.

When a thread is scheduled, it is given a quantum of time in which to run. The quantum is in units of clock ticks. The system currently uses 2 units of quantum (10ms on r4000 and 15ms on x86).

When a thread is caught running during the clock interrupt, its quantum is decremented by one. If the quantum goes to zero and the thread's dynamic priority is not at the base priority, the thread's dynamic priority is decremented by one and the thread's quantum is replenished. If a priority change occurs, then the scheduler locates the highest priority thread which is ready to run. Otherwise, the thread is placed at the end of the run queue for it's priority allowing threads of equal priority to be "round robin" scheduled. The above is a description of what is usually called priority decay, or quantum and priority decay.

When a thread voluntarily waits (an an event, for I/O, etc), the system will usually raise the thread's dynamic priority when it resumes. Internally, each wait type has an associated priority boost. For example, a wait associated with disk I/O has a one point dynamic boost. A wait associated with a keyboard I/O has a 5 point dynamic boost. In most cases, this boost will raise the priority of the thread such that it can be scheduled very soon afterwards, if not immediately.

There are other circumstances under which priority will be raised. For example, whenever a window receives input (timer messages, mouse move messages, etc), an appropriate boost is given to all threads within the process that owns the window. This is the boost that allows a thread to reshape the mouse pointer when the mouse moves over a window.

By default, the foreground application has a base process priority that is one point higher than the background application. This allows the foreground process to be even more responsive. This can be changed by bringing up the System applet, selecting the Tasking button, and choosing a different option.