Definition: Round robin scheduling is the preemptive scheduling in which every process get executed in a cyclic way, i.e. in this a particular time slice is allotted to each process which is known as time quantum. Every process, which is present in the queue for processing, CPU is assigned to that process for that time quantum. Now, if the execution of the process gets completed in that time quantum, then the process will get terminate otherwise the process will again go to the ready queue, and the previous process will wait for the turn to complete its execution.
The scheduling drives its name from the principle which is known as a round robin in which every person takes an equal share of anything they have in turn. We make use of round robin scheduling algorithm in a time-sharing system. It is generally used by those operating systems which has multiple clients to make use of resources.
Example of Round Robin Scheduling
In this example, we will take six processes P1, P2, P3, P4, P5 and P6 whose arrival and burst time are given in the table. The time quantum is 4 units.
|Processes||Arrival Time||Burst Time|
Now we have to maintain the ready queue and gantt chart in the algorithm again and again as their structures get changed after every scheduling.
Initially, at time 0, the process P1 will be executed for the 4 units of time quantum. So, in the starting in ready queue, there will be only one process P1.
P1 will be executed for 4 units.
Mid-while, during the execution of process P1, some other processes like P2, P3,P4 and P5 arises for the execution in the ready queue. As we know P1 has not completed since its time is 5 and we have 4 units of time slice. So, 1 unit is still left. So it will be again added at the back in ready queue.
Now the gantt chart will be like this.
During the execution time of P2, another process P6 arrives in the ready queue. Also, we know that P2 has not completed yet as its 2 units of burst time is still left. So, again we will add P2 in the ready queue at the back.
Now, P3 will be executed for 3 units of time slice as its bursts time is 3 units.
Now the process P3 is completed in the time slice of 4 units. So, we will not add P3 in the ready queue and now we will execute the next process P4.
The next process in the queue is P5 which has 5 units of bursts time. Again, the process P4 gets completed as it has only 1 unit of bursts time.
Now the process has not completed as 1 unit of burst time is left. So we add it in the ready queue in the back.
Now the process P1 will be executed so that it can complete its execution as its turn has come. As we know it requires only 1 unit of bursts time, so it will get completed.
As P1 also get completed. So , we will not add it to the ready queue. Now only three processes are left which are P6, P2 and P5.
Now P6 has units of 4 units of bursts time. So it will get executed in 4 units of time slice.
Since P6 is executed completely. so, we will not add it to the ready queue. Now only 2 processes left in the ready queue which are P2 and P5.
Now P2 will be executed again and it requires only 2 units of bursts time. So now it will be completed.
Only process left in the ready queue is P5 which requires only 1 unit of bursts time. As we know our time slice is of 4 units. So it will get completed in the next burst.
The process P5 will get executed until it get completed as it is the only process left in the ready queue.
Now we will calculate turn around time, completion time and average waiting time which is shown in the below table.
Turn around time= completion time- arrival time
Waiting time= turn around time – burst time
Average waiting time= (12+16+6+8+15+11)/6= 76/6 = 12.66 units
Advantages of round robin scheduling
• It is simple.
• It is easy to implement.
• It deals with all process without any priority.
• In this, all jobs get easily allocated to CPU.
• Like first come first serve scheduling, in this no problem of convoy effect or starvation is there.
• Round robin scheduling does not depend upon burst time. So it can be easily implementable on the system.
Disadvantages of round robin scheduling
• Since round robin scheduling depends upon time quantum. So deciding a perfect time quantum for scheduling is a very difficult task.
• If the time quantum is higher, then the response time of the system will also be higher.
• If the time quantum is lower, then there is higher context switching overhead.