Round Robin CPU Scheduling Algorithm

Implementation:

Suppose the time quantum is 1 unit.

Order of execution of processes in CPU:

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, the first P1 enters into the ready queue and is followed by P2 and P3; once a process is executed for a given period i.e, time slice/quantum, it is preempted and other processes in the ready queue execute for the same period. This cyclic execution of processes continues until every process completes its burst time/CPU time.

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. The processes execute until they have completed their burst/CPU times.

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

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 effortless 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;
}

You can also try this code with Online C++ Compiler

Run Code

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

You can also try this code with Online C++ Compiler

Run Code

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);
    }
}

You can also try this code with Online Java Compiler

Run Code

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

You can also try this code with Online Java Compiler

Run Code

Time Complexity: O(n)

Space Complexity: O(n)

Click here for Fibonacci Series in Python, Open Source Operating System.

Advantages

• It doesn’t face the issues of starvation or convoy effect.
• If you know the total number of processes on the run queue, 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 period, the process is preempted, and another process executes for that given period.
• It gives the best performance in terms of average response time.

Disadvantages

• Round-robin scheduling doesn’t give special priority to more critical tasks.
• Decreases comprehension
• Lower quantum results in higher context switching overhead in the system.
• Finding a correct time quantum is a pretty challenging 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.

You can also read about layered structure of operating system.

Must Read: FCFS Scheduling

Frequently Asked Questions

What is a round-robin scheduling real-life example?

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

How is round-robin scheduling calculated?

In Round Robin Scheduling, the CPU is assigned to the process based on 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.

Conclusion

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 most significant advantage of the round-robin scheduling method is that If you know the total number of processes on the run queue, you can also assume the worst-case response time for the same process.
• This method spends more time on context switching.

Don’t forget to practice similar problems on Coding Ninjas Studio. If you liked this blog, share it with your friends.