The Round Robin scheduling is very much similar to FCFS. The only difference between RR and FCFS scheduling is, RR is preemptive scheduling whereas FCFS is non-preemptive scheduling. Every process is allocated to CPU in the ready queue for a single time slice. Here, a ready queue is similar to a circular queue. Every time slice is between 10 to 100 ms. Due to this fact, it is called time slice scheduling.
The procedure of RR Scheduling is as follows:
- A new process is added to the end of the queue.
- The process is picked for execution from the front of the queue.
- The timer is set to interrupt after a one-time slice.
- After one time slice, the process either completes or moved to the end of the queue
So there may be two cases as follows:
- In the first case, the process CPU burst time is less than a single time slice, then the process will be completely executed and will release CPU and the next process is executed
- In the second case, an interrupt occurs at a single time slice. With the help of the context switch, the CPU will then be allocated to the next process and this process will be moved to the tail of the queue Then the next process is executed.
Table of Contents
Example
Let the size of the time slice be 4ms, P1 takes CPU for the first 4ms. After that, an interrupt occurs and P1 is put into the tail of the ready queue. P2 is executed for 4ms then it is put into the tail of the ready queue. After that P3 is executed for 4ms, then it is completed and releases the CPU without interruption. Again the turn of P1 comes for 4ms. This process continues.
The Gantt chart for the following process will be like this:
Waiting time for process P1 = 0 + 8 + 1 = 9ms
Now, Waiting time for process P2 = 4 + 8 = 12ms
Waiting time for process P3 = 8ms
Total waiting time = 29ms
Average waiting time = 29/3 = 9.67ms
The performance of RR scheduling depends on the size of the time slice. If the time slice is too large, then RR is just like FCFS. If the time slice is too small, then RR is just like process sharing i.e., a process will take much time to wait.
Advantages of RR Scheduling
- It supports time sharing.
- RR uses quantum.
- It can handle multiple processes.
- If the process burst time is smaller than quantum then the process executes in the first quantum.
Disadvantages of RR Scheduling
- Process execution is slower if the burst time is larger than quantum.
- If the quantum is large, it works as FCFS.
- The large process has to wait for the ending of the small process.
Implementation
C program for Round Robin Scheduling
#include<stdio.h>
#include<conio.h>
int main()
{
int n,i,qt,count=0,temp,sq=0,bt[10],wt[10],tat[10],rem_bt[10];
//n signifies number of process
//i is for using loops
//qt denotes Quantum Time
//count denotes when one process is completed
//temp and sq are temproray variables
//bt[10] denotes burst time
//wt[10] denotes waiting time
//tat[10] denotes turnaround time
//rem_bt[10] denotes remaining burst time
float awt=0,atat=0;
//awt represents average waiting time
//atat represents average turnaround time
printf("Enter number of process (upto 10) = ");
scanf("%d",&n);
printf("Enter burst time of process\n");
for (i=0;i<n;i++)
{
printf("P%d = ",i+1);
scanf("%d",&bt[i]);
rem_bt[i]=bt[i];
}
printf("Enter quantum time ");
scanf("%d",&qt);
while(1)
{
for (i=0,count=0;i<n;i++)
{
temp=qt;
if(rem_bt[i]==0)
{
count++;
continue;
}
if(rem_bt[i]>qt)//changing the value of remaining burst time
rem_bt[i]=rem_bt[i]-qt;
else
if(rem_bt[i]>=0)//if process is exhausted then setting remaining burst time tozero
{
temp=rem_bt[i];
rem_bt[i]=0;
}
sq=sq+temp; //calculating turnaround time
tat[i]=sq;
}
if(n==count)//breaking the loop when all process are exhausted
break;
}
printf("\nProcess\tBurst Time\tTurnaround Time\tWaiting Time\n");
for(i=0;i<n;i++)
{
wt[i]=tat[i]-bt[i];
awt=awt+wt[i];
atat=atat+tat[i];
printf("\n%d\t%d\t\t%d\t\t%d",i+1,bt[i],tat[i],wt[i]);
}
awt=awt/n;
atat=atat/n;
printf("\nAverage waiting Time = %f\n",awt);
printf("Average turnaround time = %f",atat);
return 0;
}
Enter number of process (upto 10) = 3 Enter burst time of process P1 = 21 P2 = 5 P3 = 4 Enter quantum time 4
Process Burst Time Turnaround Time Waiting Time 1 20 29 9 2 5 17 12 3 4 12 8 Average waiting Time = 9.666667 Average turnaround time = 19.333334
Java program for Round Robin Scheduling
import java.util.Scanner;
class main
{
public static void main(String args[])
{
int n,i,qt,count=0,temp,sq=0,bt[],wt[],tat[],rem_bt[];
float awt=0,atat=0;
bt = new int[10];
wt = new int[10];
tat = new int[10];
rem_bt = new int[10];
Scanner s=new Scanner(System.in);
System.out.print("Enter number of process (upto 10) = ");
n = s.nextInt();
System.out.print("Enter burst time of process\n");
for (i=0;i<n;i++)
{
System.out.print("P"+i+" = ");
bt[i] = s.nextInt();
rem_bt[i] = bt[i];
}
System.out.print("Enter quantum time = ");
qt = s.nextInt();
while(true)
{
for (i=0,count=0;i<n;i++)
{
temp = qt;
if(rem_bt[i] == 0)
{
count++;
continue;
}
if(rem_bt[i]>qt)
rem_bt[i]= rem_bt[i] - qt;
else
if(rem_bt[i]>=0)
{
temp = rem_bt[i];
rem_bt[i] = 0;
}
sq = sq + temp;
tat[i] = sq;
}
if(n == count)
break;
}
System.out.print("\nProcess\tBurst Time\tTurnaround Time\tWaiting Time\n");
for(i=0;i<n;i++)
{
wt[i]=tat[i]-bt[i];
awt=awt+wt[i];
atat=atat+tat[i];
System.out.print("\n "+(i+1)+"\t "+bt[i]+"\t\t "+tat[i]+"\t\t "+wt[i]);
}
awt=awt/n;
atat=atat/n;
System.out.println("\nAverage waiting Time = "+awt);
System.out.println("Average turnaround time = "+atat);
}
}
Enter number of process (upto 10) = 3 Enter burst time of process P1 = 29 P2 = 51 P3 = 42 Enter quantum time 6
Process Burst Time Turnaround Time Waiting Time 1 29 77 48 2 51 122 71 3 42 113 71 Average waiting Time = 63.333332 Average turnaround time = 104.0
Complexity Analysis
Time Complexity
O(S) where S denotes the sum of burst time of all the input processes.
Space Complexity
O(S) where S denotes the sum of burst time of all the input processes.