Information Technology Reference
In-Depth Information
What is the overhead of a Round Robin time slice?
One might think that the cost of switching tasks after a time slice is modest: the cost
of interrupting the processor, saving its registers, dispatching the timer interrupt handler,
and restoring the registers of the new task. On a modern processor, all these steps can
be completed in a few tens of microseconds.
However, we must also include the impact of Round Robin on the efficiency of the
processor cache. Each new task will need to fetch its data from memory into cache,
evicting some of the data that had been stored by the previous task. Exactly how long
this takes will depend on the memory hierarchy, the reference pattern of the new task,
and whether any of its state is still in the cache after its previous time slice. Modern
processors often have multiple levels of cache to improve performance. Reloading just
the first level on-chip cache from scratch can take several milliseconds; reloading the
second and third level caches takes even longer. Thus it is typical for operating sys-
tems to set their time slice interval to be somewhere between 10 and 100 milliseconds,
depending on the tradeoff between better responsiveness and reduced overhead.
turn. Figure 7.2 shows the behavior of Round Robin, on the same workload as
in Figure 7.1, for two different values for the time quantum.
A good analogy for Round Robin is a particularly hyperkinetic student,
studying for multiple nals simultaneously. You won't get much done if you
read a paragraph from one textbook, then switch to reading a paragraph from
the next textbook, and then switch to yet a third textbook. But if you never
switch, you may never get around to studying for some of your courses.
One way of viewing Round Robin is as a compromise between FIFO and
SJF. At one extreme, if the time quantum is infinite (or at least, longer than
the longest task), Round Robin behaves exactly the same as FIFO. Each task
runs to completion and then yields the processor to the next in line. At the other
extreme, suppose it was possible to switch between tasks with zero overhead,
so we could choose a time quantum of a single instruction. With fine-grained
time-slicing, tasks would finish in the order of length, as with SJF, but a bit
slower: a task A will take as long as it would have under SJF, plus a factor
proportional to the number of other tasks as long as A the length of A.
Unfortunately, Round Robin has some weaknesses. Figure 7.3 illustrates
what happens for FIFO, SJF and Round Robin when several tasks start at
roughly same time and are of the same length. Round Robin will rotate through
the tasks, doing a bit of each, finishing them all at roughly the same time. This
is nearly the worst possible scheduling policy for this workload! FIFO does much
better, picking a task and sticking with it until it is done. Not only does FIFO
reduce average response time for this workload relative to Round Robin, no task
is worse o under FIFO | every task nishes at least as early as it would have
under Round Robin. Time slicing added overhead without any benefit. Finally,
