Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Mar 27, 2024

Round Robin Scheduling | Part-2

gp-icon
Operating system track
Free guided path
14 chapters
83+ problems
gp-badge
Earn badges and level up
Operating System

Introduction 

Before you start with the Implementation, we would like to draw your attention to the theory part of the Round Robin Scheduling to quickly understand the algorithm and the code shared in this blog. Nonetheless, let us revisit some important points about the Round Robin algorithm: 

  • Round-robin scheduling allows an equal amount of CPU time for each process.

Illustration Image

  • It is a simple, straightforward to implement, and starvation-free scheduling algorithm since each process gets a fair share of CPU. 
  • It is preemptive since processes are only allotted CPU for a certain amount of time.
  • The downside is that it adds extra cost to context switching if the time quantum is exceedingly small.

Important terms 

  • Burst Time

Every process in a computer system necessitates time for its execution.  This time includes both CPU and I/O time. The CPU time is the time it takes the CPU to perform the process. The I/O time, on the other hand, is the time it takes the process to do an I/O activity. We generally disregard I/O time and solely evaluate CPU time for a process. As a result, burst time is the entire time required by the process to execute on the CPU.

  • Arrival Time 

As the name implies, Arrival time is when a process enters the ready state and is ready to be executed.

  • Exit Time/Completion Time

When a process completes its execution and exits the system, it is called exit time.

  • Turn Around Time 

The total time spent by the process from coming in the ready state for the first time to its completion is referred to as Turnaround Time. 

This mostly represents the time difference between completion and arrival. The formula for calculating is as follows: 

Turnaround Time = Completion Time - Arrival Time

  • Waiting Time 

The cumulative time spent by the process in the ready state waiting for the CPU is referred to as waiting time. 

It represents the time difference between the turnaround and the burst time. 

Waiting Time = Turnaround Time – Burst Time

  • Response Time 

Response time is the time spent when the process is in the ready state and gets the CPU for the first time. 

Response Time = Time at which the process gets the CPU for the first time - Arrival Time

 

Let us now discuss the Algorithm for the same:

Also see: Multiprogramming vs Multitasking, Open Source Operating System.

Algorithm 

  Ask no. of processes, arrival time, CPU burst time, time quantum from the user. 

In our example, we are using the below diagram which we’ll be providing as the input later in the Implementation: 

Time Quantum: 2 ms. 

 Time Quantum

  1. Sort the processes in order of arrival time in ascending order. There might be a chance that the arrival time of processes in an unordered way. However, in our case, the arrival time is already in sequential order. To simplify the implementation, it is recommended to sort the processes. 
  2. Use a simple FIFO queue. (We’ll simply take a ready queue externally, which works on the FIFO(First-in First-out) principle to push the processes). 
  3. Put the first process from the sorted list into the queue. 
  4. Use an array(visited[]) to check if the process is in the queue or not. This array will contain either True or False. Initially, the array will be set to False; as soon as the process enters the ready queue, the status will be updated as True. 
  5. Keep track of the time using a variable: current time. 
  6. If the process is getting CPU for the first time, record its start time as the current time. 
  7. Give a quantum unit of time to the process at the front in the queue and pop the process from the queue. 
  8. If the burst time of the process becomes 0, calculate the CT(Completion Time), TAT(Turn Around Time), WT(Waiting Time), and RT(Response Time) for the same process. 
  9. If some process(es) had arrived when it was executing, the first insert them into the queue. 
  10. If the current process has remaining burst time, push the process to the end of the queue again. 
  11. Keep doing this until all processes are completed. 

Implementation in C++ 

// C++ Implementation of the Round Robin CPU Scheduling Algorithm

#include<bits/stdc++.h>

using namespace std;
// Each process will have the following characteristics, and stored in an array
struct process_struct {
  int pid; // process ID from 0 ... n-1(where n will be the number of processes)
  int at; // arrival time 
  int bt; // CPU burst time
  int ct, wt, tat, rt, start_time; // completion time, waiting time, turn around time, response time, start time
  int bt_remaining; // remaining burst time left for the execution
}
prcs[100]; // array for the group of processes having the stated characteristics. 

// To sort the unordered arrival times
bool comparatorAT(struct process_struct a, struct process_struct b) {
  int x = a.at;
  int y = b.at;
  return x < y;
  //    if(x > y)
  //      return false;  // Apply sorting
  //    return true;   // no sorting
}
// To sort the Process IDs
bool comparatorPID(struct process_struct a, struct process_struct b) {
  int x = a.pid;
  int y = b.pid;
  return x < y;
}

int main() {
  int n, index; // n presents the total processes and index represents at which processID we are.
  int cpu_utilization;
  // ready queue to insert the processes in FIFO manner 
  queue < int > q;
  // Initialise an empty array visited[] which will be false initially. visited[] will be checking if the process is in the ready queue or not. If yes then it will be updated as TRUE else remain the same. 
  bool visited[100] = {
    false
  }, is_first_process = true;
  int current_time = 0;
  int completed = 0, tq, total_idle_time = 0;
  cout << "Enter total number of processes: ";
  cin >> n; // Accept the total processes
  // Loop for accepting the arrival time from the user
  for (int i = 0; i < n; i++) {
    cout << "\nEnter Process " << i << " Arrival Time: ";
    cin >> prcs[i].at;
    prcs[i].pid = i; // updating the process IDs starting from 0 -> n-1
  }
  // Loop for accepting the CPU burst time from the user
  for (int i = 0; i < n; i++) {
    cout << "\nEnter Process " << i << " Burst Time: ";
    cin >> prcs[i].bt;
    prcs[i].bt_remaining = prcs[i].bt; // All the modification will be made to the bt_remaining variable for all the processes. Hence the values are being copied. 
  }
  // Accept the time slice/quantum
  cout << "\nEnter the time quantum: ";
  cin >> tq;

  //sort the structure on the basis of Arrival time in increasing order
  sort(prcs, prcs + n, comparatorAT);
  // Now that we have sequential arrival time, burst time, bt_remaining, and pID in the array prcs[]. 
  // Insert 0 into the queue to begun the execution 
  q.push(0);
  // Update the status 
  visited[0] = true;
  // Run the while loop until the completed variable which is initialised as 0 will not be equal to n. 
  while (completed != n) {
    // Update the index value. The first time it would be 0 since 0 was inserted into the queue above. 
    index = q.front();
    //  Pop it 
    q.pop();
    // Apply the conditions 
    // First condition says: If the bt_remaining is the same as the bt of the current index meaning the process is not yet gone for the execution. 
    if (prcs[index].bt_remaining == prcs[index].bt) {
      // start time will have the maximum of the current time or the arrival time. 
      prcs[index].start_time = max(current_time, prcs[index].at);
      total_idle_time += (is_first_process == true) ? 0 : prcs[index].start_time - current_time;
      current_time = prcs[index].start_time;
      is_first_process = false;

    }
    // Check if the remaining burst time - tq(time quantum) is greater than 0. Means the process will have more than 1 context switching 
    if (prcs[index].bt_remaining - tq > 0) {
      // Update the bt_remaining 
      prcs[index].bt_remaining -= tq;
      // Update the current time 
      current_time += tq;
    }
    // If not, it means the burst time is equal to the time slice or less than from it. 
    else {
      // Update the current time 
      current_time += prcs[index].bt_remaining;
      // Mark the bt_remaining time as zero since the process at this time would be at the last iteration
      prcs[index].bt_remaining = 0;
      // Increment the completed counter so that the while loop will now have one less time to execute the loop. 
      completed++;
      // For the processes which have the bt_remaining as zero means they have completed their execution. Find the CT, TAT, WT and RT as per the formulas
      prcs[index].ct = current_time;
      prcs[index].tat = prcs[index].ct - prcs[index].at;
      prcs[index].wt = prcs[index].tat - prcs[index].bt;
      prcs[index].rt = prcs[index].start_time - prcs[index].at;
    }

    //check which Processes needs to be pushed to the Ready Queue from the Input list
    for (int i = 1; i < n; i++) {
      if (prcs[i].bt_remaining > 0 && prcs[i].at <= current_time && visited[i] == false) {
        q.push(i);
        visited[i] = true;
      }
    }
    //check if the Process on CPU needs to be pushed to Ready Queue
    if (prcs[index].bt_remaining > 0)
      q.push(index);

    //if the queue is empty, just add one process from list, whose remaining burst time > 0
    if (q.empty()) {
      for (int i = 1; i < n; i++) {
        if (prcs[i].bt_remaining > 0) {
          q.push(i);
          visited[i] = true;
          break;
        }
      }
    }
  } //end of while
  //sort so that process ID in output comes in Original order (just for interactivity- Not needed otherwise)  
  sort(prcs, prcs + n, comparatorPID);
  //Output
  cout << "\nPNo.\tAT\tBT\tST\tCT\tTAT\tWT\tRT\n";
  for (int i = 0; i < n; i++)
    cout << "P[" << i << "]" << "\t" << prcs[i].at << "\t" << prcs[i].bt << "\t" << prcs[i].start_time << "\t" << prcs[i].ct << "\t" << prcs[i].tat << "\t" << prcs[i].wt << "\t" << prcs[i].rt << endl;
  cout << endl;
  return 0;
}


Output 

Output

You can also read about layered structure of operating system.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions 

Differentiate Round Robin and FCFS scheduling algorithms. 

S.No Round Robin(RR) Scheduling FCFS scheduling
1. It is a preemptive scheduling algorithm.  It is a non-preemptive scheduling algorithm. 
2. RR is mainly designed for the time-sharing system.  FCFS is in-convenient for time-sharing systems. 
3. The execution is similar to the FCFS, but each process has a time quantum. The execution is based on the arrival time. 

 

What is the relation between FCFS and Round Robin scheduling algorithm?

Round Robin algorithm started behaving like FCFS if the time quantum is taken large. Since it works similarly as the FCFS differs only in the concept of the time slice, if the time slice is large, then the burst time of each process will be less; hence there will be less context switching that could lead to behaving like FCFS. 

Difference between the preemptive and non-preemptive algorithm. 

S.No Preemptive Algorithm  Non-preemptive Algorithm 
1. The CPU is allocated to the processes for a limited time.   The CPU is allocated to process till it either terminates or switches to another state. 
2. The process can be forcefully taken out of the CPU if any higher priority process needs to be executed.  The process cannot be taken out of the CPU forcefully. 
3. More context switching and CPU utilization.  Less context switching and CPU utilization.  

 

 

 

Conclusion

To wrap up the discussion, we’ve looked at the algorithm and Implementation part of the Round Robin Scheduling Algorithm. For better understanding, try dry running the Implementation while taking any other example. That would make your concepts clearer. Furthermore, if you like the article, do upvote it and share it with your friends.

Recommended Readings: 


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Learning :)

Guided path
Free
gridgp-icon
Operating system track
14 chapters
83+ Problems
gp-badge
Earn badges and level up
Live masterclass