What is Round Robin Scheduling in OS?

The Round Robin Scheduling algorithm in operating systems enables fast and efficient processing. While it might appear as if all your programs are loading and running simultaneously,  in reality, a CPU (or each core of a CPU) can execute only one process at a time. Round Robin achieves this illusion by rapidly switching between tasks, giving each a brief turn. In this article, we will understand round robin scheduling in extensive detail, with step-by-step working, implementation of the algorithm in C, as well as the uses of the round robin scheduling algorithm.

Table of Contents:

• What is the Round Robin Scheduling Algorithm?
• Key Features and Characteristics of Round Robin Scheduling
• How Does Round Robin Scheduling Work?
• Important Terms in Round Robin Scheduling
• Round Robin Scheduling Example
  • Example with Different Arrival Times
  • Example with Same Arrival Times
• Implementation of the Round Robin Scheduling Algorithm in C
• Use Cases of Round Robin Scheduling
• Impact of Time Quantum Size (Large vs. Small)
• Conclusion

What is the Round Robin Scheduling Algorithm?

The Round Robin Scheduling Algorithm assigns a time quantum (a fixed duration) to each process equally so that no one process starves from waiting for the CPU, and each gets a chance to execute. Operating systems manage CPU sharing by giving each running program tiny, rapid turns, creating the illusion that everything is happening at once. This ensures that all your apps get attention and your computer feels responsive.

Round Robin scheduling provides fairness and prevents starvation of any process that is in the ready queue and is requesting the CPU.

Launch Your Software Engineering Career Today!

Enroll Now and start building scalable applications like a pro!

Explore Program

Key Features and Characteristics of Round Robin Scheduling

Here are the key features of the round robin scheduling algorithm.

• Time Quantum:  It is the period for which each process is allocated the CPU. It is fixed at the time of designing the algorithm and does not change until the developer does so. It usually ranges from 10-100 milliseconds.
• Preemptive: Round robin is a preemptive scheduling algorithm. Preemptive means the OS can pause a running task to give other tasks a turn, giving power to the operating system to forcibly stop or pause a process and assign the resource to some other process.
• Fair Scheduling Algorithm: It promotes fairness by ensuring that every process gets an equal share of CPU time, preventing any single process from monopolizing the CPU.
• Circular Queue: In round robin, processes take turns using the CPU for a set time quantum. Once a process’s turn ends, it rejoins the back of the queue, repeatedly getting CPU time in a cycle until it finishes.
• Context Switching Overhead: Due to preempting the processes, a significant overhead is added to the overall performance of the CPU. Saving the state of one process and loading another takes CPU time.

How Does Round Robin Scheduling Work?

Imagine you are a teacher who has a lot of students in her class, and they all need your help with different questions. If you spend a long time with one student, the doubts of other students will remain unsolved. Instead, you choose to spend exactly five minutes with each student before moving to the next.

The Round Robin scheduling algorithm also follows the same principle. Here is a simple breakdown of the working of the round robin scheduling algorithm. It follows the following steps.

• Process Arrival: A process that needs the CPU to execute enters the ready queue and waits for the CPU to be assigned to it. They wait for their time to access the CPU.
• Time Allocation: Now, the round robin scheduling algorithm assigns each process a specific but brief “time quantum” to use the CPU.
• Execution: The assigned process runs on the CPU for its allotted time and then is preempted by the CPU.
• Rotation: If the process still hasn’t been completed yet, it is pushed back to the end of the ready queue for another turn.
• Repeat: The CPU continuously cycles through processes until each process in the ready queue is completed.

Important Terms in Round Robin Scheduling

Here are a few more terms that you should be familiar with before we further discuss the implementation of the round robin scheduling algorithm.

• Burst Time (or Execution Time): This is the total amount of time a process needs in the CPU to complete its entire execution.
• Ready Queue: This is the list or queue where processes wait for their turn to be executed by the CPU. In Round Robin, this is typically a circular queue.
• Starvation: This is a common problem in scheduling algorithms in which a particular process (can be more than one) never executes because some other process is always getting the CPU.
• Throughput: This represents the number of processes completed per unit of time; while round robin does not always have the best throughput, it should be geared towards fair sharing.
• Turnaround Time: This is the total time from when a process arrives in the system to when it completes execution.
• Waiting Time: The total time a process spends waiting in the ready queue for the CPU.
• Response Time: This is the time from when a process arrives to when it first begins execution. Round Robin generally offers good response times because it gets each process a quick first turn.

Round Robin Scheduling Example

Let us understand the round robin scheduling algorithm in detail with a comprehensive example and step-by-step solution.

Example with Different Arrival Times

Scenario: Consider four processes, P1, P2, P3, and P4, that arrive at different times and have different CPU burst times, and the Time Quantum (TQ) is given as 2 milliseconds. Calculate the Completion Time (CT), Turnaround Time (TAT), Waiting Time (WT), and Response Time (RT) for each process, and then their averages when the Round Robin Scheduling Algorithm is used to schedule these processes.

This is an example of the Round Robin Scheduling Algorithm with different arrival times.

Step 1: Evaluate the Initial State

Initially, the ready queue is empty, the CPU is idle, and right now the time is 0 ms.

• Ready Queue (RQ): Empty
• CPU: Idle
• Time: 0 ms

Gantt Chart:

Step 2: Process 1 (P1) arrives

At 0 ms, P1 arrives in the ready queue.

Since the CPU is idle, the operating system assigns the CPU to P1, and it starts executing from 0 ms.

• Time: 0 ms
• Burst Time of P1: 8
• CPU: Executing P1
• RQ: [P1]

Gantt Chart:

Step 3: Process 2 (P2) arrives

At 1 ms, P2 arrives. At this time, the process P1 is still executing, as it has not finished the time quantum. Therefore, process 2 waits in the ready queue.

• Time: 1 ms
• Burst Time of P1: 8
• Burst Time of P2: 4
• CPU: Executing P1
• RQ: [P2]

Gantt Chart:

Step 4: Process 3 (P3) arrives

At 2 ms, two things happen: process 3 arrives in the ready queue, and P1 completes its time quantum, so the process gets preempted and the CPU is given to the next process in line, which is P2. Hence, P2 is removed from the ready queue and is assigned to the CPU.
The burst time of P1 is 8 ms, and it got CPU for 2 ms, which means P1 has not completed. Therefore, we will push it back into the ready queue after P3 arrives in the ready queue.

• Time: 2 ms
• P1’s remaining Burst Time = 8 – 2 = 6 ms.
• Burst Time of P2: 4
• Burst Time of P3: 9
• CPU: Executing P2
• RQ: [P3, P1]

Gantt Chart:

Step 5: Process 4 (P4) arrives

Finally, at 3 ms, P4 arrives. It is the last process that needs to be scheduled in this scenario, which means no new process will come after this. P4 is pushed into the ready queue, while P2 is still executing.

• Time: 3 ms
• Burst Time of P1: 6
• Burst Time of P2: 4
• Burst Time of P3: 9
• CPU: Executing P2
• RQ: [P3, P1, P4]

Gantt Chart:

Step 6: P2 completes its Quantum

At 4 ms, P2 completes its quantum slice and is preempted by the OS. Now the next process in the ready queue, P3, gets the CPU and it starts executing.
P2 has not completed its burst time yet. Therefore, it will again be pushed back into the ready queue.

• Time: 4 ms
• Burst Time of P1: 6
• Remaining Burst Time of P2: 4 – 2 = 2
• Burst Time of P3: 9
• CPU: Executing P3
• RQ: [P1, P4, P2]

Gantt Chart:

Step 7: P3 completes its Quantum

At 6 ms, P3 completes its quantum, and P1, the next process in the ready queue, gets the CPU. Since P3 is not completed yet, it will again be pushed back to the ready queue.

• Time: 6 ms
• Burst Time of P1: 6
• Burst Time of P2: 2
• Remaining Burst Time of P3: 9 – 2 = 7
• Burst Time of P4: 5
• CPU: Executing P1
• RQ: [P4, P2, P3]

Gantt Chart:

Step 8: P1, again, completes its Quantum

At 8 ms, P1 will complete its execution, P4 will start executing, and P1 will be pushed back to the ready queue with the remaining burst time of 4 ms.

• Time: 8 ms
• Burst Time of P1: 6 – 2 = 4
• Burst Time of P2: 2
• Burst Time of P3: 7
• Burst Time of P4: 5
• CPU: Executing P4
• RQ: [P2, P3, P1]

Gantt Chart:

Step 9: P4 completes its Quantum Again

At 10 ms, P4 will complete its execution with a remaining burst time of 3 ms. It is pushed back into the ready queue, and P2, the next process in the ready queue, starts executing.

• Time: 10 ms
• Burst Time of P1: 4
• Burst Time of P2: 2
• Burst Time of P3: 7
• Burst Time of P4: 5 – 2 = 3
• CPU: Executing P2
• RQ: [P3, P1, P4]

Gantt Chart:

Step 10: P2 completes the Burst Time

At 12 ms, when P2 completes its quantum, the burst time is also completed for P2. This means that now P2 does not need to go back to the ready queue.
It leaves the CPU and the ready queue, with P3, the next process in line, starts executing.

• Time: 12 ms
• Burst Time of P1: 4
• Burst Time of P2: 2 – 2 = 0 (COMPLETED)
• Burst Time of P3: 7
• Burst Time of P4: 3
• CPU: Executing P3
• RQ: [P1, P4]

Gantt Chart:

Step 11: P3 Executes for its Time Quantum

At 14 ms, P3 completes execution with the remaining burst time of 5. P1, the next process in line, starts its execution, and P3 is pushed back to the ready queue.

• Time: 14 ms
• Burst Time of P1: 4
• Burst Time of P3: 7 – 2 = 5
• Burst Time of P4: 3
• CPU: Executing P1
• RQ: [P4, P3]

Gantt Chart:

Step 12: P1 Executes for its Time Quantum

At 16 ms, P1 completes its time quantum of 2 ms, and P4 starts executing. P1 is pushed back to the ready queue, as it still has 2 ms burst time left.

• Time: 16 ms
• Burst Time of P1: 4 – 2 = 2
• Burst Time of P3: 5
• Burst Time of P4: 3
• CPU: Executing P4
• RQ: [P3, P1]

Gantt Chart:

Step 13: P4 Executes for its Time Quantum

At 18 ms, P4 completes its time quantum, and P3 starts executing. P4 is again pushed back to the ready queue.

• Time: 18 ms
• Burst Time of P1: 2
• Burst Time of P3: 5
• Burst Time of P4: 3 – 2 = 1
• CPU: Executing P3
• RQ: [P1, P4]

Gantt Chart:

Step 14: P3 Executes for its Time Quantum

At 20 ms, P3 completes its time quantum and is pushed back to the ready queue with a remaining burst time of 3 ms. P1 starts executing.

• Time: 20 ms
• Burst Time of P1: 2
• Burst Time of P3: 5 – 2 = 3
• Burst Time of P4: 1
• CPU: Executing P1
• RQ: [P4, P3]

Gantt Chart:

Step 15: P1 and P4 complete their Burst Time

At 22 ms, finally, the P1 completes its burst time and exits the CPU. Now, only P3 and P4 are left in the ready queue. Since P4 is at the starting index, it starts executing.

• Time: 22 ms
• Burst Time of P1: 2 – 2 = 0 (COMPLETED)
• Burst Time of P3: 3
• Burst Time of P4: 1
• CPU: Executing P4
• RQ: [P3]

Gantt Chart:

At 23 ms, P4 executes for only 1 ms of time quantum because only 1 ms of burst time is left for P4. Once completed, it will leave the CPU. The CPU will be assigned to P3, the only process left in the ready queue.

• Time: 23 ms
• Burst Time of P3: 3
• Burst Time of P4: 1 – 1 = 0 (COMPLETED)
• CPU: Executing P3
• RQ: []

Gantt Chart:

Step 16: The Final Process P3 Completes Its Burst Time

Now, this is a tricky part, and you need to pay attention. Just because one process is left in the ready queue does not mean it will continue executing, ignoring the time quantum.
It will still follow the time quantum of 2 ms, preempt P3, push it back to the ready queue, and then again execute P3. This introduces an additional overhead.

• Time: 25 ms
• Burst Time of P3: 3 – 2 = 1
• CPU: Executing P3
• RQ: [P3]

Gantt Chart:

• Time: 26 ms
• Burst Time of P3: 1 – 1 = 0 (COMPLETED)
• CPU: Completed Execution
• RQ: Empty

Calculating the Metrics

Now, let us calculate the turnaround time (TAT), Waiting Time (WT), and Response Time (RT) for each process. They are calculated using the following formulas.

Turnaround Time (TAT) = Completion Time - Arrival Time
Waiting Time (WT) = Turnaround Time - Burst Time
Response Time (RT) = First Start Time - Arrival Time

The times that each process first got the CPU can be calculated using the Gantt Chart.

• P1 first starts at 0
• P2 first starts at 2
• P3 first starts at 4
• P4 first starts at 8

Now that we have calculated the turnaround time (TAT), waiting time (WT), and response time (RT) for each process, let us move forward and calculate the average of each of these metrics.

• Average Turnaround Time (TAT) = (22+11+24+20)/4 = 77/4 = 19.25 ms
• Average Waiting Time (WT) = (14+7+15+15)/4 = 51/4 = 12.75 ms
• Average Response Time (RT) = (0+1+2+5)/4 = 8/4 = 2 ms

Example with Same Arrival Times

Scenario: Let us consider another scenario, where all processes are in the ready queue from the start. We will use the same Time Quantum (TQ) of 2 milliseconds.

Let us quickly examine how the processes will be assigned to the CPU and how they will run.

• At 0 ms, P1 will begin its turn, and it will run for 2 ms of the time quantum.
• At 2 ms, P1 will be paused (remaining burst time is 6 ms total), and P2’s turn begins (it runs for 2 ms).
• At 4 ms, P2 will be paused (it needs CPU for 2 ms more), and P3 will begin (it runs for 2 ms).
• At 6 ms, P3 will be paused (it needs 7 ms total), and P4’s turn begins (it runs for 2 ms).
• This cycle of each process being assigned the CPU for 2 ms, being preempted, added to the ready queue if it needs more time, and running again continues. This will go on until all processes have completed the total burst time.

Final Outcomes

After all of the processes have completed their time quantum, here is a table showing when each process ends, and the amount of time each process took:

Calculating the Metrics

• Average Turnaround Time = (22+12+26+18)/4 = 78/4 = 19.5 ms
• Average Waiting Time = (14 + 8 + 17 + 13)/4 = 52/4 = 13 ms
• Average Response Time = (0 + 2 + 4 + 6)/4 = 12/4 = 3 ms

Implementation of the Round Robin Scheduling Algorithm in C

Now that we have completely understood the working of the round robin scheduling algorithm, let us implement it using the C programming language. We will implement both scenarios with the same arrival time of the process and different arrival times of the process.

C Program for Different Arrival Times

Output:

Explanation: This code is an implementation of the same scenario we took as an example for the round robin scheduling algorithm, with different arrival times of the processes.

C Program for Same Arrival Times

Output:

Explanation: This code is an implementation of the same scenario we took as an example for the round robin scheduling algorithm, with the same arrival time of the processes, that is 0 ms.

Use Cases of Round Robin Scheduling

Round Robin scheduling works well in the following scenarios.

• Time-Sharing Operating Systems: Users of desktop systems with different types of operating systems, such as Linux and Windows, expect quick feedback and the ability to multitask. This is the primary usage of round robin scheduling algorithms.
• Interactive Systems: It is suitable for systems where users interact frequently and expect low response times, for example, web servers and gaming platforms.
• Load Balancing: In network routers, round robin can be used to distribute incoming requests or data packets equally among available resources. This makes sure that no single resource is overloaded.
• Situations where Burst Times are Unknown: The Round Robin scheduling algorithm is also good for situations where you don’t know how long a process will run (burst time). With this method, every process gets a turn with the CPU, ensuring no process is left waiting indefinitely.

You should consider round robin when fairness among processes, low response time, and preventing process starvation are crucial for a multitasking environment.

Impact of Time Quantum Size (Large vs Small)

Choosing the time quantum is the most critical step of the round robin scheduling algorithm. Choosing a time quantum that is too large or too small will have different impacts on the efficiency and advantages of the algorithm.

1. Very Large Time Quantum

If the time quantum is too large, the algorithm starts behaving like the FCFS algorithm. Long processes will then occupy the CPU for a long time, causing other processes to wait significantly, which will ultimately lead to starvation.

The number of context switches decreases, and the CPU spends less time on overhead, which leads to better throughput (performance).

2. Very Small Time Quantum

A time quantum that is too small leads to very frequent preemption, leading to a large number of context switches and overhead. It reduces the CPU’s actual productive work and significantly decreases overall system throughput.
Either way, it is good for short I/O-bound processes, as it increases the responsiveness of the I/O requests.

3. Finding the Optimal Time Quantum

The ideal time quantum is a trade-off between short and large time quanta. It should be small enough for a good response and large enough to decrease the context-switching overhead. Often, values between 10 ms and 100 ms are chosen in practice.

Build a Solid Foundation with C Programming!

Join the Course Now and strengthen your programming logic with C!

Explore Program

Conclusion

The Round Robin Scheduling Algorithm may seem complex at first for a beginner, but after understanding the flow and step-by-step working with an example, you will understand how simple it is. At its core, this algorithm ensures fairness in CPU allocation by giving each process a fixed, small slice of time, known as the time quantum. Make sure to use a Gantt Chart whenever attempting a scheduling question using the round robin scheduling algorithm. This graphical representation clearly illustrates the sequence of execution, showing when each process starts, stops, and gets the CPU, making it much easier to track remaining burst times and calculate key performance metrics.

Round Robin Scheduling in OS – FAQs