Information Technology Reference
In-Depth Information
Figure7.1: Completion times with FIFO and SJF scheduling when short tasks
arrive just after a long task.
only when each one completes. Because it minimizes overhead, if we have a
fixed number of tasks, and those tasks only need the processor, FIFO will have
the best throughput: it will complete the most tasks the most quickly. And
as we mentioned, FIFO appears to be the denition of fairness | every task
patiently waits its turn.
Unfortunately, FIFO has a weakness. If a task with very little work to do
happens to land in line behind a task that takes a very long time, then the system
will seem very inecient. Figure 7.1 illustrates a particularly bad workload for
FIFO. If the first task in the queue takes one second, and the next five arrive
an instant later, but each only needs a millisecond of the processor, then they
will all need to wait until the first one finishes. The average response time will
be over a second, but the optimal average response time is much less than that.
In fact, if we ignore switching overhead, there are some workloads where FIFO
is literally the worst possible policy for average response time.
7.1.2
Shortest Job First (SJF)
If FIFO can be a poor choice for average response time, is there an optimal
policy for minimizing average response time? The answer is yes: schedule the
shortest job rst (SJF).
Suppose we could know how much time each task needed at the processor.
