# 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:

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

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;

// 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)

• 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.

• 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.

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.