Page 361 - DCAP103_Principle of operating system

Principles of Operating Systems

Notes
Figure 12.4: Mapping of Win32 Priorities to Windows 2000 Priorities

Win32 process class priorities

Realtime High Above Normal Below Idle
Normal Normal

Time critical 31 15 15 15 15 15

Highest 26 15 12 10 8 6

Above normal 25 14 11 9 7 5
Win 32
thread Normal 24 13 10 8 6 4
priorities
Below normal 23 12 9 7 5 3

Lowest 22 11 8 6 4 2

Idle 16 1 1 1 1 1

To use these priorities for scheduling, the system maintains an array with 32 entries, corresponding
to priorities 0 through 31 derived from the table of Figure 12.4. Each array entry points to the
head of a list of ready threads at the corresponding priority. The basic scheduling algorithm
consists of searching the array from priority 31 down to priority 0. As soon as a non-empty slot
is found, the thread at the head of the queue is selected and run for one quantum. If the quantum
expires, the thread goes to the end of the queue at its priority level and the thread at the front
is chosen next. In other words, when there are multiple threads ready at the highest priority
level, they run round robin for one quantum each. If no thread is ready, the idle thread is run.
It should be noted that scheduling is done by picking a thread without regard to which process
that thread belongs. Thus, the scheduler does not first pick a process and then pick a thread in
that process. It only looks at the threads. It does not even know which thread belongs to which
process. On a multiprocessor, each CPU schedules itself using the priority array. A spin lock is
used to make sure that only one CPU at a time is inspecting the array.

The array of queue headers is shown in Figure 12.5. The figure shows that there are actually
four categories of priorities: realtime, user, zero, and idle, which is effectively -1. These deserve
some comment. Priorities 16-31 are called real time, but they are not. There are no guarantees
given and no deadlines are met. They are simply higher priority than 0-15. However, priorities
16 through 31 are reserved for the system itself and for threads explicitly assigned those priorities
by the system administrator. Ordinary users may not run there for a good reason. If a user thread
were to run at a higher priority than, say, the keyboard or mouse thread and get into a loop,
the keyboard or mouse thread would never run, effectively hanging the system.
User threads run at priorities 1-15. By setting the process and thread priorities, a user can
determine which threads get preference. The zero thread runs in the background and eats up
whatever CPU time nobody else wants. Its job is to zero pages for the memory manager. We
will discuss its role later. If there is absolutely nothing to do, not even zero pages, the idle thread
runs. It is not really a full blown thread though.

354 LOVELY PROFESSIONAL UNIVERSITY