In this post, we will learn about round robin scheduling algorithm in operating system with example. In previous post, we have already seen basic terms, formulas in cpu scheduling and First Come First Serve Scheduling Algorithm.
Round robin scheduling algorithm is one of the important scheduling algorithm in job scheduling. It is the preemptive scheduling algorithm. Round robin uses time slice (fixed time period) for execution of the process, called time quantum.
This scheduling algorithm is used in time sharing system.
– Once a process is executed for a given time period, the process is preempted and the next process execution starts for the given time period.
– Round robin scheduling uses context switching to save states of preempted process.
Let us take an example to understand the scheduling –
Now, we will take different examples to demonstrate how does round robin cpu scheduling works.
Assume there are 5 processes with process ID and burst time given below
– Time quantum: 2
– Assume that all process arrives at 0.
Now, we will calculate average waiting time for these processes to complete.
We can represent execution of above processes using GANTT chart as shown below –
– First p1 process is picked from the ready queue and executes for 2 per unit time (time slice = 2).
If arrival time is not available, it behaves like FCFS with time slice.
– After P2 is executed for 2 per unit time, P3 is picked up from the ready queue. Since P3 burst
time is 2 so it will finish the process execution at once.
– Like P1 & P2 process execution, P4 and p5 will execute 2 time slices and then again it will start
from P1 same as above.
Waiting time = Turn Around Time – Burst Time
P1 = 19 – 6 = 13
P2 = 20 – 5 = 15
P3 = 6 – 2 = 4
P4 = 15 – 3 = 12
P5 = 23 – 7 = 16
Average waiting time = (13+15+4+12+16) / 5 = 12
Assume there are 6 processes with id, burst time and arrival time as shown below –
|PID||Arrival Time||Burst Time|
Time quantum = 2
Now, we will calculate average waiting time, completion time, turn around time for each processes’s execution.
Execution of above processes can be represented using GANTT Chart as shown below –
At the arrival time = 0, CPU scheduler picks up the p1 process from the ready queue and it will run per 2 unit of time according to given time quantum.
At arrival time = 2, there are 3 processes available P1, P2 & P3. Executed process will be placed at the tail of the ready queue. Scheduler will select the next process from the ready queue. So, P2 will execute first. After the execution of P2 process, P3 will be the next the process in the queue. So, P3 will complete execution.
According to the context switch every executed process will be placed at the tail of the ready queue and get a chance for execution again according to each position.
Every process will follow the same procedure. It is good practice to make a separate queue and place the process executed process at the tail of the queue. So, it will be easy to understand the next process which is going to be executed.
P1 = 8,
P2 = 18,
P3 = 6,
P4 = 9,
P5 = 21,
P6 = 19
Turn Around time:
P1 = 8 – 0 = 8,
P2 = 18 -1 = 17,
P3 = 6 – 2 = 4,
P4 = 9 – 3 = 6,
P5 = 21 – 4 = 17,
P6 = 19 – 6 = 13
P1 = 8 – 4 = 4,
P2 = 17 – 5 = 12,
P3 = 4 – 2 = 2,
P4 = 6 – 1 = 5,
P5 = 17 – 6 = 11
Note: In the Round Robin scheduling algorithm, as the time quantum decreases context switching increases. The increase in time quantum value results in time starvation which may put many processes on hold. So, time quantum should neither be large nor be small.
– If time quantum becomes infinity, Round Robin scheduling algorithm gradually become FCFS scheduling algorithm.
Advantages of Round Robin Scheduling
1. In RR all the processes have the equal priority because of fixed time quantum.
2. Starvation will never occur because each process in every RR cycle will be schedule for a fixed time slice or time quantum.
Disadvantages of Round Robin Scheduling
1. In RR, throughput depends on the time quantum. if the time quantum is increased, the throughput will be decreased.
2. If the time quantum decreases, it will affect the CPU efficiency.
In this post, we have learnt about Round Robin Scheduling algorithm in operating system.