Round-Robin Scheduling

This is another technique to execute processes in CPU. This is the last technique but not the least. I will give you all a very clear understanding of this with the help of a numerical and at the end I will give you the code to implement Round-Robin Scheduling. So, let's get started, shall we?

In Round-Robin Scheduling each process executes for some time quantum(time slice) in a cyclic manner. This scheduling technique is same as FCFS but the only difference is that each process is executed for equal time quantum.

Characteristics of Round-Robin Scheduling

It is a preemptive scheduling algorithm.
In this CPU executes a process for some time quantum and then moves to a new process.
Time slice should be minimal in order to improve efficiency, however it might also differ from OS to OS.
It is one of the oldest scheduling techniques.

Numerical:

Schedule the processes given in the picture below according to Round-Robin Scheduling where time slice is of 4ms. Draw a gantt chart. Also find waiting and turn around time for each process.

We will consider a table T which will help us determine remaining time for each process.

1. At arrival time 0 process P1 comes into ready queue. It will be executed for 4ms because time slice is of 4ms. Now, remaining time for P1 is 4ms and we will place this process in table T.
2. At arrival time 4 we have 3 processes to be executed. We will execute P2 for 4ms because time slice is of 4ms. Now, remaining time for P2 is 0 so we won't push it into table T.
3. Then P3 will be executed for 4ms. After execution, P3 has 5ms remaining time so we will place P3 into table T.
4. Then P4 will be executed for 4ms. After execution, P4 has 1ms remaining time so we will place P4 into table T.
5. Now, there are no new processes so we will execute the processes present in table T sequentially.
6. In table T we have P1 with remaining time 4ms, P3 with remaining time 5ms, P4 with remaining time 1ms.
7. P1 will be executed for 4ms. After execution, P1 has remaining time 0ms so it has executed completely.
8. Now we will execute P3 for 4ms. After execution, P3 has remaining time 1ms so it will be pushed into table T again.
9. Next, P4 will be executed for 4ms. But P4 require only 1ms so it will execute for 1ms only. After execution, P4 has remaining time 0ms hence it has also completed execution.
10. Only, one process remaining which is P3. So, P3 will be executed for 1ms.

Gantt Chart:

Waiting Time for each process

Waiting time is computed by the formula starting execution time - arrival time of a process.
Process Starting execution time - arrival time Waiting time
P1 20 - 8 12
P2 7 - 4 3
P3 24 - 9 15
P4 22 - 5 17

Turn around Time for each Process

Turn around time is computed by the formula completion time - arrival time of a process.
Process Completion time - arrival time Waiting time
P1 20 - 0 20
P2 8 - 1 7
P3 26 - 2 24
P4 25 - 3 22

Implementation in C++

#include<iostream> 
using namespace std; 

// Function to find the waiting time for all 
// processes 
void findWaitingTime(int processes[], int n, 
   int bt[], int wt[], int quantum) 
{ 
 // Make a copy of burst times bt[] to store remaining 
 // burst times. 
 int rem_bt[n]; 
 for (int i = 0 ; i < n ; i++) 
  rem_bt[i] = bt[i]; 

 int t = 0; // Current time 

 // Keep traversing processes in round robin manner 
 // until all of them are not done. 
 while (1) 
 { 
  bool done = true; 

  // Traverse all processes one by one repeatedly 
  for (int i = 0 ; i < n; i++) 
  { 
   // If burst time of a process is greater than 0 
   // then only need to process further 
   if (rem_bt[i] > 0) 
   { 
    done = false; // There is a pending process 

    if (rem_bt[i] > quantum) 
    { 
     // Increase the value of t i.e. shows 
     // how much time a process has been processed 
     t += quantum; 

     // Decrease the burst_time of current process 
     // by quantum 
     rem_bt[i] -= quantum; 
    } 

    // If burst time is smaller than or equal to 
    // quantum. Last cycle for this process 
    else
    { 
     // Increase the value of t i.e. shows 
     // how much time a process has been processed 
     t = t + rem_bt[i]; 

     // Waiting time is current time minus time 
     // used by this process 
     wt[i] = t - bt[i]; 

     // As the process gets fully executed 
     // make its remaining burst time = 0 
     rem_bt[i] = 0; 
    } 
   } 
  } 

  // If all processes are done 
  if (done == true) 
  break; 
 } 
} 

// Function to calculate turn around time 
void findTurnAroundTime(int processes[], int n,int bt[], int wt[], int tat[]) 
{ 
 // calculating turnaround time by adding 
 // bt[i] + wt[i] 
 for (int i = 0; i < n ; i++) 
  tat[i] = bt[i] + wt[i]; 
} 

// Function to calculate average time 
void findavgTime(int processes[], int n, int bt[], int quantum) 
{ 
 int wt[n], tat[n], total_wt = 0, total_tat = 0; 

 // Function to find waiting time of all processes 
 findWaitingTime(processes, n, bt, wt, quantum); 

 // Function to find turn around time for all processes 
 findTurnAroundTime(processes, n, bt, wt, tat); 

 // Display processes along with all details 
 cout << "Processes "<< " Burst time "
  << " Waiting time " << " Turn around time\n"; 

 // Calculate total waiting time and total turn 
 // around time 
 for (int i=0; i<n; i++) 
 { 
  total_wt = total_wt + wt[i]; 
  total_tat = total_tat + tat[i]; 
  cout << " " << i+1 << "\t\t" << bt[i] <<"\t "
   << wt[i] <<"\t\t " << tat[i] <<endl; 
 } 

 cout << "Average waiting time = "
  << (float)total_wt / (float)n; 
 cout << "\nAverage turn around time = "
  << (float)total_tat / (float)n; 
} 

// Driver code 
int main() 
{ 
 // process id's 
 int processes[] = { 1, 2, 3}; 
 int n = sizeof processes / sizeof processes[0]; 

 // Burst time of all processes 
 int burst_time[] = {10, 5, 8}; 

 // Time quantum 
 int quantum = 2; 
 findavgTime(processes, n, burst_time, quantum); 
 return 0; 
}

OUTPUT:

Round-Robin Scheduling

Contact Form