Page 363 - DCAP103_Principle of operating system

Principles of Operating Systems

Notes
Figure 12.6: An Example of Priority Inversion

Before the consumer gets a chance to run again, an unrelated thread at priority 8 becomes ready
and starts running, as shown in Figure 12.6(b). As long as this thread wants to run, it will be
able to, since it outruns the consumer and the producer, while higher, is blocked. Under these
circumstances, the producer will never get to run again until the priority 8 thread gives up.
Windows 2000 solves this problem through what might be charitably called a big hack. The
system keeps track of how long it has been since a ready thread ran last. If it exceeds a certain
threshold, it is moved to priority 15 for two quanta. This may give it the opportunity to unblock
the producer. After the two quanta are up, the boost is abruptly removed rather than decaying
gradually. Probably a better solution would be to penalize threads that use up their quantum
over and over by lowering their priority. After all, the problem was not caused by the starved
thread, but by the greedy thread. This problem is well known under the name priority inversion.

An analogous problem happens if a priority 16 thread grabs a mutex and does not get a chance
to run for a long time, starving more important system threads that are waiting for the mutex.
This problem can be prevented within the operating system by having a thread that needs a
mutex for a short time just disable scheduling while it is busy. On a multiprocessor, a spin lock
should be used.
Before leaving the subject of scheduling, it is worth saying a couple of words about the quantum.
On Windows 2000 Professional the default is 20 msec; on uniprocessor servers it is 120 msec; on
multiprocessors various other values are used, depending on the clock frequency. The shorter
quantum favors interactive users whereas the longer quantum reduces context switches and thus
provides better efficiency. These defaults can be increased manually by 2x, 4x, or 6x if desired.
As an aside, the size of the quantum was chosen a decade ago and not changed since although
machines are now more than an order of magnitude faster. The numbers probably could be
reduced by a factor of 5 to 10 with no harm and possibly better response time for interactive
threads in a heavily loaded system.
One last patch to the scheduling algorithm says that when a new window becomes the foreground
window, all of its threads get a longer quantum by an amount taken from the registry. This
change gives them more CPU time, which usually translates to better service for the window
that just moved to the foreground.

Scheduling is applied in procurement and production, in transportation and
distribution, and in information processing and communication.

356 LOVELY PROFESSIONAL UNIVERSITY