Working of Round Robin Scheduling Algorithm
Let's understand the workings of the Round-Robin scheduling algorithm with an example.
Consider a scenario with three processes: P1, P2, and P3, each requiring different CPU burst times. Let the time quantum be 4 units.
1. Initially, all processes are placed in the circular queue: [P1, P2, P3].
2. The CPU scheduler starts with process P1 and allocates the CPU to it for 4 units of time. P1 executes for 4 units and is then preempted.
3. P1 is placed at the end of the queue: [P2, P3, P1].
4. The CPU is now allocated to process P2 for 4 units of time. P2 completes its execution within this time and releases the CPU.
5. The queue now contains: [P3, P1].
6. Process P3 gets the CPU for 4 units of time, executes, and is preempted.
7. P3 is placed at the end of the queue: [P1, P3].
8. P1 gets the CPU again for the remaining part of its execution, and so on.
This process continues until all processes complete their execution. The time quantum is a crucial factor in determining the performance of the Round Robin algorithm. A smaller time quantum results in more frequent context switches, which can lead to a higher system load. On the other hand, a larger time quantum may cause processes to wait longer for their turn, increasing response times.
Characteristics of Round Robin CPU Scheduling Algorithm
The Round Robin CPU scheduling algorithm has many main characteristics that define its behavior and performance:
1. Fairness: Round Robin ensures fair allocation of CPU time among processes. Each process gets an equal share of the CPU, preventing any single process from monopolizing the resources. This fairness is achieved through the cyclic allocation of time quanta.
2. Preemption: Round Robin is a preemptive scheduling algorithm. Processes are preempted if they do not complete within their allocated time quantum. This preemption allows other processes to get a chance to execute, promoting responsiveness & preventing starvation.
3. Time Quantum: The time quantum is a critical parameter in Round Robin scheduling. It determines the duration for which a process can execute before being preempted. The choice of time quantum influences the performance of the algorithm. A smaller time quantum leads to more frequent context switches, while a larger time quantum may cause longer waiting times for processes.
4. Context Switching: Round Robin involves frequent context switches as the CPU is switched among processes. Context switching allows the state of a preempted process to be saved and later restored when it is allocated the CPU again. However, context switches introduce overhead and can impact system performance if they occur too frequently.
5. Responsiveness: Round Robin provides good responsiveness, especially for interactive systems. By allocating time quanta to processes in a cyclic manner, it ensures that each process gets a chance to execute within a reasonable time frame. This responsiveness is important for user-facing applications.
6. No Priority: Round Robin does not consider process priorities. All processes are treated equally, regardless of their importance or urgency. This lack of priority distinction can be a limitation in systems where certain processes require higher priority or faster execution.
Advantages of Round Robin CPU Scheduling Algorithm
1. Fairness: One of the primary advantages of Round Robin is its fairness. It ensures that each process gets an equal share of CPU time, preventing any process from monopolizing the resources. This fair allocation of CPU time is particularly important in time-sharing systems where multiple users or processes are competing for CPU access.
2. Responsiveness: Round-robin scheduling provides good responsiveness, especially for interactive systems. By allocating time quanta to processes in a cyclic manner, it ensures that each process gets a chance to execute within a reasonable time frame. This responsiveness is crucial for user-facing applications where quick response times are expected.
3. Simplicity: The Round Robin algorithm is relatively simple to implement and understand. It does not require complex calculations or priority assignments. The simplicity of the algorithm makes it easy to implement in operating systems and reduces the overhead associated with scheduling decisions.
4. Avoids starvation: Round-robin scheduling prevents starvation, which occurs when a process is indefinitely denied access to the CPU. Since each process gets a fixed time quantum and is placed at the end of the queue after execution, no process is left waiting indefinitely. This ensures that all processes eventually get a chance to execute.
5. Suitable for time-sharing systems: Round Robin is well-suited for time-sharing systems where multiple users or processes share the CPU. It allows each user or process to get a fair share of CPU time, ensuring that no single entity dominates the system. This makes Round Robin scheduling a good choice for multi-user environments.
Disadvantages of Round Robin CPU Scheduling Algorithm
1. Context switching overhead: Round Robin involves frequent context switches as the CPU is switched among processes. Each context switch requires saving the state of the current process and loading the state of the next process, which introduces overhead. If the time quantum is too small, the overhead of context switching can become significant, leading to reduced system performance.
2. Poor performance for processes with varying CPU burst times: Round Robin treats all processes equally, regardless of their CPU burst times. If a process requires a longer CPU burst time than the time quantum, it will be preempted multiple times, leading to increased waiting time and reduced performance. This can be particularly problematic for CPU-bound processes that require longer uninterrupted execution times.
3. No priority consideration: Round Robin does not take process priorities into account. All processes are treated equally, regardless of their importance or urgency. This lack of priority consideration can be a limitation in systems where certain processes have higher priority or real-time requirements. Round Robin may not be suitable for systems with strict priority-based scheduling needs.
4. Determining the optimal time quantum: Choosing the right time quantum is crucial for the performance of Round Robin scheduling. If the time quantum is too small, the overhead of context switching increases, and the system spends more time in context switches than in actual execution. On the other hand, if the time quantum is too large, processes may experience longer waiting times, and the responsiveness of the system may suffer. Finding the optimal time quantum requires careful consideration and tuning based on the specific system requirements.
5. Not suitable for real-time systems: Round Robin scheduling may not be suitable for real-time systems that have strict timing constraints. In real-time systems, processes often have deadlines that must be met, and the scheduling algorithm must ensure that these deadlines are satisfied. Round Robin's equal treatment of processes and lack of priority consideration may not guarantee the timely execution of critical tasks in real-time environments.
Examples to show working of Round Robin Scheduling Algorithm
Let's understand the working of Round Robin scheduling with an example.
Consider the following set of processes with their arrival times & CPU burst times:
Process | Arrival Time | Burst Time
P1 | 0 | 5
P2 | 1 | 3
P3 | 2 | 8
P4 | 3 | 6
Assume the time quantum is 2 units.
Gantt Chart:
| P1 | P2 | P3 | P4 | P1 | P3 | P4 | P3 | P4 |
0 2 4 6 8 10 12 14 16 18
Explanation:
1. At time 0, process P1 arrives & starts executing for 2 units.
2. At time 1, process P2 arrives & is added to the ready queue.
3. At time 2, P1 is preempted, & P2 starts executing for 2 units.
4. At time 3, process P4 arrives & is added to the ready queue.
5. At time 4, P2 completes execution, & P3 starts executing for 2 units.
6. At time 6, P3 is preempted, & P4 starts executing for 2 units.
7. At time 8, P4 is preempted, & P1 resumes execution for the remaining 1 unit.
8. At time 10, P3 resumes execution for 2 units.
9. At time 12, P3 is preempted, & P4 resumes execution for 2 units.
10. At time 14, P4 is preempted, & P3 resumes execution for the remaining 2 units.
11. At time 16, P3 completes execution, & P4 resumes execution for the remaining 2 units.
12. At time 18, P4 completes execution, & all processes have finished.
The average waiting time for this example can be calculated as follows:
- P1 waits for 5 units (from time 2 to time 8, except for its own execution)
- P2 waits for 1 unit (from time 2 to time 4, except for its own execution)
- P3 waits for 7 units (from time 4 to time 16, except for its own execution)
- P4 waits for 7 units (from time 6 to time 18, except for its own execution)
Average waiting time = (5 + 1 + 7 + 7) / 4 = 5 units
How do you compute the below times in Round Robin using a program?
To compute various times in Round Robin scheduling using a program, we need to consider the following:
1. Completion Time (CT): The time at which a process completes its execution.
2. Turnaround Time (TAT): The total time taken by a process from its arrival until its completion.
TAT = CT - AT, where AT is the arrival time of the process.
3. Waiting Time (WT): The total time a process spends waiting in the ready queue.
WT = TAT - BT, where BT is the burst time of the process.
4. Response Time (RT): The time interval between the process arrival and its first response (i.e., when it first gets the CPU).
To calculate these times, we need to track the current time, each process's remaining burst time, and the time a process starts executing for the first time.
Let’s look at a step-by-step approach to compute these times:
1. Initialize variables to track current time, completion time, and waiting time for each process.
2. Create a queue to store the processes in the order they arrive.
3. While there are processes in the queue or any process is still executing:
- If a process is currently executing and its remaining burst time is greater than the time quantum:
- Decrement its remaining burst time by the time quantum.
- Increment the current time by the time quantum.
- If a process is currently executing and its remaining burst time is less than or equal to the time quantum:
- Increment the current time by the remaining burst time.
- Set the completion time of the process to the current time.
- Calculate the turnaround time and waiting time for the process.
- Remove the process from the queue.
- If no process is currently executing.
- Dequeue the next process from the queue.
- If the process is executing for the first time, set its response time to the current time.
- If a new process arrives, enqueue it into the queue.
4. Calculate the average waiting time and average turnaround time by summing up the individual times and dividing by the number of processes.
Program for Round Robin Scheduling with arrival time as 0 for all processes
Let’s take a sample program in C that shows the Round Robin scheduling algorithm when the arrival time for all processes is 0:
#include <stdio.h>
struct Process {
int burstTime;
int remainingTime;
};
void roundRobin(struct Process processes[], int n, int quantum) {
int completedProcesses = 0;
int currentTime = 0;
int waitingTime[n], turnaroundTime[n];
float avgWaitingTime = 0, avgTurnaroundTime = 0;
while (completedProcesses < n) {
for (int i = 0; i < n; i++) {
if (processes[i].remainingTime > 0) {
if (processes[i].remainingTime > quantum) {
currentTime += quantum;
processes[i].remainingTime -= quantum;
} else {
currentTime += processes[i].remainingTime;
waitingTime[i] = currentTime - processes[i].burstTime;
turnaroundTime[i] = currentTime;
processes[i].remainingTime = 0;
completedProcesses++;
}
}
}
}
for (int i = 0; i < n; i++) {
avgWaitingTime += waitingTime[i];
avgTurnaroundTime += turnaroundTime[i];
}
avgWaitingTime /= n;
avgTurnaroundTime /= n;
printf("Average Waiting Time: %.2f\n", avgWaitingTime);
printf("Average Turnaround Time: %.2f\n", avgTurnaroundTime);
}
int main() {
struct Process processes[] = {{5, 5}, {3, 3}, {8, 8}, {6, 6}};
int n = sizeof(processes) / sizeof(processes[0]);
int quantum = 2;
roundRobin(processes, n, quantum);
return 0;
}
You can also try this code with Online C Compiler
In this program:
1. The `Process` structure represents a process with its burst time & remaining time.
2. The `roundRobin` function implements the Round Robin scheduling algorithm.
3. The function iterates until all processes are completed.
4. In each iteration, it checks each process & executes it for the time quantum or until its remaining time becomes zero.
5. The waiting time & turnaround time for each process are calculated.
6. Finally, the average waiting time & average turnaround time are calculated & printed.
Output:
Average Waiting Time: 5.00
Average Turnaround Time: 10.50
Program for Round Robin Scheduling with arrival time as zero, different and same arrival times:
In this section, we will modify the previous program to handle different scenarios of arrival times.
1. Arrival time as zero for all processes:
This is the same scenario as the previous program, where all processes arrive at time 0. The program remains unchanged for this case.
2. Different arrival times for processes:
To handle different arrival times, we need to make some modifications to the program.
Here's the updated code:
#include <stdio.h>
struct Process {
int burstTime;
int remainingTime;
int arrivalTime;
};
void roundRobin(struct Process processes[], int n, int quantum) {
int completedProcesses = 0;
int currentTime = 0;
int waitingTime[n], turnaroundTime[n], responseTime[n];
float avgWaitingTime = 0, avgTurnaroundTime = 0, avgResponseTime = 0;
int isCompleted[n];
for (int i = 0; i < n; i++)
isCompleted[i] = 0;
while (completedProcesses < n) {
for (int i = 0; i < n; i++) {
if (processes[i].arrivalTime <= currentTime && !isCompleted[i]) {
if (processes[i].remainingTime > quantum) {
currentTime += quantum;
processes[i].remainingTime -= quantum;
} else {
currentTime += processes[i].remainingTime;
processes[i].remainingTime = 0;
isCompleted[i] = 1;
completedProcesses++;
waitingTime[i] = currentTime - processes[i].burstTime - processes[i].arrivalTime;
turnaroundTime[i] = currentTime - processes[i].arrivalTime;
responseTime[i] = waitingTime[i];
}
}
}
currentTime++;
}
for (int i = 0; i < n; i++) {
avgWaitingTime += waitingTime[i];
avgTurnaroundTime += turnaroundTime[i];
avgResponseTime += responseTime[i];
}
avgWaitingTime /= n;
avgTurnaroundTime /= n;
avgResponseTime /= n;
printf("Average Waiting Time: %.2f\n", avgWaitingTime);
printf("Average Turnaround Time: %.2f\n", avgTurnaroundTime);
printf("Average Response Time: %.2f\n", avgResponseTime);
}
int main() {
struct Process processes[] = {{5, 5, 0}, {3, 3, 1}, {8, 8, 2}, {6, 6, 3}};
int n = sizeof(processes) / sizeof(processes[0]);
int quantum = 2;
roundRobin(processes, n, quantum);
return 0;
}
You can also try this code with Online C Compiler
In this modified program:
1. The `Process` structure now includes an `arrivalTime` field to represent the arrival time of each process.
2. An `isCompleted` array is introduced to keep track of completed processes.
3. The program iterates until all processes are completed, considering their arrival times.
4. A process is only executed if its arrival time is less than or equal to the current time.
5. The response time for each process is calculated as the difference between the time it starts executing and its arrival time.
Output:
Average Waiting Time: 5.00
Average Turnaround Time: 10.50
Average Response Time: 2.00
Program for Round Robin Scheduling with Different Arrival Times for all Processes
To handle different arrival times for all processes in Round Robin scheduling, we need to make further modifications to the program. Let’s look at the latest updated code:
#include <stdio.h>
#include <stdbool.h>
struct Process {
int pid;
int burstTime;
int arrivalTime;
int remainingTime;
};
void roundRobin(struct Process processes[], int n, int quantum) {
int currentTime = 0;
int completedProcesses = 0;
int waitingTime[n], turnaroundTime[n], responseTime[n];
float avgWaitingTime = 0, avgTurnaroundTime = 0, avgResponseTime = 0;
bool isCompleted[n];
for (int i = 0; i < n; i++)
isCompleted[i] = false;
while (completedProcesses < n) {
bool allCompleted = true;
for (int i = 0; i < n; i++) {
if (processes[i].arrivalTime <= currentTime && !isCompleted[i]) {
allCompleted = false;
if (processes[i].remainingTime <= quantum) {
currentTime += processes[i].remainingTime;
processes[i].remainingTime = 0;
isCompleted[i] = true;
completedProcesses++;
waitingTime[i] = currentTime - processes[i].burstTime - processes[i].arrivalTime;
turnaroundTime[i] = currentTime - processes[i].arrivalTime;
responseTime[i] = waitingTime[i];
} else {
currentTime += quantum;
processes[i].remainingTime -= quantum;
}
}
}
if (allCompleted)
currentTime++;
}
for (int i = 0; i < n; i++) {
avgWaitingTime += waitingTime[i];
avgTurnaroundTime += turnaroundTime[i];
avgResponseTime += responseTime[i];
}
avgWaitingTime /= n;
avgTurnaroundTime /= n;
avgResponseTime /= n;
printf("Average Waiting Time: %.2f\n", avgWaitingTime);
printf("Average Turnaround Time: %.2f\n", avgTurnaroundTime);
printf("Average Response Time: %.2f\n", avgResponseTime);
}
int main() {
struct Process processes[] = {{1, 5, 0, 5}, {2, 3, 1, 3}, {3, 8, 3, 8}, {4, 6, 5, 6}};
int n = sizeof(processes) / sizeof(processes[0]);
int quantum = 2;
roundRobin(processes, n, quantum);
return 0;
}
You can also try this code with Online C Compiler
In this program:
1. Each process is represented by a `Process` structure that includes the process ID (`pid`), burst time, arrival time, and remaining time.
2. The `isCompleted` array keeps track of whether a process has completed execution or not.
3. The program iterates until all processes are completed.
4. In each iteration, it checks each process and executes it if its arrival time is less than or equal to the current time and it has not completed execution.
5. If a process can complete within the time quantum, its remaining time is set to zero, and it is marked as completed. The waiting time, turnaround time, and response time are calculated.
6. If a process cannot complete within the time quantum, its remaining time is reduced by the quantum, and the current time is incremented by the quantum.
7. If all processes have arrived and completed execution in an iteration, the current time is incremented to handle idle time.
8. Finally, the average waiting time, average turnaround time, and average response time are calculated and printed.
Output:
Average Waiting Time: 4.50
Average Turnaround Time: 10.50
Average Response Time: 1.50
Applications of Round Robin
1. Operating Systems: Round Robin is often used as the default scheduling algorithm in many operating systems, particularly in time-sharing systems. It allows multiple processes to share the CPU in a fair & efficient manner, ensuring that each process gets an equal opportunity to execute.
2. Task Scheduling: Round Robin can be applied to task scheduling in real-time systems or embedded systems. It helps in distributing the processing time among different tasks, ensuring that each task gets a fair share of the CPU resources.
3. Load Balancing: Round Robin is commonly used in load balancing techniques, especially in web servers and distributed systems. Using round Robin, incoming requests are distributed among multiple servers in a cyclic manner, ensuring that the workload is evenly distributed and no single server is overwhelmed.
4. Network Scheduling: Round Robin is used in network scheduling algorithms to allocate bandwidth fairly among multiple clients or nodes. It helps prevent any single client from monopolizing the network resources and ensures that all clients get a fair share of the available bandwidth.
5. Gaming & Simulation: Round Robin can be used in gaming and simulation systems to allocate CPU time among different game objects or entities. It helps ensure smooth gameplay and prevents any single entity from consuming excessive CPU resources.
6. Resource Allocation: Round Robin is applied in various resource allocation scenarios, such as allocating CPU time to virtual machines in cloud computing environments or allocating time slots to users in a time-sharing system. It ensures fair distribution of resources among competing entities.
7. Queue Management: Round Robin can be used to manage queues in various applications, such as task queues, job queues, or request queues. It helps process items in the queue in a fair and cyclic manner, preventing starvation and ensuring that each item gets processed within a reasonable timeframe.
Sure, here are three frequently asked questions about Round Robin scheduling, followed by a concise conclusion:
Frequently Asked Questions
What happens if a process's burst time is less than the time quantum?
If a process's burst time is less than the time quantum, it will complete its execution within one time slice & release the CPU voluntarily. The CPU will then move on to the next process in the queue.
Can Round Robin scheduling be used in real-time systems?
While Round-Robin scheduling is simple and fair, its fixed time quantum approach may not suit hard real-time systems with strict deadlines. However, it can be used in soft real-time systems with more flexible timing requirements.
How does the time quantum affect the performance of Round Robin scheduling?
The choice of time quantum is crucial in Round-Robin scheduling. A smaller time quantum leads to more frequent context switches and higher overhead, while a larger time quantum may cause longer process waiting times. The optimal time quantum depends on the specific system requirements and workload characteristics.
Conclusion
In this article, we discussed the Round Robin scheduling algorithm, its working principles, characteristics, advantages, & disadvantages. We looked into examples and programs demonstrating its implementation in C, covering scenarios with different arrival times. Round Robin scheduling is very useful in different domains, like operating systems, load balancing, & resource allocation, which makes it an effective solution for fair and efficient CPU time-sharing among processes.
You can also check out our other blogs on Code360.
428+ registered 
