Let’s understand about Round Robin Algorithm or Round Robin Scheduling and how to implement this in C programming language.
What is Round Robin Algorithm / Round Robin Scheduling:
Round-robin (RR) is one of the algorithms employed by process and network schedulers in computing. As the term is generally used, time slices (also known as time quanta) are assigned to each process in equal portions and in circular order, handling all processes without priority (also known as cyclic executive). Round-robin scheduling is simple, easy to implement, and starvation-free. Round-robin scheduling can also be applied to other scheduling problems, such as data packet scheduling in computer networks. It is an operating system concept.
The name of the algorithm comes from the round-robin principle known from other fields, where each person takes an equal share of something in turn.
Process scheduling:
Round-robin algorithm is a pre-emptive algorithm as the scheduler forces the process out of the CPU once the time quota expires.
For example, if the time slot is 100 milliseconds, and job1 takes a total time of 250 ms to complete, the round-robin scheduler will suspend the job after 100 ms and give other jobs their time on the CPU. Once the other jobs have had their equal share (100 ms each), job1 will get another allocation of CPU time and the cycle will repeat. This process continues until the job finishes and needs no more time on the CPU.
- Job1 = Total time to complete 250 ms (quantum 100 ms).
- First allocation = 100 ms.
- Second allocation = 100 ms.
- Third allocation = 100 ms but job1 self-terminates after 50 ms.
- Total CPU time of job1 = 250 ms
Consider the following table with the arrival time and execute time of the process with the quantum time of 100ms to understand the round-robin scheduling:
Process name | Arrival time | Execute time |
---|---|---|
P0 | 0 | 250 |
P1 | 50 | 170 |
P2 | 130 | 75 |
P3 | 190 | 100 |
P4 | 210 | 130 |
P5 | 350 | 50 |
Program to implement Round Robin Algorithm in C:
#include<stdio.h> int main() { int count,j,n,time,remain,flag=0,time_quantum; int wait_time=0,turnaround_time=0,at[10],bt[10],rt[10]; printf("Enter Total Process:\t "); scanf("%d",&n); remain=n; for(count=0;count<n;count++) { printf("Enter Arrival Time and Burst Time for Process Process Number %d :",count+1); scanf("%d",&[count]); scanf("%d",&[count]); rt[count]=bt[count]; } printf("Enter Time Quantum:\t"); scanf("%d",&time_quantum); printf("\n\nProcess\t|Turnaround Time|Waiting Time\n\n"); for(time=0,count=0;remain!=0;) { if(rt[count]<=time_quantum && rt[count]>0) { time+=rt[count]; rt[count]=0; flag=1; } else if(rt[count]>0) { rt[count]-=time_quantum; time+=time_quantum; } if(rt[count]==0 && flag==1) { remain--; printf("P[%d]\t|\t%d\t|\t%d\n",count+1,time-at[count],time-at[count]-bt[count]); wait_time+=time-at[count]-bt[count]; turnaround_time+=time-at[count]; flag=0; } if(count==n-1) count=0; else if(at[count+1]<=time) count++; else count=0; } printf("\nAverage Waiting Time= %f\n",wait_time*1.0/n); printf("Avg Turnaround Time = %f",turnaround_time*1.0/n); return 0; }
OUTPUT:
$ ./a.out Enter Total Process : 4 Enter Arrival Time and Burst Time for Process Number 1: 0 9 Enter Arrival Time and Burst Time for Process Number 2: 1 5 Enter Arrival Time and Burst Time for Process Number 3: 2 3 Enter Arrival Time and Burst Time for Process Number 4: 3 4 Enter Time Quantum: 5 Process | Turnaround Time | Waiting Time P[2] | 9 | 4 P[3] | 11 | 8 P[4] | 14 | 10 P[1] | 21 | 12 Average waiting Time= 8.500000 Avg turnaround Time= 13.750000
Comment in case of any query, suggestion or improvements.
#include
int main()
{
int i,j,n,time,remain,flag=0,t;
int wt=0,tt=0,at[10],bt[10],rt[10];
printf(“Enter Total Process: “);
scanf(“%d”,&n);
remain=n;
printf(“Enter Burst Time and Arrival Time for:\n”);
for(i=0;i<n;i++)
{
printf("P[%d] :\n",i+1);
printf("BURST TIME: ");
scanf("%d",&bt[i]);
printf("ARIVAL TIME: ");
scanf("%d",&at[i]);
rt[i]=bt[i];
}
printf("Enter Time Quantum:");
scanf("%d",&t);
printf("\nProcess\t\tBurst Time\tWaiting Time\tTurnaround Time");
for(time=0,i=0;remain!=0;)
{
if(rt[i]0)
{
time+=rt[i];
rt[i]=0;
flag=1;
}
else if(rt[i]>0)
{
rt[i]-=t;
time+=t;
}
if(rt[i]==0 && flag==1)
{
remain–;
printf(“\nP[%d]\t\t%d\t\t%d\t\t%d”,i+1,bt[i],time-at[i],time-at[i]-bt[i]);
wt+=time-at[i]-bt[i];
tt+=time-at[i];
flag=0;
}
if(i==n-1)
i=0;
else if(at[i+1]<=time)
i++;
else
i=0;
}
printf("\n");
printf("\nAvg Waiting Time= %fms",wt*1.0/n);
printf("\nAvg Turnaround Time = %fms",tt*1.0/n);
printf("\n");
return 0;
}
#include
int main()
{
int count,j,n,time,remain,flag=0,time_quantum;
int wait_time=0,turnaround_time=0,at[10],bt[10],rt[10];
printf(“Enter Total Process:\t “);
scanf(“%d”,&n);
remain=n;
for(count=0;count<n;count++)
{
printf("Enter Arrival Time and Burst Time for Process Process Number %d :",count+1);
scanf("%d",&at[count]);
scanf("%d",&bt[count]);
rt[count]=bt[count];
}
printf("Enter Time Quantum:\t");
scanf("%d",&time_quantum);
printf("\n\nProcess\t|Turnaround Time|Waiting Time\n\n");
for(time=0,count=0;remain!=0;)
{
if(rt[count]0)
{
time+=rt[count];
rt[count]=0;
flag=1;
}
else if(rt[count]>0)
{
rt[count]-=time_quantum;
time+=time_quantum;
}
if(rt[count]==0 && flag==1)
{
remain–;
printf(“P[%d]\t|\t%d\t|\t%d\n”,count+1,time-at[count],time-at[count]-bt[count]);
wait_time+=time-at[count]-bt[count];
turnaround_time+=time-at[count];
flag=0;
}
if(count==n-1)
count=0;
else if(at[count+1]<=time)
count++;
else
count=0;
}
printf("\nAverage Waiting Time= %f\n",wait_time*1.0/n);
printf("Avg Turnaround Time = %f",turnaround_time*1.0/n);
return 0;
}