Inside the Windows NT Scheduler, Part 1

Boosting and Decay
The picture I've presented so far is of a fairly static system: Threads execute at a priority level until a program changes their priorities or they exit. What actually happens is more dynamic: In a variety of situations, NT boosts (or increases) the priority of dynamic range threads. The most common boost occurs 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 (a 6-point boost) when a keystroke wakes it up. Other increases include a 6-point boost for mouse events and a 1-point boost when a thread wakes up from a wait on a general event.

Boosting applies to only dynamic range threads. The system never changes the priority of a realtime thread--only a program can change a realtime priority. In addition, a boost never causes a thread's priority to move into the realtime range; priority level 15 is the upper limit for boosts. Event-related boosts are temporary because the boost decays over time. Each time a thread runs through an entire quantum, its boost decreases by 1 point. This decay continues until the thread reaches its programmed priority level (the priority it had before its first boost).

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

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

Starvation Prevention
Left alone, the FindReadyThread and ReadyThread might prevent low-priority threads from getting a chance to execute. For example, a priority 4 thread running on a system with continuously running priority 8 threads would be starved for CPU time. However, NT provides a mechanism that gives low-priority threads a shot at the CPU. The NT Balance Set Manager is a system thread that wakes up every second or so to perform memory tuning. As a secondary responsibility, 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 from priority 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-starvation boost, doubles its quantum, and calls ReadyThread with the thread as a parameter. The anti-starvation boost differs from other boosts: Instead of applying a relative priority increment, the anti-starvation boost slams the thread's priority to the top of the dynamic range. (On pre-Service Pack 2--SP2--systems, the anti-starvation boost was to priority 14; post-SP2 systems boost to priority 15). When a thread that receives an anti-starvation boost finishes its extended quantum (or the thread blocks), its priority returns to the pre-starvation boost level and its quantum returns to its usual length.

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