Inside the Windows NT Scheduler, Part 1

Assigning CPU time in a uniprocessor environment

Windows NT is a preemptive multithreading operating system. That is, NT lets severalprograms run simultaneously and switches among them often enough to create theillusion that each program is the only program running on the machine. Well,that's the idea anyway. How to smoothly share one CPU (or multiple CPUs) amongmany threads of control is a complicated problem. Solving this problemdynamically many times per second is the job of the NT scheduler. The NTscheduler must honor the relative priorities that the application's programmersdesignate for each thread and attempt to provide responsiveness touser-interactive threads.

In this first part of a two-part series about the algorithms NT's scheduleremploys, I'll introduce basic information about the NT scheduler. (For anoverview of how NT schedules applications to run, see Christa Anderson, "ForegroundApplication Handling in NT 4.0," June 1997.) You'll find out about thepriority levels that NT assigns to threads, how Win32 programs specifypriorities for their threads, the situations that invoke the scheduler, and thealgorithms NT uses on uniprocessors in those situations. I'll wrap up with adiscussion of some advanced features of the scheduler, including priorityboosting and starvation prevention. Next month, I'll provide an in-depth tour ofhow the NT scheduler implements multiprocessor scheduling.

Threads and Priorities
The basic scheduling unit in NT is a thread. A thread is a point ofcontrol within a process. Processes consist of a virtual address spacethat includes executable instructions, a set of resources such as file handles,and one or more threads that execute within its address space. Typicalapplications consist of only one process, so program and processare often used synonymously. Most programs today are single-threaded,which means they run as one process with one thread. However, multithreadedprograms are becoming more commonplace. An example of a multithreaded program isa program that lets a user sort a list, with an option to cancel. One thread inthe program's process might perform the CPU-intensive sorting task while anotherthread in the process displays a how-to-cancel message to the user and waits fora response. The scheduler does not differentiate between threads of differentprocesses. Instead, the scheduler examines the priorities of all thethreads ready to run at a given instant to pick which thread to execute.

NT assigns each thread a priority number from 1 to 31, where higher numberssignal higher priorities. (NT uses priority 0 for the system idle thread, whichexecutes when no other thread is able to.) NT reserves priorities 16 through 31(realtime priorities) for use by time-critical operations. Only a userwith Administrator privileges can direct the system to execute threads in thisrange. NT uses priorities 1 through 15 (dynamic priorities) for theprogram threads of typical applications (e.g., Notepad, Word, Lotus Notes).

The NT kernel provides functions that let you set a thread to any of the 31priority levels, but the Win32 API is more indirect. In Win32, specifying athread's priority is a two-step process. You must first set the priorityclass of the process; then, you can apply a relative priority toindividual threads.

A process priority class is a priority level around which NT lets theprocess' threads execute. The Win32 API defines four priority classes: realtime,high, normal, and idle. These names correspond to priority levels 24, 13, 8, and4. Setting a process priority class causes all the threads of that process tobegin executing at priorities within ±2 of the class priority. This schemeis shown in Figure 1, page 168. New processes inherit the priority class oftheir parent. Process threads start at the priority level associated with theirprocess' priority class.

The relative priorities that can change a thread's priority from itsprocess class priority are highest, above normal, normal, below normal, andlowest. Highest adds 2 to the thread's priority, above normal adds 1, normaladds 0, below normal adds -1, and lowest adds -2. Figure 2, page 168, shows therelative priorities applied to the Normal priority class range.

The Win32 API includes two special-case priority modifiers: time-criticaland idle. Time-critical moves a dynamic thread's priority to the top ofthe dynamic range (15), and idle moves it to the bottom (1). Similarly,time-critical and idle move realtime threads to the top (31) and bottom (16) ofthe realtime range.

Whose Turn Is It?
Threads must take turns running on the CPU so that one thread doesn'tprevent other threads from performing work. One of the scheduler's jobs is toassign units of CPU time (quantums) to threads. A quantum is typicallyvery short in duration, but threads receive quantums so frequently that thesystem appears to run smoothly--even when many threads are performing work. Onedifference between NT Server and NT Workstation is the length of a user thread'squantum. On most x86 systems running NT Server, a quantum is 120 milliseconds(ms). On x86 systems running NT Workstation, a quantum can be 20ms, 40ms, or60ms, depending on your system settings and whether the thread is a backgroundor foreground application thread (more on this topic later).

The scheduler must make a CPU scheduling decision every time one of threesituations occurs:

*A thread's quantum on the CPU expires.

*A thread waits for an event to occur.

*A thread becomes ready to execute.

When a thread's quantum expires, the scheduler executes the FindReadyThreadalgorithm to decide whether another thread needs to take over the CPU. If ahigher-priority thread is ready to execute, it replaces (or preempts)the thread that was running.

In many cases, threads perform processing and then wait for an event tooccur. For example, a client/server application might have a server thread thatperforms processing when it receives client requests and then waits for morerequests. A waiting (or blocked) thread gives up its quantum early, andthe scheduler must execute the FindReadyThread algorithm to find a new thread torun.

When a new thread or a blocked thread becomes ready to execute (e.g., whenthe client/server application server thread receives another client request),the scheduler executes the ReadyThread algorithm. This algorithm determineswhether the ready thread will take over the CPU immediately or be placed in aneligible-to-execute list.

FindReadyThread and ReadyThread are the key algorithms the NT scheduleruses to determine how threads take turns on the CPU. The uniprocessor versionsof FindReadyThread and ReadyThread are straightforward algorithms. Let's examinehow FindReadyThread and ReadyThread work.

FindReadyThread. FindReadyThread locates thehighest-priority thread that's ready to execute. The scheduler keeps track ofall ready-to-execute threads in the Dispatcher Ready List. The Dispatcher ReadyList contains 31 entries, each of which corresponds to a priority level and aqueue of threads assigned to that priority level. The FindReadyThread algorithmscans the Dispatcher Ready List and picks the front thread in thehighest-priority nonempty queue. Figure 3 shows an example Dispatcher Ready Listwith three ready threads--two at priority 10 and one at priority 7.FindReadyThread directs the scheduler to choose the first thread in priority10's queue as the next thread to run.

ReadyThread. ReadyThread is the algorithm that placesthreads in the Dispatcher Ready List. When ReadyThread receives aready-to-execute thread, it checks to see whether the thread has a higherpriority than the executing thread. If the new thread has a higher priority, itpreempts the current thread and the current thread goes to the Dispatcher ReadyList. Otherwise, ReadyThread places the ready-to-execute thread in theappropriate Dispatcher Ready List. At the front of the queue, ReadyThread placesthreads that the scheduler pulls off the CPU before they complete at least onequantum; all other threads (including blocked threads) go to the end of thequeue.

Boosting and Decay
The picture I've presented so far is of a fairly static system: Threadsexecute at a priority level until a program changes their priorities or theyexit. What actually happens is more dynamic: In a variety of situations, NT boosts(or increases) the priority of dynamic range threads. The most common boostoccurs when an event happens that a blocked thread was waiting for. For example,a thread waiting for input from the keyboard increases six priority levels (a6-point boost) when a keystroke wakes it up. Other increases include a 6-pointboost for mouse events and a 1-point boost when a thread wakes up from a wait ona general event.

Boosting applies to only dynamic range threads. The system never changes thepriority of a realtime thread--only a program can change a realtime priority. Inaddition, a boost never causes a thread's priority to move into the realtimerange; priority level 15 is the upper limit for boosts. Event-related boosts aretemporary because the boost decays over time. Each time a thread runsthrough an entire quantum, its boost decreases by 1 point. This decay continuesuntil the thread reaches its programmed priority level (the priority it hadbefore its first boost).

NT's boosting logic lets the system boost a thread repeatedly before itspriority has decayed to its base priority. Thus, a priority 8 thread thatreceives keyboard input gets boosted to priority 14. If the thread completes aquantum, its priority decays to 13. If the thread waits for and receives anotherkeyboard event, its priority gets boosted to the 15 limit.

Another type of boost NT Workstation applies is a foreground applicationboost, which you can control from the Performance tab of the System applet inControl Panel (shown in Screen 1). This type of boost affects quantum length,rather than priority. For the default Maximum setting, NT extends the quantumsof foreground application threads to 60ms. If you position the slider in themiddle, NT sets the quantums to 40ms. If you position the slider on None, thequantums are 20ms--the same as the quantums of background application threads.

Starvation Prevention
Left alone, the FindReadyThread and ReadyThread might prevent low-prioritythreads from getting a chance to execute. For example, a priority 4 threadrunning on a system with continuously running priority 8 threads would bestarved for CPU time. However, NT provides a mechanism that gives low-prioritythreads a shot at the CPU. The NT Balance Set Manager is a system thread thatwakes up every second or so to perform memory tuning. As a secondaryresponsibility, Balance Set Manager executes the ScanReadyQueues algorithm,which implements NT's anti-CPU starvation policy.

ScanReadyQueues scans the Dispatcher Ready List, working down the list frompriority 31. It looks for threads that haven't executed in more than 3 seconds.When it finds one, ScanReadyQueues gives the thread a special anti-starvationboost, doubles its quantum, and calls ReadyThread with the thread as aparameter. The anti-starvation boost differs from other boosts: Instead ofapplying a relative priority increment, the anti-starvation boost slams thethread's priority to the top of the dynamic range. (On pre-Service Pack2--SP2--systems, the anti-starvation boost was to priority 14; post-SP2 systemsboost to priority 15). When a thread that receives an anti-starvation boostfinishes its extended quantum (or the thread blocks), its priority returns tothe pre-starvation boost level and its quantum returns to its usual length.

Next Month
Scheduling in a uniprocessor environment is relatively straightforward, butfactors within a multiprocessor environment complicate how FindReadyThread andReadyThread work. For example, NT lets applications define threads toexecute on only certain CPUs, and NT tries to keep threads running on the sameCPU for performance benefits. Next month, I'll describe the multiprocessorimplementations of FindReadyThread and ReadyThread. These algorithms arecomplex--so complex that you might argue that a better way must exist forscheduling in a multiprocessor environment. Stay tuned.