Inside the Windows NT Scheduler, Part 2

In my July column, "Inside the Windows NT Scheduler, Part 1," I described the basics of threads, priorities, and uniprocessor scheduling on Windows NT 4.0. I presented definitions for threads and processes, and provided an overview of NT's thread priority scheme. This month, I'll finish my examination of NT scheduling by presenting the algorithms NT employs on multiprocessors.

The priority scheme and scheduling basics that I described last month apply to multiprocessor systems as well. However, in most cases on multiprocessor systems, the scheduler can choose among several CPUs to schedule a given thread. Deciding which CPU to pick so that NT uses the processors to their full potential is a complex problem, as you'll see.

In writing this article, I assumed that you are up to speed with the terminology I introduced last month. If you are not familiar with basic scheduling terms and concepts (e.g., you don't know what the Dispatcher Ready List is), I suggest you read last month's column before digging into this one.

NT and Multiprocessing
From the outset, Microsoft designed NT with multiprocessing in mind. The type of multiprocessing that NT supports is symmetric multiprocessing (SMP). In an SMP system, all the CPUs are identical, the operating system (NT) can run on any of the CPUs, and all the CPUs have equal access to main memory and peripheral devices. The opposite of an SMP system is a system in which the CPUs are different, the CPUs have private memory or devices, or the CPUs have priorities such that the operating system runs on only certain CPUs. Figures 1a and 1b (page 178) contrast an SMP system with an example of a non-SMP (an asymmetric multiprocessing--ASMP) system.

Figure1A depicts an SMP system. The CPUs are identical, all the CPUs have private Level 1 (L1) and Level 2 (L2) caches (the L1 cache usually resides on the CPU chip), and all the CPUs have equal access to main memory and the I/O subsystem. The NT kernel can run on any of the CPUs; it can even run simultaneously on several CPUs. Figure1B presents an example ASMP system with one master CPU. The master CPU, which runs the operating system and is the only CPU that can access the I/O subsystem, farms out work to the slave CPUs.

Microsoft designed NT's internal data structures and code to support up to 32 processors. However, NT Workstation enables a maximum of 2 processors, and NT Server enables a maximum of 4 processors, regardless of how many CPUs the system contains. Microsoft imposes these limitations with Registry values, which the NT kernel queries during processor initialization to determine the upper limit of CPUs to conFigure. This process involves two values that cross-reference each other, and the system monitors one value to prevent tampering. If a system has more than 4 processors, the vendor must license the OEM version of NT, which is nothing more than NT with modified setup files that initialize the Registry with values appropriate to the system during NT's installation. As NT enables processors, it assigns them numbers (starting with 0) to identify them internally.

To prevent corruption that might occur if multiple instances of the kernel modified the same data simultaneously, the NT kernel protects its shared data structures with locks. Typically, only one kernel instance (CPU) at a time can write to, or read from, core data structures. Before accessing a data structure, a CPU must acquire a lock that protects the data structure; after completing the access, the CPU must release the lock. If the lock is not available when the CPU requests it, the CPU waits.

An example of a core data structure that NT protects with a lock is the Dispatcher Ready List, which I described last month. Locking ensures that even though more than one processor might require a scheduling operation, the scheduling code will never be running on more than one CPU at a time. Other processors that require scheduling must wait until they can acquire the lock protecting the Dispatcher Ready List before executing the scheduling algorithms.

Although SMP systems contain more than one processor, the situations on SMP systems that require scheduling operations are the same as the situations that require scheduling operations on uniprocessor systems. You'll recall from last month that several situations invoke the scheduler. If a thread's turn on the CPU expires, if a thread blocks (i.e., waits for an event to occur), or if a thread yields its turn on a processor because the thread has terminated, the scheduler uses the FindReadyThread routine to find a new thread to execute on the CPU.

A thread that becomes ready to execute also invokes the scheduler. One example of a ready-to-execute thread is a thread that wakes up after waiting for an event to occur. Another example is a thread that NT pulls off a CPU because the thread's turn has ended--the thread is still eligible to execute, so the scheduler might move it to another CPU. The algorithm the scheduler executes in ready-to-execute situations is ReadyThread.