What is Round-robin scheduling algorithm?

Operating Systems use various scheduling algorithms to schedule the execution of different processes on the CPU. The following are some scheduling algorithms:

First Come First Serve (FCFS) scheduling
Shortest job next (SJN) scheduling
Priority scheduling
Shortest remaining time
Round Robin (RR) scheduling
Multiple-level queues scheduling

Note: Algorithms are either preemptivePreemptive scheduling is based on priority where a scheduler may preempt a low priority running process anytime when a high priority process enters into a ready state. or non-preemptiveNon-preemptive algorithms are designed so that once a process enters the running state, it cannot be preempted until it completes its allotted time..

In this answer, we'll discuss the RR scheduling algorithm.

Methodology

In Round Robin scheduling, every process is assigned a time quantum to use CPU resources for its execution in a cyclic way. If we modify the FCFS algorithm to make it preemptive, it will work like Round Robin scheduling.

This scheduling algorithm focus on the time-sharing technique for the utilization of CPU resources and that unit of time is called time quantumThe period of time for which a process or job is allowed to run in a pre-emptive method is called time quantum. .

Every process in the ready queueThe ready queue is a queue of all processes that are waiting to be scheduled on a core/CPU. gets CPU for that time quantum, and if the process completes its execution in the fixed time quantum, then the process will be removed from the queue; otherwise, the process will go back to the waiting queue and wait for its turn to complete the execution.

Example

Suppose we have a set of three processes whose burst timeBurst time is the total time taken by the process for its execution on the CPU. is given with time quantum $2$ , schedule the processes using round-robin scheduling, and calculate the average waiting time.

// C++ program for Round-Robin scheduling
#include<iostream>
using namespace std;
// Function to find the waiting time 
void findWaitingTime(int processes[], int size,
			int bursttime[], int waittime[], int quantum)
{
	
	int rem_bt[size]; // To store remaining burst times
	int i = 0;
	while(i < size)
	{
		rem_bt[i] = bursttime[i];
		i++;
	}
	int t = 0; // Current time
	// Keep traversing processes in round robin manner untill complete execution
	
	while (1)
	{
		bool done = true;
		int i = 0; 
		// Traverse all processes in a cycle
		while( i < size)
		{
			// Only execute a process with burst time > 0
			if (rem_bt[i] > 0)
			{
				done = false; // A pending process
				if (rem_bt[i] > quantum)
				{
					//Process execution so far
					t += quantum;
					// Decrement burst time of process with respect to quantum
					rem_bt[i] -= quantum;
				}
				// Last cycle for this process
				else
				{
					//Process execution for unit time
					t = t + rem_bt[i];
					//Wait time formula
					waittime[i] = t - bursttime[i];
					//After complete execution of process make it burst time 0
					rem_bt[i] = 0;
				}
			}
			i++;
		}
		// If all processes are done
		if (done == true)
		break;
	}
}
// Function to calculate average time
void findavgTime(int processes[], int size, int bursttime[],
									int quantum)
{
	int waittime[size], total_wt = 0;
	// Function to find waiting time
	findWaitingTime(processes, size, bursttime, waittime, quantum);
	// Display processes details
	cout << "ProcessNo   "<< "BurstTime"
		<< "  WaitTime";
	// Calculate total waiting time 
	int i = 0;
    cout <<endl;
	while(i<size)
	{
		total_wt = total_wt + waittime[i];
		
		cout << " " << i+1 << "\t\t" << bursttime[i] <<"\t "
			<< waittime[i] <<"\t\t "<<endl;
		
		i++;
	}
	cout << "Average waiting time = "
		<< (float)total_wt / (float)size;
	
}
// 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[] = {4, 3, 5};
	// Time quantum
	int quantum = 2;
	findavgTime(processes, n, burst_time, quantum);
	return 0;
}

Advantages

The advantages of the RR algorithm are as follows:

All process in the queue gets an equal share of CPU resources, unlike FCFS.
Since round-robin uses time-sharing, it gives each process a time slot.
Every process gets a chance to re-use the CPU after a fixed time quantum.
It's easy to implement and is also Starvation is the problem that occurs when low priority processes get jammed for an unspecified time as the high priority processes keep executing. a starvationStarvation is the problem that occurs when low priority processes get jammed for an unspecified time as the high priority processes keep executing.-free algorithm.

Disadvantages

The disadvantages of the RR algorithm are as follows:

The waiting time and response time are relatively more extensive.
The throughputThroughput is a measure of how many units of information a system can process in a given amount of time. is low.
There is an overhead of context switching.
If quantum time is less for scheduling, it gives too big a Gantt chart.

Free AI Mock Interviews

Coding Interview

Coding PatternsFree Interview

Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.

System Design

You TubeFree Interview

Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources

Process Queue	Burst Time
P1	4
P2	3
P3	5

What is Round-robin scheduling algorithm?

Methodology

Example

Solution

Gantt chart

Waiting time

Average waiting time

Code example

Advantages

Disadvantages