Some implementations of multi-programming provide two levels of process scheduling. The first level (macro-scheduling) is used to select a small subset of processes, and the processor is switched only among the processes in the subset using the second level (micro-scheduling). This technique obviously reduces the number of context switches as well as the number of times the more expensive macro-scheduling decisions must be made. It is also useful in conjunction with managing virtual memory working sets.
However, the technique basically assumes that there will always be more ready processes than the processor can handle. That is, it assumes that the processor will seldom be idle. Given the contrary assumptions and requirements stated above, a single level of scheduling is more appropriate.
The requirements stated above virtually dictate that two ready queues must be maintained and the lower priority queue served only when the higher priority queue is empty. Furthermore, an executing process must be preempted if a higher priority process becomes ready. The only decision thus left to the scheduling mechanism is the choice of the next process to execute, given a set of ready processes of the same priority.
The simplest mechanism that readily presents itself, is to organize each ready queue as a first-in-first-out (FIFO) queue, giving each process a static time slice of (R/C)100 milliseconds before switching to the next process. (R denotes the minimum rate of execution, specified by process . Thus, time slices differ from process to process, but a particular process always receives the same slice.)
Clearly, if the processor is not overloaded, each process will progress at least as fast as its minimum rate, provided there is no interference from higher priority processes, and only minimal interference from interrupt servicing. Of course, if the processor is overloaded, a process may not receive the processor within the 100 millisecond period. However, the delay increases in proportion to the degree of overloading. And, if averaged over several 100 millisecond periods, the rate of execution also decreases in proportion to the degree of overloading. The simple FIFO mechanism thus keeps the rate of execution ``close'' to the desired rate - as is required. Moreover, in the overloaded case, the number of context switches are as few as can be made while still satisfying the requirements.
However, if the processor is underloaded, a process may receive the processor, exceed its time slice and lose the processor, and then receive the processor again, all within a single 100 millisecond period. That is, more context switches will be performed than is absolutely necessary. Clearly, the number of context switches can be minimized by dynamically increasing the time slice of the executing process in proportion to the degree of underloading.
However, increasing the time slices in proportion to processor underloading is difficult to implement. The processor loading changes every time a process blocks or becomes ready, and consequently the time slice must be re-calculated with each such event. Since these events are likely to be frequent, and the recalculations relatively expensive, the advantage of dynamically increasing time slices must be closely examined.
First of all it must be noted that if the processor is truly underloaded in the sense that the processor is often idle, it doesn't matter much whether some of the idle time is utilized instead to perform extra context switches. Furthermore, if most context switches are caused by the executing process blocking, rather than exceeding its time slice, the number of context switches cannot be much reduced by any policy. And, as already noted, if the processor is seldom idle, as well as overloaded (rate-wise), the fixed time slice mechanism results in minimal context switches.
It thus follows that the only situation where increasing time slices will save a significant number of context switches, is the one where the processor is ``underloaded'' in the sense that all processes can progress faster than their minimum rates of progress, but ``overloaded'' in the sense that processes usually exceed their time slices and the processor is seldom idle. Given the assumptions stated above, this does not amount to sufficient justification for varying process time slices as the processor's load varies.
Prof Herman Venter