Round Robin Scheduling

Difficulty Level Medium
Frequently asked in Amazon Facebook Google Microsoft
Algorithm Operating SystemsViews 3846

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:

  1. A new process is added to the end of the queue.
  2. The process is picked for execution from the front of the queue.
  3. The timer is set to interrupt after a one-time slice.
  4. After one time slice, the process either completes or moved to the end of the queue

So there may be two cases as follows:

  1. 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
  2. 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.

Example

Round Robin Scheduling

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:

Round Robin Scheduling

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

  1. It supports time sharing.
  2. RR uses quantum.
  3. It can handle multiple processes.
  4. If the process burst time is smaller than quantum then the process executes in the first quantum.

Disadvantages of RR Scheduling

  1. Process execution is slower if the burst time is larger than quantum.
  2. If the quantum is large, it works as FCFS.
  3. 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.

Reference

Translate »