On an SMP system, the decision is more complicated because the scheduler
must consider multiple CPUs (unless the thread's hard affinity stipulates only
one processor). ReadyThread, the algorithm responsible for this complex
evaluation, uses soft affinity as its primary guide. After acquiring the
Dispatcher Ready List lock, ReadyThread looks to see whether any idle processors
(i.e., processors not executing instructions from an active thread) appear in
the thread's hard-affinity list. If so, the scheduler's work is done; it signals
the idle processor to execute the thread. (The scheduler picks the CPU it's
running on if that CPU is a candidate; a CPU can be idle even though it's
executing the scheduler because the scheduler executes in a nonthread-specific
context).
If no processors are idle or the thread cannot execute on any thread,
Ready-Thread looks at one other processor. If the thread has an ideal processor,
the scheduler considers that CPU; otherwise, the scheduler examines the last
processor that the thread executed on. If the thread has a priority that equals
or exceeds the priority of the thread running on the CPU in question, the
scheduler signals the CPU to stop executing its current thread and execute the
new thread. In the case where the thread's priority is lower than the priority
of the running thread, ReadyThread places the thread in the appropriate priority
queue of the Dispatcher Ready List and releases the list's lock.
Unusual Consequences
If no processors are idle and the ready-to-execute thread has a lower
priority than the thread running on the ready-to-execute thread's ideal or
soft-affinity processor, ReadyThread can produce some unusual consequences
because it doesn't evaluate other processors in the system. Consider the
scenario in Figure3. A priority 9 thread (Thread 0) has just become
ready to run, and even though it has a higher priority than the threads running
on three of the four CPUs in the system, the scheduler places Thread 0 in the
Dispatcher Ready List. Why? Thread 0's priority is lower than the priority of
the thread running on the CPU that Thread 0 last executed on (Thread 1 on CPU 0
has priority 10). Thus, until FindReadyThread picks Thread 0 from the Dispatcher
Ready List, the system's second highest-priority thread will wait for a
processor.
ReadyThread can also potentially lead to needless movement (migration) of
threads from one processor to another. Consider the variation of
Figure3's
scenario that Figure4 depicts. In this example, Thread 1 executing on CPU 0 has
priority 8 instead of 10. ReadyThread will pull Thread 1 off CPU 0 in favor of
Thread 0 because Thread 0 has a higher priority (9). Because Thread 1 is still
ready to execute, NT calls ReadyThread for Thread 1. ReadyThread sees that
Thread 1 has a lower priority than the thread executing on Thread 1's last
processor (CPU 0); therefore, ReadyThread places Thread 1 in the Dispatcher
Ready List.
If the next event that triggers FindReadyThread is the expiration of Thread
4's quantum, FindReadyThread pulls Thread 1 off the Dispatcher Ready List to
execute on CPU 3 and puts Thread 4 on the list. At this point, Thread 1 has
migrated from CPU 0 to CPU 3. Thread 4 might then migrate to CPU 1 or CPU 2 when
one of them next invokes FindReadyThread.
NT could avoid unnecessary thread shuffling if ReadyThread considered only
the system's lowest-priority executing thread in its scheduling decision, rather
than using a soft-affinity strategy. Compare the thread movements diagrammed in
Figure5a and
Figure5b, in which threads with priorities 9, 8, and 7 are
running on three CPUs. In the worst case for the soft-affinity strategy, a
priority 10 thread that becomes ready-to-execute could set off all the shuffling
shown in Figure5a. Alternatively, checking only the lowest-priority executing
thread causes just the few movements shown in Figure5b.
The lowest-priority executing thread-scheduling strategy is simpler than
the soft affinity-based ReadyThread algorithm and can eliminate many unnecessary
thread migrations. The Solaris operating system uses this simpler algorithm, but
Microsoft defends its use of soft affinity as a primary scheduling parameter by
stating that SQL Server achieves higher throughput with this implementation.
Scalability Ramification
Microsoft bases NT's scheduling algorithms for SMP systems on the same
principles it incorporates for NT's
uniprocessor algorithms. However, efficiently using multiple processors
complicates the scheduling problem.
Having more than one processor that the NT scheduler can assign a thread to
leads to some interesting trade-offs in the ReadyThread algorithm--trade-offs
that could potentially hinder NT's ability to effectively use extra processors
that you add to a system (scalability). Because Microsoft has apparently decided
that it will measure the scalability of NT by the performance of SQL Server,
Microsoft has tuned NT's scheduling algorithms for this database application.