Information Technology Reference
In-Depth Information
100ms, the disk-bound task slows down by nearly a factor of twenty | each
time it needs the processor, it must wait nearly 200ms for its turn. SJF on this
workload would perform well | prioritizing short tasks at the processor keeps
the disk-bound task busy, while only modestly slowing down the compute-bound
tasks.
If you have ever tried to surf the web while doing a large download, you
can see that network operations visibly slow during the download. This is even
though your browser may need to transfer only a very small amount of data to
provide good responsiveness. The reason is quite similar. Browser packets get
their turn, but only after being queued behind a much larger number of packets
for the bulk download. Prioritizing the browser's packets would have only a
minimal impact on the download speed and a large impact on the perceived
responsiveness of the system.
7.1.4
Max-Min Fairness
In many settings, a fair allocation of resources is as important to the design of
a scheduler as responsiveness and low overhead. On a multi-user machine or
on a server, we do not want to allow a single user to be able to monopolize the
resources of the machine, degrading service for other users. While it might seem
that fairness has little value in single-user machines, individual applications are
often written by different companies, each with an interest in making their
application performance look good even if that comes at a cost of degrading
responsiveness for other applications. Further, some applications may run inside
a single process, while others may create many processes, and each process may
involve multiple threads. Round robin among threads can lead to starvation
if applications with only a single thread are competing with applications with
hundreds of threads.
We can be concerned with fair allocation at any of these levels of granular-
ity: threads within a process, processes for a particular user, users sharing a
physical machine. For simplicity, our discussion will assume we are interested
in providing fairness among processes | the same principles apply if the unit
receiving resources is the user, application or thread.
Fairness is easy if all processes are compute-bound: Round Robin will give
each process an equal portion of the processor. In practice, however, different
processes consume resources at different rates. An I/O-bound process may need
only a small portion of the processor, while a compute-bound process is willing
to consume all available processor time. What is a fair allocation when there is
a diversity of needs?
One possible answer is to say that whatever Round Robin does is fair |
after all, each process gets an equal chance at the processor. As we saw above,
however, Round Robin can result in I/O-bound processes running at a much
slower rate than they would if they had the processor to themselves, while
