 Round Robin Scheduling Algorithm with Examples and Programs!!

# Round Robin Scheduling Algorithm with Examples and Programs!!

Round Robin scheduling is a CPU scheduling algorithm that allocates equal time slices to each process in a circular order. It is designed to provide fairness and prevent starvation. Now, we are going to explain about Round Robin scheduling algorithm with its examples; involving with Round Robin scheduling program in C, C++, and Java with their output. This is unique article over the internet. So we make sure that at the end of this post; you will definitely fully educate about Round Robin Scheduling Algorithm without getting any hassle.

## Introduction to Round Robin Scheduling

Round Robin scheduling is a CPU scheduling algorithm that is commonly used in operating systems to allocate CPU time to processes. It is a pre-emptive algorithm that assigns time slices or quantum to each process in a circular manner, regardless of the process’s priority. The basic idea behind Round Robin scheduling is that each process is given a small unit of time, called a time slice, to execute. Once the time slice is over, the CPU is pre-empted, and the next process in the queue is given a time slice to execute. This process continues until all the processes have had a chance to execute. If a process finishes its execution before its time slice is over, it is removed from the queue.

Round Robin scheduling is a simple and fair scheduling algorithm that ensures that each process gets an equal share of the CPU time. It also provides a way to handle processes with varying levels of priority by simply giving higher priority processes more time slices. However, it may not be the most efficient scheduling algorithm, as it can result in a significant amount of overhead due to the frequent context switches that occur.

## ‘Round Robin Scheduling’ Tutorial Headlines:

1. Introduction to Round Robin Scheduling
2. How Does Round Robin Scheduling Algorithm Work?
3. Examples of Round Robin Scheduling with Arrival Time
4. Advantages of Round Robin Scheduling
5. Disadvantages of Round Robin Scheduling
6. Characteristics of Round Robin Scheduling
7. Worst Case Latency
8. Round Robin Scheduling Program in C with Gantt Chart
9. Round Robin Scheduling Program in C++
10. Round Robin Scheduling Program in Java
• What is the Round Robin CPU scheduling in OS?
• What is Round Robin concept?
• What is the time quantum in the Round Robin algorithm?
• How do you calculate the average waiting time in the Round Robin algorithm?
• Is the Round Robin algorithm preemptive or non-preemptive?
• Why is Round Robin scheduling pre-emptive?
• What is the time complexity of Round Robin scheduling?
• What is a Round-Robin scheduling real-life example?

## How Does Round Robin Scheduling Algorithm Work?

Round Robin algorithm is a pre-emptive algorithm that is designed to provide fair scheduling for processes or threads that are competing for CPU time. The algorithm works by allocating a fixed time slice or quantum to each process in a circular order, hence the name “Round Robin”.

### Also Read: First Come First Serve (FCFS) Scheduling Algorithm in OS with Examples & Programs!!

Here’s how it works in more detail:

1. The algorithm maintains a queue of processes that are ready to execute.
2. Each process is given a fixed time quantum to execute, usually in the range of 10-100 milliseconds.
3. The scheduler selects the first process from the queue and assigns it the CPU.
4. The process executes for the duration of its time quantum.
5. If the process completes before the end of its quantum, it is moved to the end of the queue and the next process in the queue is selected.
6. If the process does not complete within its quantum, it is pre-empted and moved to the end of the queue.
7. The scheduler then selects the next process from the queue and assigns it the CPU.

Steps 4-7 are repeated until all processes have completed execution.

The Round Robin algorithm is simple and easy to implement, and it ensures that each process gets a fair share of the CPU time. However, it may not be optimal for all scenarios, as it may result in some processes experiencing significant latency if their quantum is too short. Therefore, it is important to choose an appropriate quantum value that balances fairness and efficiency.

## Examples of Round Robin Scheduling with Arrival Time

Here, we will show you an example of Round Robin Scheduling with Arrival Time:

### Also Read: Process Life Cycle in Operating System | Process State in OS

Suppose we have 4 processes with the following characteristics:

Process   Arrival Time    Burst Time

P1                   0                          4

P2                   1                          3

P3                   2                          2

P4                   3                          1

Assume that the time quantum is 2.

At time t=0, all the processes are in the ready queue. We will execute each process for 2 units of time (the time quantum), in the order they arrived, until all processes are finished. Here’s how the scheduling would look:

Time      Execution          Process             Burst Time

0                  2                            P1                         2

2                  2                            P2                         1

3                  1                            P1                         0

4                  1                            P3                         1

5                  1                            P2                         0

6                  1                            P4                         0

7

At time 0, P1 is the only process in the ready queue, so it executes for 2 units of time. At time 2, P2 arrives and joins the queue. Since P1 has already executed for 2 units of time, we switch to P2 and execute it for 2 units of time. At time 3, we switch back to P1, which has 2 units of burst time remaining, but since its time quantum is exhausted, we switch to the next process in the queue, which is P3.

This process has 2 units of burst time remaining, but it only executes for 1 unit of time, since that is the remaining time quantum. At time 5, we switch back to P2, which only has 1 unit of burst time remaining, so it finishes executing. At time 6, we switch to P4, which only has 1 unit of burst time remaining, so it also finishes executing. Finally, at time 7, all processes have finished executing and the scheduling is complete.

## Advantages of Round Robin Scheduling

There are some advantages and benefits of Round Robin Scheduling include:

### Also Read: What is Process in OS? Types of Process in Operating System!!

Fairness: Round Robin scheduling ensures that every process gets a fair share of CPU time. This is because each process is allocated an equal time slice, and no process can monopolize the CPU for an extended period.

Good for Time-Sharing Systems: RR is especially useful in time-sharing systems, where multiple users share a single system. It ensures that each user gets a fair share of CPU time, and no user can monopolize the system resources.

Simple and Easy to Implement: Round Robin is a simple algorithm that is easy to implement. The time slice can be adjusted to suit the needs of the system and the processes.

Efficient: RR is an efficient algorithm that can provide fast response times for interactive processes. Since each process gets a small time slice, the turnaround time for processes is usually low, which means that processes complete quickly.

Preemptive: Round Robin is a pre-emptive scheduling algorithm, which means that a process can be interrupted if a higher-priority process arrives. This ensures that critical processes get priority and are executed in a timely manner.

Therefore, Round Robin scheduling is a simple, efficient, and fair scheduling algorithm that can be used in a variety of computing environments.

## Disadvantages of Round Robin Scheduling

Round Robin scheduling is the most eminent CPU algorithm that is going to use for scheduling tasks in operating systems, but it does have some drawbacks:

Poor Performance for Long-Running Tasks: Round Robin scheduling can be inefficient for long-running tasks because each task gets a fixed time slice to execute, and if a task requires more time than its assigned time slice, it will be pre-empted and placed at the back of the queue. This can result in poor performance and long wait times for long-running tasks.

Overhead: Round Robin scheduling requires a timer interrupt to switch between tasks, which can add overhead to the system. The frequency of the timer interrupts needs to be carefully chosen to balance the overhead with the responsiveness of the system.

Variability in Response Time: The response time of a task can vary depending on the number of tasks in the queue and their execution time. This can lead to unpredictable response times, which may not be suitable for real-time systems.

Bad Utilization of Resources: Round Robin scheduling may not be efficient in utilizing system resources if there are many short-lived tasks in the queue. This is because each task gets a fixed time slice, which may result in wasted CPU time if a task completes its work before its time slice expires.

Starvation: Round Robin scheduling may lead to starvation, where a low-priority task may not get a chance to execute if there are high-priority tasks in the queue. This can result in poor system performance and unpredictable behavior.

## Characteristics of Round Robin Scheduling

Here, some of the key characteristics of Round Robin scheduling in OS are:

• Round Robin scheduling is a time-sharing algorithm. The CPU time is divided into time slices or quanta, and each process is given a fixed time slice to execute. After the time slice expires, the process is pre-empted and moved to the end of the ready queue.
• RR scheduling comes in a preemptive scheduling algorithm. This means that the CPU can be taken away from a running process at any time, even before its time slice has expired, and given to a higher-priority process.
• This scheduling ensures fairness among all the processes by giving them an equal chance to use the CPU. Each process is given a time slice, and the process is moved to the end of the queue after the time slice expires. This prevents any single process from monopolizing the CPU.
• Round Robin scheduling has a relatively low overhead because it only requires a timer to keep track of the time slices.
• The response time for Round Robin scheduling is generally good for interactive systems because each process is given a time slice to execute, which allows for quick context switching.
• The throughput for Round Robin scheduling is generally lower compared to other scheduling algorithms because of the overhead associated with context switching.
• Context switching is the process of saving the state of the current process and loading the state of the next process in the ready queue. Round Robin scheduling requires frequent context switching, which can have a negative impact on the overall performance of the system.

## Worst Case Latency

The worst-case latency in round-robin scheduling refers to the maximum amount of time a task has to wait before being executed, given a specific set of tasks and their execution requirements.

Round-robin scheduling can affects worst-case latency by a variety of factors, including the length of the time slice, the number of tasks in the queue, and the execution requirements of each task. Generally speaking, the longer the time slice and the larger the number of tasks in the queue, the greater the worst-case latency.

In a scenario where there are n tasks in the queue and each task requires a time T to execute, the worst-case latency in round-robin scheduling can be calculated as follows:

Worst-case latency = (n-1) * T

This formula assumes that each task is scheduled in a strictly circular order and that no task is allowed to run for longer than its allocated time slice. Therefore, the worst-case latency occurs when a task has to wait for all other tasks in the queue to complete their execution before it gets a chance to execute, which happens when there are n-1 tasks in the queue.

In practice, the worst-case latency in round-robin scheduling can be reduced by adjusting the time slice to better match the execution requirements of the tasks and by optimizing the scheduling algorithm to minimize context switches and reduce overhead.

## Round Robin Scheduling Program in C with Gantt Chart

Here’s a sample C program that implements Round Robin scheduling algorithm with a Gantt chart to visualize the schedule:

#include <stdio.h>

#include <stdlib.h>

#define MAX_PROCESSES 10

#define TIME_QUANTUM 4

struct Process {

int pid;

int burst_time;

int remaining_time;

int arrival_time;

};

int main() {

struct Process processes[MAX_PROCESSES];

int num_processes, total_time = 0, time_elapsed = 0, done = 0, current_process = -1;

int time_chart[MAX_PROCESSES] = {0}; // Gantt chart

printf(“Enter the number of processes: “);

scanf(“%d”, &num_processes);

for (int i = 0; i < num_processes; i++) {

printf(“Enter arrival time and burst time for process %d: “, i+1);

scanf(“%d %d”, &processes[i].arrival_time, &processes[i].burst_time);

processes[i].remaining_time = processes[i].burst_time;

processes[i].pid = i+1;

total_time += processes[i].burst_time;

}

printf(“\nRound Robin Scheduling\n\n”);

printf(“Time Chart:\n”);

printf(“0”);

while (done != num_processes) {

current_process = (current_process + 1) % num_processes;

if (processes[current_process].remaining_time <= TIME_QUANTUM && processes[current_process].remaining_time > 0) {

time_elapsed += processes[current_process].remaining_time;

processes[current_process].remaining_time = 0;

done++;

} else if (processes[current_process].remaining_time > 0) {

time_elapsed += TIME_QUANTUM;

processes[current_process].remaining_time -= TIME_QUANTUM;

}

for (int i = 0; i < num_processes; i++) {

if (processes[i].arrival_time <= time_elapsed && processes[i].remaining_time > 0) {

time_chart[i][time_elapsed] = processes[i].pid;

}

}

}

printf(“\n”);

for (int i = 0; i < num_processes; i++) {

printf(“P%d\t”, processes[i].pid);

for (int j = 0; j <= total_time; j++) {

if (time_chart[i][j] == processes[i].pid) {

printf(“|”);

} else {

printf(” “);

}

}

printf(“\n”);

}

printf(“0”);

for (int i = 1; i <= total_time; i++) {

printf(“%2d”, i);

}

printf(“\n\n”);

return 0;

}

Here’s an example input/output for this program:

Enter the number of processes: 3

Enter arrival time and burst time for process 1: 0 7

Enter arrival time and burst time for process 2: 1 3

Enter arrival time and burst time for process 3: 2 4

Round Robin Scheduling

Time Chart:

0|1111111111222222222233333333334|4444

P1           |       ||||||||

P2             |   |||||

P3              |  |||||

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

In the Gantt chart, each process is represented by a vertical bar (|) that spans the time it runs

## Round Robin Scheduling Program in C++

Here, we will show you the example of a Round Robin scheduling program in C++:

#include<iostream>

using namespace std;

struct Process {

int pid;        // Process ID

int bt;         // Burst Time

int art;        // Arrival Time

int wt;         // Waiting Time

int tt;         // Turnaround Time

int remaining;  // Remaining Time

};

void roundRobin(Process processes[], int n, int quantum) {

int t = 0;                      // Current time

int completed = 0;              // Number of completed processes

int total_wt = 0, total_tt = 0; // Total waiting time and turnaround time

// Initialize remaining time of all processes

for (int i = 0; i < n; i++)

processes[i].remaining = processes[i].bt;

// Keep executing processes in round robin manner until all are done

while (completed != n) {

bool done = true;

// Traverse all processes one by one repeatedly

for (int i = 0; i < n; i++) {

// If process is not completed

if (processes[i].remaining > 0) {

done = false;

// Execute for quantum time or until completion

if (processes[i].remaining > quantum) {

t += quantum;

processes[i].remaining -= quantum;

}

else {

t += processes[i].remaining;

processes[i].wt = t – processes[i].bt – processes[i].art;

processes[i].remaining = 0;

completed++;

// Calculate turnaround time

processes[i].tt = t – processes[i].art;

// Add to total waiting time and turnaround time

total_wt += processes[i].wt;

total_tt += processes[i].tt;

}

}

}

// If all processes are done

if (done)

break;

}

// Calculate average waiting time and turnaround time

float avg_wt = (float)total_wt / n;

float avg_tt = (float)total_tt / n;

// Print results

cout << “Average Waiting Time: ” << avg_wt << endl;

cout << “Average Turnaround Time: ” << avg_tt << endl;

}

int main() {

int n, quantum;

cout << “Enter the number of processes: “;

cin >> n;

cout << “Enter the time quantum: “;

cin >> quantum;

Process processes[n];

for (int i = 0; i < n; i++) {

cout << “Enter process ” << i + 1 << ” arrival time: “;

cin >> processes[i].art;

cout << “Enter process ” << i + 1 << ” burst time: “;

cin >> processes[i].bt;

processes[i].pid = i + 1;

}

roundRobin(processes, n, quantum);

return 0;

}

This program takes in the number of processes, arrival time, and burst time for each process from the user. It then executes the Round Robin scheduling algorithm with the given time quantum and outputs the average waiting time and turnaround time for all processes.

## Round Robin Scheduling Program in Java

Sure, we can help you with that. Here’s an example of a Round Robin Scheduling Program in Java:

import java.util.Queue;

public class RoundRobinScheduling {

public static void main(String[] args) {

// initialize the queue with processes

// set the time quantum

int timeQuantum = 2;

// simulate the scheduling algorithm

int time = 0;

while (!queue.isEmpty()) {

Process p = queue.poll();

int burstTime = p.getBurstTime();

if (burstTime <= timeQuantum) {

// process completes within time quantum

time += burstTime;

System.out.println(p.getName() + ” completes at time ” + time);

} else {

// process still needs more time

time += timeQuantum;

burstTime -= timeQuantum;

System.out.println(p.getName() + ” gets ” + timeQuantum + “ms, remaining burst time = ” + burstTime);

}

}

}

}

class Process {

private String name;

private int burstTime;

public Process(String name, int burstTime) {

this.name = name;

this.burstTime = burstTime;

}

public String getName() {

return name;

}

public int getBurstTime() {

return burstTime;

}

}

In this example, we have a Process class that represents a process in the system. It has a name and a burst time (the amount of time required to execute the process). We also have a RoundRobinScheduling class that simulates the scheduling algorithm.

The queue represents the ready queue of processes. We initialize it with some processes, but in a real system, processes would be added to the queue dynamically.

We set the time quantum to 2 milliseconds in this example, but this value can be adjusted as needed.

We simulate the scheduling algorithm by repeatedly taking the next process from the queue and executing it for the time quantum. If the process completes within the time quantum, we print a message indicating that it has completed. If the process still needs more time, we reduce its burst time by the time quantum and add it back to the queue.

### What is the Round Robin CPU scheduling in OS?

The Round Robin algorithm is a scheduling algorithm used by operating systems to allocate CPU time to processes. In this algorithm, each process is given a fixed time quantum or time slice, and the CPU switches between processes after the time quantum expires.

### What is Round Robin concept?

The round robin concept is a scheduling algorithm that is commonly used in computer science and operating systems. It is a simple and fair way to allocate resources, such as CPU time or access to a shared resource, among multiple processes or tasks.

So, round robin concept ensures that all processes are treated fairly and that no process is starved of resources for too long. It also provides a good balance between responsiveness and throughput, as each process gets a chance to execute fairly frequently.

### What is the time quantum in the Round Robin algorithm?

The time quantum in the Round Robin algorithm is the amount of time that a process is allowed to run on the CPU before being pre-empted and moved to the end of the ready queue. The time quantum is typically set to a fixed value, such as 10-100 milliseconds, depending on the system’s requirements.

### How do you calculate the average waiting time in the Round Robin algorithm?

The average waiting time in the Round Robin algorithm can be calculated by adding up the waiting times of all processes and dividing the total by the number of processes. The waiting time of a process is the time it spends in the ready queue before being assigned the CPU.

### Is the Round Robin algorithm preemptive or non-preemptive?

The Round Robin algorithm is a preemptive scheduling algorithm because it allows the CPU scheduler to interrupt a process and switch to another process after a time quantum expires. This feature ensures that all processes get an equal share of CPU time and prevents a single process from hogging the CPU.

### Why is Round Robin scheduling pre-emptive?

Round-robin scheduling is a pre-emptive scheduling algorithm because it allows the operating system to interrupt a currently executing process at a fixed time interval (known as the time quantum) and switch to the next process in the queue.

### What is the time complexity of Round Robin scheduling?

The time complexity of round-robin scheduling is O(n), where n is the number of processes. This is because the algorithm processes each process in a circular order, and it has to process each process at least once.

### What is a Round-Robin scheduling real-life example?

A real-life example of round-robin scheduling is a tennis tournament. In a tennis tournament, there are many players who need to play against each other. To schedule the matches, a round-robin algorithm can be used. Each player is assigned a fixed time slot during which they play a match against another player. The players play against each other in a circular order, and each player gets an equal opportunity to play against every other player in the tournament.

## Wrapping Up

`Happy Learning!!`