disadvantages of a long time quantum in scheduling

Question

I'm trying to understand the example showing disadvantages of a long time quantum in Tanenbaum's book in Section 2.4.3 “Scheduling in Interactive Systems”.

To improve the CPU efficiency, we could set the quantum to, say, 100 msec. Now the wasted time is only 1%. But consider what happens on a server system if 50 requests come in within a very short time interval and with widely varying CPU requirements. Fifty processes will be put on the list of runnable processes. If the CPU is idle, the first one will start immediately, the second one may not start until 100 msec later, and so on. The unlucky last one may have to wait 5 sec before get- ting a chance, assuming all the others use their full quanta. Most users will perceive a 5-sec response to a short command as sluggish. This situation is especially bad if some of the requests near the end of the queue required only a few milliseconds of CPU time. With a short quantum they would have gotten better service.

I suppose request execution times are not known, so the order of execution of requests is chosen randomly with uniform distribution. I calculated the mean request completion times for 2 requests having execution times 1 and 2:

• infinitely small time quantum: 2.5
• infinitely large time quantum: 2.25

For the infinitely small time quantum, the 1-request completes in 2 time units since both requests are processed in parallel, then the 2-request completes in 3 time units. For the infinitely large time quantum, we have two equiprobable situations:

• the order is [1-request, 2-request], and the 1-request completes in 1 time units, then the 2-request completes in 3 time units
• the order is [2-request, 1-request], and the 2-request completes in 2 time units, then the 1-request completes in 3 time units

The mean request completion times for 3 requests having execution times 1, 2, and 3:

• infinitely small time quantum: 4.666666666666667
• infinitely large time quantum: 4

Where is the disadvantage of the infinitely large time quantum?

Answer 1

Try to think in practical terms what would actually happen if your computer used a big quantum:

Lets say our quantum is 1 second. Now, say you browse in a browser (for example, CS stack exchange), and want to ask a question in the CS stack exchange. Lets say, that you also got from your instructors some really annoying homework that made you need to run 20 programs at the same time, for a really long time (a few hours). While the programs run, you want to ask that question in the CS SE (because you really really need to know the answer of course). But all 20 programs use up all their quanta (and don't stop mid-quantum), so the probability that the browser gets to work every second is $\frac{1}{20}$. So, with an expected wait of $20$ seconds, the browser will be able to do work for only one second. You see the problem here? You will have to wait 20 seconds on average each time before you see anything happening in the browser: clicking a button, writing text, etc...

So the disadvantage comes from a user-experience perspective, rather than from a "total process time" perspective. Of course, if the only usage of the computer is to run 2-3 programs that only compute values (like what supercomputers do), and do not have any user interacting with them, then there is no need for such a short quantum.

Answer 2

I agree with you that Tanenbaum kind of biffed it here. Arguably if your goal was to minimize worst case wait time for the short jobs at the end of the queue, Tanenbaum's example would sort-of make sense. If there are 49 long jobs and 1 1msec job, the worst case wait time for the 1ms job with 100ms time slices would be 4901ms, while the worst case wait time with 1ms time slices would be 50ms.

I probably have an older edition of Tanenbaum than you (I have Modern Operating Systems, 2/e, 2001), and I think what he was trying to do in this section was motivate the need for multi-level priority feedback scheduling. This is essentially the scheduling algorithm used by CTSS in 1962. Variants of it were used in UNIX (for example as described in Bach's Design of the UNIX Operating System, 1986) and are used in Linux (for example as described in Bovet and Cesati's Understanding the Linux Kernel).

The goal of multi-level priority feedback is to try to simultaneously balance the fairness of round robin, with the latency minimization of shortest-job first (which requires you to have some way of predicting job lengths even though you don't really know the "true" job lengths), while maximizing the utilization of your physical disk by keeping the disk request queue as full as possible, and finally to minimize the overhead of context switching.

For the latency minimization subgoal, Bovet and Cesati specifically mention a threshold of annoyance for interactive users is somewhere between 50ms and 150ms.

The problem is that there's no formal definition of "interactive" jobs versus "batch" jobs, the operating system doesn't know which are which in any case, and we're trying to heuristically balance a bunch of mutually inconsistent goals, so there's no well-defined optimization problem to solve here. In practice multi-level priority feedback scheduling is a heuristic that qualitatively does a pretty good job.