 New update is available. Click here to update.

# Round Robin CPU Scheduling Algorithm

## Introduction

You open your system in the morning; you open your mailbox, text someone on chat, and join your meetings; and have you ever wondered that all this happens simultaneously, within seconds? Let’s examine how the algorithm works. The name of the Round Robin Scheduling algorithm comes from the old principle of round-robin, where the algorithm is designed to get an 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.

Recommended Topic, FCFS 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, 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 following process after a fixed interval, called time quantum/time slice.
• It is a real-time algorithm responding 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, 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;

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

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

### 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 CodeStudio. If you liked this blog, share it with your friends. 