How Windows 2000 Handles SMP CPU Scheduling

Microsoft Windows 2000 implements symmetric multiprocessing (SMP) support through a preemptive, priority-driven kernel dispatcher that schedules individual execution threads rather than whole processes across all available CPUs. In an SMP system, Windows 2000 treats all physical processors as peers, balancing thread execution using a global priority model, processor affinity mechanisms, and cache-optimization heuristics to assign the highest-priority runnable threads to idle or lower-priority processors.

Thread-Level Scheduling

Windows 2000 does not schedule processes directly; instead, the basic unit of execution is the thread. A process serves merely as a container providing an address space and security context. The Windows 2000 kernel dispatcher evaluates all active threads across the operating system to determine which threads are assigned execution time on available CPUs.

Priority Architecture

The dispatcher manages threads using 32 discrete priority levels ranging from 0 (lowest) to 31 (highest):

  • Real-Time Priorities (16–31): Fixed-priority threads that execute without automatic dynamic priority adjustments. They guarantee immediate preemption of lower-priority tasks.
  • Dynamic Priorities (1–15): Variable-priority threads whose base priorities can be dynamically boosted by the kernel (e.g., following I/O completion, window focus changes, or to prevent resource starvation).
  • System Thread (0): Reserved exclusively for the zero-page thread, which clears memory pages when the system is idle.

On an SMP system, the scheduler constantly ensures that the \(N\) highest-priority runnable threads in the system are executing across the \(N\) available processors.

The Global Dispatcher Lock and Ready Queues

Unlike later Windows architectures that use per-processor ready queues, Windows 2000 utilizes a centralized dispatching database. Ready threads are held in a set of global queues sorted by priority.

To maintain synchronization across multiple CPUs, the kernel relies on a central synchronization primitive known as the KiDispatcherLock. When a processor requires a new thread or a thread changes state, that processor acquires the dispatcher spinlock, inspects the global ready queues, updates thread execution states, and releases the spinlock. While effective for typical dual- and quad-processor systems supported by Windows 2000 Professional and Server editions, this centralized lock was a known bottleneck for larger multi-socket configurations.

Processor Affinity and Cache Optimization

When a thread enters the ready state, the Windows 2000 scheduler determines the most appropriate CPU using affinity rules designed to minimize cache invalidation:

  • Hard Affinity: A bitmask set by the application or an administrator specifying the exact set of processors on which a thread is permitted to run. The dispatcher will never assign the thread to an unmasked processor.
  • Soft Affinity: The kernel's preference to run a thread on the processor it executed on most recently. Reusing the same processor maximizes CPU cache hits by taking advantage of cached instructions and data remaining in L1/L2 caches.
  • Ideal Processor: A specific processor designated by the developer or the system as the preferred target for that thread. If the ideal processor is available, the thread is assigned there first; if busy, the dispatcher checks the thread's previous processor before selecting any other idle CPU.

Processor Selection Logic

When a processor finishes its thread quantum, blocks on an I/O request, or is preempted, the scheduler executes the following sequence:

  1. Idle CPU Check: If a thread is ready and a processor is currently idle, the scheduler checks if the idle processor matches the thread's ideal or previous processor. If it does, the thread is dispatched immediately.
  2. Next Available Processor: If the ideal processor is busy, the thread may be scheduled on any other available CPU allowed by its hard affinity mask, provided that the thread has waited long enough to diminish the value of cache locality.
  3. Preemption: If all processors are busy, the dispatcher evaluates whether the ready thread has a higher priority than the thread running on the candidate processor. If so, the scheduler sends an Inter-Processor Interrupt (IPI) to that CPU, forcing a context switch to preempt the lower-priority thread.