Round Robin CPU Scheduling Algorithm

Round Robin CPU Scheduling Algorithm
Round Robin CPU Scheduling Algorithm

Introduction

You open your system in the morning, you open your mailbox, text someone on chat, join your meetings, and have you ever wondered that all this happens at the same time, within some seconds. Let’s examine how the algorithm works. The name of Round Robin Scheduling algorithm comes from the old principle round robin, where the algorithm is designed to get the equal share, maybe time or memory.

This algorithm also offers starvation free execution of processes. Let’s explore the characteristics of a round robin scheduling algorithm.

Characteristics of Round Robin Scheduling Algorithm

  • Round robin is a preemptive algorithm.
  • Widely used scheduling method in traditional OS.
  • Time slice should be minimum, which is assigned for a specific task that needs to be processed. However, it may differ from OS to OS.
  • The process that is preempted is added to the end of the queue.
  • The CPU is shifted to the next process after fixed interval time, which is called time quantum/time slice.
  • It is a real time algorithm which responds to the event within a specific time limit.
  • Round robin is a hybrid model which is clock-driven.
  • Round robin is one of the oldest, fairest, and easiest algorithms.

Let’s examine the examples and implementation of the round robin scheduling algorithm.

Implementation:

ProcessBurst TimeOrderArrival Time
P1310
P2420
P3330

Suppose the time quantum is 1 unit.

Order of execution of processes in CPU:

P1P2P3P1P2P3P1P2P3P2

0                10

P1 waiting Time: 4 The average waiting time(AWT): (4+6+6)/3 = 5.33

P2 waiting Time: 6

P3 waiting Time: 6 

During the process scheduling first P1 enters into the ready queue and is then followed by P2, P3, once a process is executed for a given time period i.e time slice/quantum, it is preempted and other processes in the ready queue execute for the same period of time and this cyclic execution of processes continue until every process completes its burst time/cpu time.

blog banner 1

First P1 gets the CPU for a time slice of 1 unit and then moves back to the ready queue, followed by P2 and P3 in a similar manner. The processes execute until they have completed their burst/cpu times.

To implement a round-robin scheduling algorithm, first, we need to understand the completion time, turnaround time, and waiting time.

Completion Time: The time at which the process completes the execution.

Turnaround Time: The time difference between completion and arrival time.

Turnaround time= Completion time- Arrival time

Waiting Time: The time difference between turnaround time and burst time.

Waiting Time= Turnaround time- Burst time

Note: In most cases, we assume arrival time as zero (Same in Blog).

Let’s find the steps to find waiting times for all responses.

1- Create an array rem_bt[] to keep track of remaining
   burst time of processes. This array is initially a 
   copy of bt[] (burst times array)
2- Create another array wt[] to store waiting times
   of processes. Initialize this array as 0.
3- Initialize time : t = 0
4- Keep traversing the all processes while all processes
   are not done. Do following for i'th process if it is
   not done yet.
    a- If rem_bt[i] > quantum
       (i)  t = t + quantum
       (ii) bt_rem[i] -= quantum;
    c- Else // Last cycle for this process
       (i)  t = t + bt_rem[i];
       (ii) wt[i] = t - bt[i]
       (ii) bt_rem[i] = 0; // This process is over

After finding the waiting time, it is very simple to find the turnaround time.

Turnaround time= Waiting time+Burst time

Now let’s explore the code to understand it in more detail.

C++ Code

// C++ program for implementation of RR scheduling
#include<iostream>
using namespace std;
  

void findWaitingTime(int processes[], int n,
             int bt[], int wt[], int quantum)
{
        // burst times.
    int m_bt[n];
    for (int i = 0 ; i < n ; i++)
        m_bt[i] =  bt[i];
  
    int t = 0; // Current time
  
    // Keep traversing processes in round-robin manner
    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 (m_bt[i] > 0)
            {
                done = false; // There is a pending process
  
                if (m_bt[i] > quantum)
                {
                    t += quantum;
                    m_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                   
                     t = t + m_bt[i];
  
                    // Waiting time is current time minus time
                    wt[i] = t - bt[i];
  
                    // As the process gets fully executed
                    // make its remaining burst time = 0
                    m_bt[i] = 0;
                }
            }
        }
  
        // If all processes are done
        if (done == true)
          break;
    }
}
  
// Function to calculate turnaround 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 turnaround time for all processes
    findTurnAroundTime(processes, n, bt, wt, tat);
  
    // Display processes along with all details
    cout << "Processes "<< " Burst time "
         << " Waiting time " << " Turnaround 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 turnaround 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:

Processes  Burst time  Waiting time  Turnaround time
 1              10       13              23
 2              5        10              15
 3              8        13              21
Average waiting time = 12
Average turnaround time = 19.6667

Time Complexity: O(n)

Space Complexity: O(n)

Java Code

// Java program for implementation of RR scheduling
  
public class Main
{
    // Method to find the waiting time for all
    // processes
    static 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[] = new int[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(true)
        {
            boolean 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;
        }
    }
       
    // Method to calculate turnaround time
    static 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];
    }
       
    // Method to calculate average time
    static void findavgTime(int processes[], int n, int bt[],
                                         int quantum)
    {
        int wt[] = new int[n], tat[] = new int[n];
        int total_wt = 0, total_tat = 0;
       
        // Function to find waiting time of all processes
        findWaitingTime(processes, n, bt, wt, quantum);
       
        // Function to find turnaround time for all processes
        findTurnAroundTime(processes, n, bt, wt, tat);
       
        // Display processes along with all details
        System.out.println("Processes " + " Burst time +
                      " Waiting time " + " Turnaround time");
       
        // 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];
            System.out.println(" " + (i+1) + "\t\t" + bt[i] +"\t " +
                              wt[i] +"\t\t " + tat[i]);
        }
       
        System.out.println("Average waiting time = " +
                          (float)total_wt / (float)n);
        System.out.println("Average turnaround time = " +
                           (float)total_tat / (float)n);
    }
      
    // Driver Method
    public static void main(String[] args)
    {
        // process id's
        int processes[] = { 1, 2, 3};
        int n = processes.length;
       
        // Burst time of all processes
        int burst_time[] = {10, 5, 8};
       
        // Time quantum
        int quantum = 2;
        findavgTime(processes, n, burst_time, quantum);
    }
}

Output:

Processes  Burst time  Waiting time  Turnaround time
 1              10       13              23
 2              5        10              15
 3              8        13              21
Average waiting time = 12.0
Average turnaround time = 19.666666

Time Complexity: O(n)

Space Complexity: O(n)

Advantages

  • It doesn’t face the issues of starvation or convoy effect.
  • If you know the total number of processes on the run queue, then you can also assume the worst-case response time for the same process.
  • All the jobs get a fair allocation of CPU.
  • It deals with all processes without any priority.
  • Allows OS to use the Context switching method to save states of preempted processes.
  • This scheduling method does not depend upon burst time. That’s why it is easily implementable on the system.
  • Once a process is executed for a specific set of the period, the process is preempted, and another process executes for that given time period.
  • It gives the best performance in terms of average response time.

Disadvantages

  • Round-robin scheduling doesn’t give special priority to more important tasks.
  • Decreases comprehension
  • Lower quantum results in higher context switching overhead in the system.
  • Finding a correct time quantum is a quite difficult task in this system.
  • If the slicing time of the OS is low, the processor output will be reduced.
  • This method spends more time on context switching
  • Its performance heavily depends on the time quantum.
  • Priorities cannot be set for the processes.

Frequently Asked Questions

What is a round robin scheduling real life example?

The real life example of a round robin scheduling algorithm is multitasking.

How is round robin scheduling calculated?

In Round Robin Scheduling, CPU is assigned to the process on the basis of FCFS for a fixed amount of time. This fixed amount of time is called a time quantum or time slice. After the time quantum expires, the running process is preempted and sent to the ready queue.

What is a round robin?

Round-robin is one of the algorithms employed by process and network schedulers in computing.

What is a round robin strategy?

Round-robin scheduling allocates each task an equal share of the CPU time. In its simplest form, tasks are in a circular queue and when a task’s allocated CPU time expires, the task is put to the end of the queue and the new task is taken from the front of the queue.

Key Takeaways

In the above blog we have discussed:

  • The name of this algorithm comes from the round-robin principle, where each person gets an equal share of something in turns.
  • Round robin is one of the oldest, fairest, and easiest algorithms and widely used scheduling methods in traditional OS.
  • Round robin is a preemptive algorithm
  • The biggest advantage of the round-robin scheduling method is that If you know the total number of processes on the run queue, then you can also assume the worst-case response time for the same process.
  • This method spends more time on context switching.

Read more about search algorithms here, Don’t forget to practice similar problems on CodeStudio as well. If you liked this blog, share it with your friends.