# Scheduling Algorithms

A scheduling algorithm is the algorithm which dictates how much CPU time is allocated to Processes and Threads. The goal of any scheduling algorithm is to fulfill a number of criteria:

• no task must be starved of resources - all tasks must get their chance at CPU time;
• if using priorities, a low-priority task must not hold up a high-priority task;
• the scheduler must scale well with a growing number of tasks, ideally being O(1). This has been done, for example, in the Linux kernel.

## Interactive Scheduling Algorithms

### Round Robin

Round Robin is the simplest algorithm for a preemptive scheduler. Only a single queue of processes is used. When the system timer fires, the next process in the queue is switched to, and the preempted process is put back into the queue.

Each process is assigned a time slice or "quantum". This quantum dictates the number of system timer ticks the process may run for before being preempted. For example, if the timer runs at 100Hz, and a process' quantum is 10 ticks, it may run for 100 milliseconds (10/100 of a second). To achieve this, the running process is given a variable that starts at its quantum, and is then decremented each tick until it reaches zero. The process may also relinquish its quantum by doing a blocking system call (i.e. I/O), like in other preemptive algorithms.

In the Round Robin algorithm, each process is given an equal quantum; the big question is how to choose the time quantum.

Here are some considerations: The smaller the quantum, the larger the proportion of the time used in context switches.
Interactive processes should do I/O before being preempted, so that unnecessary preemptions are avoided.
The larger the quantum, the "laggier" the user experience - quanta above 100ms should be avoided.

A frequently chosen compromise for the quantum is between 20ms and 50ms.

Advantages of Round Robin include its simplicity and strict "first come, first served" nature. Disadvantages include the absence of a priority system: lots of low privilege processes may starve one high privilege one.

### Priority-Based Round Robin

Priority scheduling is similar to Round Robin, but allows a hierarchy of processes. Multiple process queues are used, one for each priority. As long as there are processes in a higher priority queue, they are run first. For example, if you have 2 queues, "high" and "low", in this state:

"high": X
"low": xterm, vim, firefox

The first process to run would be X, then if it blocked (for I/O, probably), the state would be:

"high":
"low": xterm, vim, firefox

The next process that would run would be xterm. If process "kswapd" is added to "high", it would then get the next quantum:

"high": kswapd
"low": vim, firefox, xterm

There are usually between four and sixteen queues used in a priority scheduler.

Advantages of this algorithm are simplicity and reasonable support for priorities. The disadvantage (or possible advantage) is that privileged processes may completely starve unprivileged ones. This is less of a problem than it appears, because processes (especially daemons, which are usually privileged) are usually blocked for I/O.

Let's have a look on the round robin scheduler with three processes in the queue: A B C:

```A(time 0) B(time 10) C(time 10)  A's time slice is zero: let's do round robin scheduling:
B(time 10) C(time 10) A(time 10) ... one clock tick occurs ... the next one ...
B(time 8) C(time 10) A(time 10)  ... several clock ticks occur ... b's time slice is worn out ...
C(time 10) A(time 10) B(time 10) ... ten clock ticks later ...
A(time 10) B(time 10) C(time 10) ... now A has its share of CPU time again.
```

#### SVR2 Unix Implementation

Classical UNIX systems scheduled equal-priority processes in a round-robin manner, each running for a fixed time quantum. If a higher priority process becomes runnable, it will preempt the current process (if it's not running in kernel mode, since classical UNIX kernels were non-preemptive) even if the process did not finish its time quantum. This way, high priority processes can possibly starve low-priority ones. To avoid this, a new factor in calculating a process priority was introduced: the 'usage' factor.

This factor allows the kernel to vary processes priorities dynamically. When a process is not running, the kernel periodically increases its priority. When a process receives some CPU time, the kernel reduces its priority. This scheme will potentially prevent the starvation of any process, since eventually the priority of any waiting process will rise high enough to be scheduled.

All user-space priorities are lower than the lowest system priority. The usage factor of a user-process is calculated by the amount of compute time to real-time consumed by the process. A process that has used a lot of compute time in the last real-time unit is assigned a low user priority. Because interactive processes are characterized by low ratios of compute to real time, interactive response is maintained without any special arrangements.

If there are no processes eligible for execution, the CPU idles till the next interrupt, which will happen at most after one clock tick. After handling the interrupt, the kernel again attempts to schedule a process to run.