Round-Robin Scheduling

• The round-robin (RR) scheduling algorithm is designed especially for time-sharing systems. It is similar to FCFS scheduling, but pre-emption is added to switch between processes.
• A small unit of time, called a time quantum or time slice, is defined. A time quantum is generally from 10 to 100 milliseconds. The ready queue is treated as a circular queue.
• To implement RR scheduling,
  • we keep the ready queue as a FIFO queue of processes.
  • New processes are added to the tail of the ready queue.
  • The CPU scheduler picks the first process from the ready queue, sets a timer to interrupt after 1 time quantum, and dispatches the process.
  • The process may have a CPU burst of less than 1 time quantum.
    • In this case, the process itself will release the CPU voluntarily.
    • The scheduler will then proceed to the next process in the ready queue.
  • Otherwise, if the CPU burst of the currently running process is longer than 1 time quantum,
    • the timer will go off and will cause an interrupt to the OS.
    • A context switch will be executed, and the process will be put at the tail of the ready queue.
    • The CPU scheduler will then select the next process in the ready queue.

  Figure 5.11: Round-robin scheduling. (a) The list of runnable processes. (b) The list of runnable processes after B uses up its quantum.

  
• The average waiting time under the RR policy is often long. Consider the following set of processes that arrive at time 0, with the length of the CPU burst given in milliseconds: (a time quantum of 4 milliseconds)
  

  	Burst	Waiting	Turnaround
  Process	Time	Time	Time
  $P_1$	24	6	30
  $P_2$	3	4	7
  $P_3$	3	7	10
  Average	-	5.66	15.66

• Using round-robin scheduling, we would schedule these processes according to the following chart:

  
• In the RR scheduling algorithm, no process is allocated the CPU for more than 1 time quantum in a row (unless it is the only runnable process).
• If a process's CPU burst exceeds 1 time quantum, that process is preempted and is put back in the ready queue. The RR scheduling algorithm is thus pre-emptive.
  • If there are $n$ processes in the ready queue and the time quantum is q, then each process gets $\frac{1}{n}$ of the CPU time in chunks of at most q time units.
  • Each process must wait no longer than $(n - 1)*q$ time units until its next time quantum.
  • For example, with five processes and a time quantum of 20 milliseconds, each process will get up to 20 milliseconds every 100 milliseconds.
• The performance of the RR algorithm depends heavily on the size of the time quantum.
  • If the time quantum is extremely large, the RR policy is the same as the FCFS policy.
  • If the time quantum is extremely small (say, 1 millisecond), the RR approach is called processor sharing and (in theory) creates the appearance that each of $n$ processes has its own processor running at $\frac{1}{n}$ the speed of the real processor.
• We need also to consider the effect of context switching on the performance of RR scheduling (see Fig. 5.12). 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, etc.
  • Let us assume that we have only one process of 10 time units.
  • If the quantum is 12 time units, the process finishes in less than 1 time quantum, with no overhead.
  • If the quantum is 6 time units, however, the process requires 2 quanta, resulting in a context switch.
  • If the time quantum is 1 time unit, then nine context switches will occur, slowing the execution of the process accordingly

  Figure 5.12: The way in which a smaller time quantum increases context switches.

  
• Thus, we want the time quantum to be large with respect to the context-switch time.
  • If the context-switch time is approximately 10 percent of the time quantum, then about 10 percent of the CPU time will be spent in context switching.
  • In practice, most modern systems have time quanta ranging from 10 to 100 milliseconds.
  • The time required for a context switch is typically less than 10 microseconds; thus, the context-switch time is a small fraction of the time quantum.
• 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.
• Poor average waiting time when job lengths are identical; Imagine 10 jobs each requiring 10 time slices, all complete after about 100 time slices, even FCFS is better!
• In general, the average turnaround time can be improved if most processes finish their next CPU burst in a single time quantum. If context-switch time is added in, the average turnaround time increases for a smaller time quantum, since more context switches are required.
• Although the time quantum should be large compared with the context-switch time, it should not be too large. If the time quantum is too large, RR scheduling degenerates to FCFS policy.

  Figure 5.13: An example to Round Robin.