Priority Inversion and Windows NT Scheduler

This article was previously published under Q96418
This article has been archived. It is offered "as is" and will no longer be updated.
The kernel schedules a thread with the real-time process priority classahead of every thread with another priority class (nearly all user-modethreads). Windows NT does not alter the priority of real-time threads. Thesystem trusts that the programmer will avoid priority inversion. Theremainder of this article talks about the scheduling of threads that arenot real-time priority class and how the system solves the problem ofpriority inversion.

Threads are scheduled according to their priority. When the kernel ischoosing 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 bescheduled. Consider a simple case with three threads: Thread 1 is highpriority and becomes ready to be scheduled, while thread 2, a low-prioritythread, is executing in a critical section. Thread 1, the high-prioritythread, begins waiting for a shared resource from thread 2. A third threadhas medium priority. The third thread receives all the processor time,because the high-priority thread (thread 1) is busy waiting for sharedresources from the low-priority thread (thread 2). Thread 2 won't leave thecritical section, because it isn't the highest priority thread and won't bescheduled.

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

Priority inversion is handled differently in Windows 95. If a high prioritythread is dependent on a low priority thread which will not be allowed torun because a medium priority thread is getting all of the CPU time, thesystem recognizes that the high priority thread is dependent on the lowpriority thread and will boost the low priority thread's priority up to thepriority of the high priority thread. This will allow the formerly lowpriority thread to run and unblock the high priority thread that waswaiting on it.
Each Process has a base priority. Each thread has a base priority that is afunction of its process base priority. A thread's base priority is settableto:

  • 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 basepriority, all threads have a dynamic priority. The dynamic priority isnever less than the base priority. The system raises and lowers the dynamicpriority of a thread as needed.

All scheduling is done strictly by priority. The scheduler chooses thehighest priority thread which is ready to run. On a multi-processor (MP)system, the highest N runnable threads run (where N is the number ofprocessors). The thread priority used to make these decisions is thedynamic 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 unitsof quantum (10ms on r4000 and 15ms on x86).

When a thread is caught running during the clock interrupt, its quantum isdecremented by one. If the quantum goes to zero and the thread's dynamicpriority is not at the base priority, the thread's dynamic priority isdecremented by one and the thread's quantum is replenished. If a prioritychange occurs, then the scheduler locates the highest priority thread whichis ready to run. Otherwise, the thread is placed at the end of the runqueue for it's priority allowing threads of equal priority to be "roundrobin" scheduled. The above is a description of what is usually calledpriority decay, or quantum and priority decay.

When a thread voluntarily waits (an an event, for I/O, etc), the systemwill usually raise the thread's dynamic priority when it resumes.Internally, each wait type has an associated priority boost. For example, await associated with disk I/O has a one point dynamic boost. A waitassociated 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 bescheduled very soon afterwards, if not immediately.

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

By default, the foreground application has a base process priority that isone point higher than the background application. This allows theforeground process to be even more responsive. This can be changed bybringing up the System applet, selecting the Tasking button, and choosing adifferent option.
3.10 3.50

Article ID: 96418 - Last Review: 02/28/2014 00:25:46 - Revision: 3.1

  • Microsoft Win32 Application Programming Interface
  • kbnosurvey kbarchive KB96418