by Dinesh Thakur Category: Operating System

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
P1 0 5
P2 1 6
P3 2 3
P5 3 1
P6 4 5
P7 5 4

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.
Ready Queue
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
5

Gantt chart

P1 will be executed for 4 units.

Round robin Gantt Chart 1

Ready Queue
Midwhile, 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.

P2      P3    P4    P5    P1   
6 3 1 5 1

GANTT chart
Now the gantt chart will be like this.

Round robin Gantt Chart 2

Ready queue
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.

P3 P4 P5 P1 P6 P2
3 1 5 1 4

2

GANTT CHART

Now, P3 will be executed for 3 units of time slice as its bursts time is 3 units.

Round robin Gantt Chart 3

Ready queue
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.

P4 P5 P6 P1 P2
1 5 1 4 2

GANTT CHART

Round robin Gantt Chart 4

Ready queue
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.

P5 P6 P1 P2
5 1 4 2

GANTT chart

Round robin Gantt Chart 5

Ready Queue
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.

P1 P6 P2 P5
1 4 2 1

 

GANTT chart
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.

Round robin Gantt Chart 6

Ready queue
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.

P6 P2 P5
4 2 1

 

GANTT CHART
Now P6 has units of 4 units of bursts time. So it will get executed in 4 units of time slice.

Round robin Gantt Chart 7

Ready queue
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.

P2 P5
2 1

 

GANTT CHART
Now P2 will be executed again and it requires only 2 units of bursts time. So now it will be completed.

Round robin Gantt Chart 8

Ready queue
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.

P5
1

GANTT CHART
The process P5 will get executed until it get completed as it is the only process left in the ready queue.

Round robin Gantt Chart 9

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

Round robin Result Table

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.





About Dinesh Thakur

Dinesh ThakurDinesh Thakur holds an B.SC (Computer Science), MCSE, MCDBA, CCNA, CCNP, A+, SCJP certifications. Dinesh authors the hugely popular blog. Where he writes how-to guides around Computer fundamental , computer software, Computer programming, and web apps. For any type of query or something that you think is missing, please feel free to Contact us.



Related Articles