Round Robin Scheduling

1. What is the Round Robin algorithm?

Round Robin is one of the oldest and easiest preemptive scheduling algorithms which is often used in interactive systems. Quantum and ready-queue are important terms to know when talking about this scheduling technique. The Quantum or time slice is the period of time for which a process is allowed to run on a CPU in a preemptive multitasking system. The ready-queue consists of all processes in the state ready, so they're eager to get the  CPU.

2. How does the Round Robin algorithm work?

  1. All processes/threads in the ready state are located in a queue (the ready queue).
  2. The quantum is assigned to each process. The first process in the ready queue obtains the CPU for the duration of the quantum. While the process is running on the CPU its process state is "running".
  3. If the process is still active after the quantum has been depleted (which means the process still has work to do) and at least one process is waiting in the ready queue, it will be preempted, set into the ready state and inserted at the end of the ready queue. The next process in the ready queue gets the CPU afterwards.
  4. A blocked process which switches into the ready state will be inserted at the end of the ready queue.

3. Round Robin Example

Given a system with the following processes:

  • Process P1
    Arrival: 0ms
    CPU burst: 100ms
  • Process P2 
    Arrival: 10ms
    CPU burst: 40ms
  • Process P3
    Arrival: 20ms
    CPU burst: 50ms
  • Process P4
    Arrival: 30ms
    CPU burst: 30ms

The scheduler of this systems uses the Round Robin scheduling algorithm with a quantum of 30ms, which means a process can run up until 30ms without interruption.

  • At the beginning the ready queue only consists of P1. This process is directly assigned to the CPU and can use up its quantum of 30ms completely.
  • After 10ms process P2 arrives in the ready queue.
  • After another 10ms process P3 arrives.
  • 30ms after process P1 started his work, process P4 arrives.
  • After P1 depleted its quantum, it switches into the ready state and is inserted at the end of the ready queue.
  • After that, P2 gets the CPU and uses up its whole quantum. But the process is not done yet. Therefore, it switches into the ready state and is inserted at the end of the ready queue.
  • P3 runs for 30ms and still needs to run 20ms afterwards.
  • P4 runs for 30ms and completes its task. The process  is terminated  and not sent back to the ready queue.
  • P1 is the first process in the ready queue again and runs for 30ms on the CPU. But it still needs to run for 40ms  afterwards. Nevertheless, the dispatcher sends P1 back to the ready queue.
  • Shortly after that, P2 gets the chance to complete its task. It doesn't even need the whole quantum of 30ms, but only 33% of it, namely 10ms.
  • Now P3 starts working again. It also uses only 2/3 of its quantum and terminates.
  • Now P1 is the only process in the ready queue. It gets the CPU directly and can use up its whole quantum. 
  • After P1 depleted its quantum it is not preempted and sent back to the ready queue since no process is waiting there, so P1 can work 10 more ms until the job is done.

4. Die Wahl des Quantums

The choice of the quantum determines the success of this scheduling strategy.

  • If the time slice is too long, processes will take longer to respond to input which is disadvantageous for I/O resp. interactive processes.
  • If the time slice is too short then the scheduler will consume too much processing time caused by the overhead of a context switch.

A lot of performance issues can be solved by throwing hardware at a problem. This could also be a solution for scheduling strategies spread over multiple CPUs. But just defining a larger quantum does not necessarily help. A typical quantum for Round Robin lies between 10ms and 100ms.

5. Fairness

Round Robin schedules unfair for I/O processes since they can only use up a fraction of their quantum and then they have to wait for the end of CPU intensive processes. As a solution the virtual Round Robin algorithm has been developed where unused quantums are recorded as a time credit.