7.2.4   Analysis of Round-Robin Systems

Assume that a round-robin system is such that there are n processes in the ready
queue, no new ones arrive after the system starts, and none terminate prematurely.

The release time is arbitrary – in other words, although all processes are ready
at the same time, the order of execution is not predetermined, but is fixed.

Assume all processes have maximum end-to-end execution time, c. While this
assumption might seem unrealistic, suppose that each process, i, has a different
maximum execution time, c_i . Then letting c = max{c₁, . . . , c_n} yields a reasonably
upper bound for the system performance and allows the use of this model.

Now let the timeslice be q. If a process completes before the end of a time
quantum, in practice, that slack time would be assigned to the next ready process.
However, for simplicity of analysis, assume that it is not. This does not
hurt the analysis because an upper bound is desired, not an analytic responsetime
solution.

In any case, each process, ideally, would get 1/n of the CPU time in chunks
of q time units, and each process would wait no longer than (n − 1)q time units
until its next time up. Now, since each process requires at most time units
to complete, the waiting time will be (n − 1)q (where represents the
“ceiling” function, which yields the smallest integer greater than the quantity
inside the brackets). Thus, the worst-case time from readiness to completion for
any task (also known as turnaround time), denoted T , is the waiting time plus
undisturbed time to complete, c, or

As an example, suppose that there is only one process with a maximum execution
time of 500 ms and that the time quantum is 100 ms. Thus, n = 1, c = 500,
q = 100, and

which, is as expected.

Now suppose there are five processes with a maximum execution time of
500 ms. The time quantum is 100 ms. Hence, n = 5, c = 500, q = 100, which
yields

This is intuitively pleasing, since it would be expected that five consecutive tasks
of 500 ms each would take 2500 ms end-to-end to complete.

However, now assume that there is a context switching overhead, o. Now each
process still waits no longer than (n − 1)q until its next time quantum, but there
is the additional overhead of n · o each time around for context switching. Again,
each process requires at most time quanta to complete. So the worst-case
turnaround time for any task is now at most

An assumption is that there is an initial context switch to load the first time around.

To illustrate, suppose that there is one process with a maximum execution time
of 500 ms. The time quantum is 40 ms and context switch time is 1 ms. Hence,
n = 1, c = 500, q = 40, o = 1. So,

which is expected since the context switch time to handle the round-robin clock
interrupt costs 1 ms each time for the 13 times it occurs.

Next, suppose that there are six processes, each with a maximum execution
time of 600 ms, the time quantum is 40 ms, and context switch time costs 2 ms.
Now, n = 6, c = 600, q = 40, and o = 2. Then

which again is pleasing, because one would expect six processes of 600 ms in
duration to take at least 3600 ms, without context switching costs.

In terms of the time quantum, it is desirable that q < c to achieve “fair”
behavior. For example, if q is very large, the round-robin algorithm is just the
first-come, first-served algorithm in that each process will execute to completion,
in order of arrival, within the very large time quantum.

The technique just discussed is also useful for cooperative multitasking analysis
or any kind of “fair” cyclic scheduling with context switching costs.