A closer look to one of the most widely used scheduling algorithm. Being present in all major operating system (under variants, of course) but also in most amateur OS, we consider it is a good reading for all OS developers.

Scheduling is the process of assigning tasks to a set of resources. It is an important concept in many areas such as computing and production processes.
It is a key concept in multitasking and multiprocessing operating system design, and in real-time operating system design. It refers to the way processes are assigned priorities in a priority queue. This assignment is carried out by software known as a scheduler.

In general-purpose operating systems, the goal of the scheduler is to balance processor loads, and prevent any one process from either monopolizing the processor or being starved for resources. In real-time environments, such as devices for automatic control in industry (for example robotics), the scheduler also must ensure that processes can meet deadlines; this is crucial for keeping the system stable.

Round-robin is the simplest scheduling algorithm for processes in an operating system, which assigns time slices to each process in equal portions and order, handling all processes as having the same priority. In prioritized scheduling systems, processes on an equal priority are often addressed in a round-robin manner. This algorithm starts at the beginning of the list of PDBs (Process Descriptor Block), giving each application in turn a chance at the CPU when time slices become available.

Round robin has the great advantage of the fact that it is easy to implement in software. Since the operating system must have a reference to the start of the list, and a reference to the current application, it can easily decide who to run next�just follow the array or chain of PDBs to the next element, and if you reach the end of the array or list, reset back to the start. The PDBs must be checked to ensure that we don�t inadvertently execute a blocked application, as that needlessly could waste CPU time, or worse, make a task think it has found its resources when in reality it should be waiting a while longer. The word comes from the round-robin principle known from other fields, where each person takes an equal share of something in turn.

In short, each process is assigned a time interval, called its quantum, 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 of finished before the quantum has elapsed, the CPU switching is done when process blocks, of course.

The Scheduling algorithms can be divided into two categories with respect to how they deal with clock interrupts.

Nonpreemptive Scheduling

A scheduling discipline is nonpreemptive if, once a process has been given the CPU it cannot be taken away from that process.
Following are some characteristics of nonpreemptive scheduling:
1. In nonpreemptive system, short jobs are made to wait by longer jobs but the overall treatment of all processes is fair.
2. In nonpreemptive system, response times are more predictable because incoming high priority jobs can not displace waiting jobs.
3. In nonpreemptive scheduling, a scheduler executes jobs in the following two situations:
a. When a process switches from running state to the waiting state.
b. When a process terminates.

Preemptive Scheduling

A scheduling discipline is preemptive if, once a process has been given the CPU can taken away.

The strategy of allowing processes that are logically runable to be temporarily suspended is called Preemptive Scheduling and it is contrast to the "run to completion" method.

Round Robin Scheduling is preemptive (at the end of time-slice) therefore it is effective in time-sharing environments in which the system needs to guarantee reasonable response times for interactive users.

The most interesting issue with round robin scheme is the length of the quantum. Setting the quantum too short causes too many context switches and lower the CPU efficiency. On the other hand, setting the quantum too long may cause poor response time and approximates First Come First Served (FCFS).
Let's assume that task switching takes 2 msec.

If we have a quantum of 8 msec, we ensure very good response time. For example, imagine 20 users all logged in to a single CPU server; with every user making a request at the same time, each task takes up 10 msec (8 msec quantum + 2 msec overhead), and the 20th user gets a response in 200 msec (10 msec � 20), which is pretty good (5th second).

On the other hand, efficiency is:
Useful time � total time = 8ms � 10ms = 80%
i.e. 20% of the CPU time is wasted on overhead.

With a 200 msec quantum, efficiency is 200 msec / 202 msec = ~99%

But, response time if 20 users make a request at once is 202 * 20 = 4040 msec or > 4 seconds, which is not good. To get a full picture about what is really happening, let�s take a look to the parameters definitions:
� Response Time - Time for processes to complete. The OS may want to favor certain types of processes or to minimize a statistical property like average time
� Implementation Time - This includes the complexity of the algorithm and the maintenance
� Overhead - Time to decide which process to schedule and to collect the data needed to make that selection
� Fairness - To what extent are different users� processes treated differently
So, large quantum insures more efficient while a small quantum will determine a better response-time. Throughput and turnaround depend on number of jobs in system and I/O usage per task. Round robin is obviously fair.

In any event, the average waiting time under round robin scheduling is often quite long - process may use less than its time slice (e.g. blocking on a semaphore or I/O operation). Idle task should never get CPU except when no other task is running (it should not participate in the round robin).

Most current major operating systems run variants of round robin and maybe the most important improvement they bring are the priority classes for processes.

A simple algorithm for setting these classes 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 2 msec of its 100 msec share would get a priority level of 50, while one which used 50 msec before blocking will get a priority level of 2. Therefore, the processes that used their entire 100 msec quantum will get the lowest priority (that would be one, on other systems, priority are C-style [0...99], unlike Linux which sets them from 1 to 99).

READING LIST & BIBLIOGRAPHY
1. Tanenbaum, Andrew S. - Modern Operating Systems (ISBN: 0-12-588187-0)
2. MegaTokyo OS FAQ (dead link)
3. Wikipedia Encyclopedia