Information Technology Reference
In-Depth Information
7.1
Uniprocessor scheduling
We start by considering one processor, generalizing to multiprocessor scheduling
policies in the next section. We begin with three simple policies | rst-in-rst-
out, shortest-job-rst, and round robin | as a way of illustrating scheduling
concepts. Each approach has its own the strengths and weaknesses, and most
resource allocation systems (whether for processors, memory, network or disk)
combine aspects of all three. At the end of the discussion, we will show how
the different approaches are synthesized into a more practical and complete
processor scheduler.
Before proceeding, we need to define a few terms. A workload is a set of tasks
Denition: workload
for some system to perform, along with when each task arrives and how long
each task takes to complete. In other words, the workload defines the input to
a scheduling algorithm. Given a workload, a processor scheduler decides when
each task is to be assigned the processor.
We are interested in scheduling algorithms that work well across a wide va-
riety of environments, because workloads will vary quite a bit from system to
system and user to user. Some tasks are compute-bound and only use the pro-
Denition:
compute-bound
cessor. Others, such as a compiler or a web browser, mix I/O and computation.
Still others, such as a BitTorrent download, are I/O bound , spending most of
Denition: I/O bound
their time waiting for I/O and only brief periods computing. In the discus-
sion, we start with very simple compute-bound workloads and then generalize
to include mixtures of different types of tasks as we proceed.
Some of the policies we outline are the best possible policy on a particular
metric and workload, and some are the worst possible policy. When discussing
optimality and pessimality, we are only comparing to policies that are work-
conserving . A scheduler is work-conserving if it never leaves the processor idle
Denition:
work-conserving
if there is work to do. Obviously a trivially poor policy has the processor sit
idle for long periods when there are tasks in the ready queue.
Our discussion also assumes the scheduler has the ability to preempt the
Denition: preempt
processor and give it to some other task. Preemption can happen either because
of a timer interrupt, or because some task arrives on the ready list with a higher
priority than the current task, at least according to some scheduling policy. We
explained how to switch the processor between tasks in Chapters 2 and 4. While
much of the discussion is also relevant to non-preemptive schedulers, there are
few such systems left, so we leave that issue aside for simplicity.
7.1.1
First In First Out (FIFO)
Perhaps the simplest scheduling algorithm possible is rst-in-rst-out (FIFO):
do each task in the order in which it arrives. (FIFO is sometimes also called
rst-come-rst-served, or FCFS.) When we start working on a task, we keep
running it until it is done. FIFO minimizes overhead, switching between tasks
