Time quantum assignment to processes

Question

In a book I am reading it is stated that an input/output intensive process should receive a higher time quantum whereas a computing intensive process on the other hand should receive a lower one. Here however, it is stated that:

A short quantum is good because it allows many processes to circulate through the processor quickly, each getting a brief chance to run. This way, highly interactive jobs that usually do not use up their quantum will not have to wait as long before they get the CPU again, hence improving interactive performance.

That's basically the exact opposite to what's stated in the book. So my question is should the quanta for input/output intensive processes and computing intensive processes be high or low and why?

Answer 1

It depends on what you are trying to achieve, but generally i/o intensive jobs should receive a higher priority, and a small time quantum.

I assume you are asking about some variety of multilevel feedback queuing. The idea behind multilevel feedback queue-based schedulers is to try to approximate shortest remaining time first scheduling, where you are trying to minimize the average time each process spends waiting while it is ready-to-run.

We assume each process goes through the following cycle:

1. ready-to-run: waiting for all higher-priority processes to finish using cpu.
2. running: for some amount of cpu time then perform a blocking i/o request.
3. sleeping: after making a blocking i/o request, the process sleeps, waiting for the response from the i/o system.

When the response comes back from the i/o system the process wakes up and is ready-to-run again. We call the set of processes that are ready to run (the processes not blocked waiting for a response from the i/o system), the run queue.

If we were able to predict exactly how long each process needed the cpu before its next i/o request, then we wouldn't need to have quanta at all. Every time a process made an i/o request (moving it from state running to state sleeping) or got a response from i/o (moving it from sleeping to ready-to-run) we would just find the process with the shortest remaining time to its next i/o request, and run it.

But we don't know exactly how long each process will use the cpu before its next i/o request. So we have to guess (e.g., by keeping track of how long it took the last few times, and using the average of those as the guess), but we might be way off. So we also start a timer with a length somewhat larger than our guess for the expected cpu usage. If our guesses are very good, then the timer will never fire. Instead, each process will either make an i/o request, causing itself to block and allowing some other process to run, or a response to an i/o request will return, preempting the currently running job and allowing us to perform a new scheduling decision.

Multilevel feedback queues approximate shortest remaining time first by having a few priority levels and moving jobs to lower priority when they use more than their allotted quantum. The idea is over 50 years old:

Corbató, FJ; Daggett, MM; Daley, RC: An Experimental Time-Sharing System, AFIPS Conference Proceedings, Vol. 21, pp. 335-344, 1962.