Round Robin Scheduling Algorithm
Round Robin scheduling algorithm is one of the most popular scheduling algorithm which can actually be implemented in most of the operating systems. This is the preemptive version of first come first serve scheduling. The Algorithm focuses on Time Sharing. In this algorithm, every process gets executed in a cyclic way. A certain time slice is defined in the system which is called time quantum. Each process present in the ready queue is assigned the CPU for that time quantum, if the execution of the process is completed during that time then the process will terminate else the process will go back to the ready queue and waits for the next turn to complete the execution.
Advantages
· It can be actually implementable in the system because it is not depending on the burst time.
· It doesn't suffer from the problem of starvation or convoy effect.
· All the jobs get a fare allocation of CPU.
Disadvantages
In the following example, there are six processes named as P1, P2, P3, P4, P5 and P6. Their arrival time and burst time are given below in the table. The time quantum of the system is 4 units.
Process ID | Arrival Time | Burst Time |
1 | 0 | 5 |
2 | 1 | 6 |
3 | 2 | 3 |
4 | 3 | 1 |
5 | 4 | 5 |
6 | 6 | 4 |
According to the algorithm, we have to maintain the ready queue and the Gantt chart. The structure of both the data structures will be changed after every scheduling.
Initially, at time 0, process P1 arrives which will be scheduled for the time slice 4 units. Hence in the ready queue, there will be only one process P1 at starting with CPU burst time 5 units.
P1 |
5 |
The P1 will be executed for 4 units first.
Meanwhile the execution of P1, four more processes P2, P3, P4 and P5 arrives in the ready queue. P1 has not completed yet, it needs another 1 unit of time hence it will also be added back to the ready queue.
P2 | P3 | P4 | P5 | P1 |
6 | 3 | 1 | 5 | 1 |
After P1, P2 will be executed for 4 units of time which is shown in the Gantt chart.
During the execution of P2, one more process P6 is arrived in the ready queue. Since P2 has not completed yet hence, P2 will also be added back to the ready queue with the remaining burst time 2 units.
P3 | P4 | P5 | P1 | P6 | P2 |
3 | 1 | 5 | 1 | 4 | 2 |
After P1 and P2, P3 will get executed for 3 units of time since its CPU burst time is only 3 seconds.
Since P3 has been completed, hence it will be terminated and not be added to the ready queue. The next process will be executed is P4.
P4 | P5 | P1 | P6 | P2 |
1 | 5 | 1 | 4 | 2 |
After, P1, P2 and P3, P4 will get executed. Its burst time is only 1 unit which is lesser then the time quantum hence it will be completed.
The next process in the ready queue is P5 with 5 units of burst time. Since P4 is completed hence it will not be added back to the queue.
P5 | P1 | P6 | P2 |
5 | 1 | 4 | 2 |
P5 will be executed for the whole time slice because it requires 5 units of burst time which is higher than the time slice.
P5 has not been completed yet; it will be added back to the queue with the remaining burst time of 1 unit.
P1 | P6 | P2 | P5 |
1 | 4 | 2 | 1 |
The process P1 will be given the next turn to complete its execution. Since it only requires 1 unit of burst time hence it will be completed.
P1 is completed and will not be added back to the ready queue. The next process P6 requires only 4 units of burst time and it will be executed next.
P6 | P2 | P5 |
4 | 2 | 1 |
P6 will be executed for 4 units of time till completion.
Since P6 is completed, hence it will not be added again to the queue. There are only two processes present in the ready queue. The Next process P2 requires only 2 units of time.
P2 | P5 |
2 | 1 |
P2 will get executed again, since it only requires only 2 units of time hence this will be completed.
Now, the only available process in the queue is P5 which requires 1 unit of burst time. Since the time slice is of 4 units hence it will be completed in the next burst.
P5 |
1 |
P5 will get executed till completion.
The completion time, Turnaround time and waiting time will be calculated as shown in the table below.
As, we know,
Turn Around Time = Completion Time - Arrival Time
Waiting Time = Turn Around Time - Burst Time
Process ID | Arrival Time | Burst Time | Completion Time | Turn Around Time | Waiting Time |
1 | 0 | 5 | 17 | 17 | 12 |
2 | 1 | 6 | 23 | 22 | 16 |
3 | 2 | 3 | 11 | 9 | 6 |
4 | 3 | 1 | 12 | 9 | 8 |
5 | 4 | 5 | 24 | 20 | 15 |
6 | 6 | 4 | 21 | 15 | 11 |
Avg Waiting Time = (12+16+6+8+15+11)/6 = 76/6 units