Scheduling in Interactive Systems

Scheduling in Interactive Systems

We will now study some algorithms that can be used in interactive systems. These are common on personal computers, servers, and other kinds of systems as well.

Round-Robin Scheduling

One of the oldest, simplest, fairest, and most extensively used algorithms is round robin. Each process is assigned a time interval, called its quantum, during which it is allowed to run. If the process is still running at the end of the quantum, the CPU is preempted and given to another process. If the process has blocked or ended before the quantum has elapsed, the CPU switching is done when the process blocks, of course. Round robin is easy to implement. All the scheduler needs to do is maintain a list of runnable processes, as shown in Figure 1(a). When the process uses up its quantum, it is put on the end of the list, as shown in Figure 1(b).

The only interesting issue with round robin is the length of the quantum. Switching from one process to another requires a certain amount of time for doing the administration-saving and loading registers and memory maps, updating various tables and lists, flushing and reloading the memory cache, and so on. Assume that this process switch or context switch, as it is sometimes  called, takes 1 msec, including switching memory maps, flushing and reloading the cache, etc. Also assume that the quantum is  set at 4 msec. With these parameters, after doing 4 msec of useful work, the CPU will have to spend (i.e., waste) 1 msec on process switching. As a result 20% of the CPU time will be thrown away on administrative overhead. Clearly, this is too much.

Round-robin scheduting

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 getting 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.
 
Another factor is that if the quantum is set longer than the mean CPU burst, preemption will not occur very often. Instead, most processes will perform a blocking operation before the quantum runs out, causing a process switch. Eliminating preemption  improves performance because process switches then only occur when they are logically necessary, that is, when a process  blocks and cannot continue.

The conclusion can be formulated as follows: setting the quantum too short causes too many process switches and lowers the  CPU efficiency, but setting it too long may cause poor response to short interactive requests. A quantum around 20-50 msec is  often a reasonable compromise.

Priority Scheduling

Round-robin scheduling makes the implicit assumption that all processes are equally important. Often, the people who own and operate multiuser computers have different ideas on that subject. At a university, for instance, the pecking order may be deans first, then professors, secretaries, janitors, and finally students. The need to take external factors into account leads to priority scheduling. The main idea is straightforward: each process is assigned a priority, and the runnable process with the highest priority is allowed to run.

Even on a PC with a single owner, there may be multiple processes, some of them more important than others. For instance, a daemon process sending electronic mail in the background should be assigned a lower priority than a  process displaying a video film on the screen in real time.

To prevent high-priority processes from running indefinitely, the scheduler may decrease the priority of the currently running process at each clock tick (i.e., at each clock interrupt). If this action causes its priority to drop below that of the
next highest process, a process switch happens. Alternatively, each process may be assigned a maximum time quantum that it is allowed to run. When this quantum is used up, the next highest priority process is given a chance to run.

Priorities can be assigned to processes statically or dynamically. On a military computer, processes started by generals might begin at priority 100, processes started by colonels at 90, majors at 80, captains at 70, lieutenants at 60, and so on. Alternatively, at a commercial computer center, high-priority jobs might cost $100 an hour, medium priority $75 an hour,  and low priority $50 an hour. The UNIX system has a command, nice, which allows a user to willingly reduce the priority of his process, in order to be nice to the other users. Nobody ever uses it.

Priorities can also be assigned dynamically by the system to achieve certain system goals. For instance, some processes are highly I/O bound and spend most of their time waiting for I/O to complete. Whenever such a process wants the CPU, it should be given the CPU immediately, to let it start its next I/O request, which can then proceed in parallel with another process actually computing. Making the I/O-bound process wait a long time for the CPU will just mean having it around occupying memory for an unnecessarily long time. A simple algorithm for giving good service to I/O-bound processes is to set the priority to 1/f, where f is the fraction of the last quantum that a process used. A process that used only 1 msec of its 50 msec quantum would get priority 50, while a process that ran 25 msec before blocking would get priority 2, and a process that used the whole quantum would get priority 1.

It is often convenient to group processes into priority classes and use priority scheduling among the classes but round- robin scheduling within each class. Figure 2 shows a system with four priority classes. The scheduling algorithm is as
follows: as long as there are runnable processes in priority class 4, just run each one for one quantum, round-robin  fashion, and never bother with lower-priority classes. If priority class 4 is empty, then run the class 3 processes round robin. If classes 4 and 3 are both empty, then run class 2 round robin, and so on. If priorities are not adjusted occasionally,  lower priority classes may all starve to death.

Multiple Queues

One of the earliest priority schedulers was in CTSS, the M.I.T. Compatible TimeSharing System that ran on the IBM 7094  (Corbato et al., 1962). CTSS had the problem that process switching was very slow because the 7094 could hold

A scheduling algorithm with four priority classes

only one process in memory. Each switch meant swapping the current process to disk and reading in a new one from disk. The CTSS designers quickly realized that it was more efficient to give CPU-bound processes a large quantum once  in a while, rather than giving them small quanta frequently (to reduce swapping). On the other hand, giving all processes a large quantum would mean poor response time, as we have already seen. Their solution was to set up priority classes.  Processes in the highest class were run for one quantum. Processes in the next-highest class were run for two quanta.  Processes in the next class were run for four quanta, and so on. Whenever a process used up all the quanta allocated to it, it was moved down one class.

As an example, consider a process that needed to compute continuously for 100 quanta. It would at first be given one quantum,  then swapped out. Next time it would get two quanta before being swapped out. On succeeding runs it would get 4, 8, 16,  32, and 64 quanta, although it would have used only 37 of the final 64 quanta to complete its work. Only 7 swaps would be required (including the initial load) instead of 100 with a pure round-robin algorithm. Moreover, as the process sank deeper and deeper into the priority queues, it would be run less and less frequently, saving the CPU for short, interactive processes.

The following policy was adopted to prevent a process that required to run for a long time when it first started but became interactive later, from being punished forever. Whenever a carriage return (Enter key) was typed at a terminal, the process belonging to that terminal was moved to the highest priority class, on the assumption that it was about to become interactive. One fine day, some user with a heavily CPU-bound process discovered that just sitting at the terminal and  typing carriage returns at random every few seconds did wonders for his response time. He told all his friends. Moral of the story: getting it right in practice is much harder than getting it right in principle.

Many other algorithms have been used for assigning processes to priority classes. For instance, the influential XDS 940  system (Lampson, 1968), built at Berkeley, had four priority classes, called terminal, I/O, short quantum, and long quantum. When a process that had been waiting for terminal input was finally awakened, it went into the highest priority class (terminal). When a process waiting for a disk block became ready, it went into the second class. When a process was still running when its quantum ran out, it was at first placed in the third class.  However, if a process used up its quantum too many times in a row without blocking for terminal or other I/O, it was moved down to the bottom queue. Many other systems use something similar to favor interactive users and processes over background ones.



Tags

round robin, quantum, memory cache, process switch, runnable processes