What is the round robin CPU scheduling algorithm?

Overview

Round robin scheduling is a pre-emptive algorithm commonly used in operating systems to schedule processes.

In round robin scheduling, the CPU is assigned to each process in a queue turn by turn for a time period. Once the time is over, the process is moved to the end of the queue and the CPU is shifted to the next process in the queue. In this manner, processes are handled from a cyclic queue until the burst time of a process has passed.

Example

You will be able to understand round robin scheduling better through the example given below. First, we need a list of processes, including their arrival and burst times. The quantum time per process will be 3, so every process will execute for 3 seconds each.

Time = 0

At $time=0$, the processes P1 and P2 enter the queue according to their arrival time and wait to be executed. Since P1 arrives first, it is taken out of the waiting queue and executed for 3 seconds.

Time = 2

At $time=2$, P3 and P4 enter the waiting queue.

Time = 3

At $time=3$, P1 stops executing and its burst time is over. Hence, it is not added back to the waiting queue. P2 is removed from the waiting queue and executed for the next 3 seconds.

Time = 6

At $time=6$, P2 is done executing and its burst time is over. Hence, it isn’t added back to the waiting queue. We remove the next process, P3, from the waiting queue and execute it for the next 3 seconds.

Time = 9

At $time=9$, P3 stops executing and is added back to the waiting queue because its burst time is not over. Then, we remove the next process, P4, from the waiting queue and execute it for the next 3 seconds.

Time = 12

At $time=12$, P4 stops executing and is added back to the waiting queue because its burst time is not over yet. Then, we remove process P3 from the waiting queue and execute it. As P3 has a burst time of 4 and has completed an execution of 3 seconds already, it is only executed for the next 1 second.

Time = 13

At $time=13$, P3 is done executing and its burst time is over. Hence, it is not added back to the waiting queue. Then, process P4 is executed for the next 1 second only, as it was previously executed for 3 of its 4-second burst time.

Time = 14

At $time=14$, the execution of all the processes is complete.

Average waiting time

To deduce the average waiting time, we calculate the waiting time for each process and divide it by the total number of processes.

P1 waiting time: 0
P2 waiting time: 0
P3 waiting time: 9
P4 waiting time: 10

Average waiting time: $\frac {9+10}{4}= 4.75$

Advantages and disadvantages

The following is a table of all the advantages and disadvantages of using the round robin scheduling algorithm.