Information Technology Reference
In-Depth Information
Chapter 7
Scheduling
Time is money { Ben Franklin
The best performance improvement is the transition from the non-working
state to the working state. That's innite speedup. { John Ousterhout
When there are multiple things to do, how do you choose which one to do
first? In the last few chapters, we have described how to create threads, switch
between them, and synchronize their access to shared data. At any point in
time, some threads are running on the processor. Others are waiting their turn
for the processor. Still other threads are blocked waiting for I/O to complete,
a condition variable to be signalled, or for a lock to be released. When there
is more than one runnable thread, the processor scheduling policy determines
Definition: processor
scheduling policy
which thread to run next.
You might think the answer to this question is easy: just do the work in
the order in which it arrives. After all, that seems to be the only fair thing
to do. Because it is obviously fair, almost all government services work this
way. When you go to your local Department of Motor Vehicles (DMV) to get a
driver's license, you take a number and wait your turn. Although fair, the DMV
often feels slow. There's a reason why: as we'll see later in this chapter, doing
things in order of arrival is sometimes the worst thing you can do in terms
of improving user-perceived response time. Advertising that your operating
system uses the same scheduling algorithm as the DMV is probably not going
to increase your sales!
You might think that the answer to this question is unimportant. With the
million-fold improvement in processor performance over the past thirty years, it
might seem that we are a million times less likely to have anything waiting for its
turn on the processor. We disagree! Server operating systems in particular are
often overloaded. Parallel applications can create more work than processors,
and if care isn't taken in the design of the scheduling policy, performance can
badly degrade.
There are subtle relationships between scheduling policy and
291
