Page 360 - DCAP103_Principle of operating system

Unit 12: Processes and Threads in Windows

12.1.5 Scheduling Notes

Windows 2000 does not have a central scheduling thread. Instead, when a thread cannot run any
more, the thread enters kernel mode and runs the scheduler itself to see which thread to switch
to. The following conditions cause the currently running thread to execute the scheduler code:
1. The thread blocks on a semaphore, mutex, event, I/O, etc.
2. It signals an object (e.g., does an up on a semaphore).

3. The running thread’s quantum expires.

In condition 1, the thread is already running in kernel mode to carry out the operation on the
dispatcher or I/O object. It cannot possibly continue, so it must save its own context, run the
scheduler code to pick its successor, and load that thread’s context to start it.

In condition 2, the running thread is in the kernel, too. However, after signaling some object,
it can definitely continue because signaling an object never blocks. Still, the thread is required
to run the scheduler to see if the result of its action has released a higher priority thread that is
now free to run. If so, a thread switch occurs because Windows 2000 is fully preemptive (i.e.,
thread switches can occur at any moment, not just at the end of the current thread’s quantum).

In condition 3, a trap to kernel mode occurs, at which time the thread executes the scheduler
code to see who runs next. Depending on what other threads are waiting, the same thread may
be selected, in which case it gets a new quantum and continues running. Otherwise a thread
switch happens.

The scheduler is also called under two other conditions:
1. An I/O operation completes.

2. A timed wait expires.

In the first condition, a thread may have been waiting on this I/O and is now released to run. A
check has to be made to see if it should preempt the running thread since there is no guaranteed
minimum run time. The scheduler is not run in the interrupt handler itself (since that may keep
interrupts turned off too long). Instead a DPC is queued for slightly later, after the interrupt
handler is done. In the second condition, a thread has done a down on a semaphore or blocked
on some other object, but with a timeout that has now expired. Again it is necessary for the
interrupt handler to queue a DPC to avoid having it run during the clock interrupt handler. If
a thread has been made ready by this timeout, the scheduler will be run and if nothing more
important is available, the DPC will run next.

Now we come to the actual scheduling algorithm. The Win32 API provides two hooks for
processes to influence thread scheduling. These hooks largely determine the algorithm. First,
there is a call SetPriorityClass that sets the priority class of all the threads in the caller’s process.
The allowed values are: realtime, high, above normal, normal, below normal, and idle. Second,
there is a call SetThreadPriority that sets the relative priority of some thread (possibly, but
not necessarily, the calling thread) compared to the other threads in its process. The allowed
values are: time critical, highest, above normal, normal, below normal, lowest, and idle. With
six process classes and seven thread classes, a thread can have any one of 42 combinations. This
is the input to the scheduling algorithm.
The scheduler works as follows. The system has 32 priorities, numbered from 0 to 31. The 42
combinations are mapped onto the 32 priority classes according to the table of Figure 12.4.
The number in the table determines the thread’s base priority. In addition, every thread has a
current priority, which may be higher (but not lower) than the base priority and that we will
discuss shortly.

LOVELY PROFESSIONAL UNIVERSITY 353