Round Robin CPU Scheduling Algorithm (Part-5)

In this blog, we are going to learn the Round Robin CPU Scheduling algorithm, which I think used most of the times. Let’s get started with the today’s discussion:

Introduction

The round-robin (RR) scheduling algorithm is designed especially for time sharing systems. It is similar to First Come First Serve (FCFS) scheduling, but preemption is added to enable the system to switch between processes.

In this type of scheduling each process runs for a small amount of time which depends on the implementation, this small amount of time is called a time quantum or a time slice. Once a process runs for that time quantum the CPU switches to the next process in the queue. Once all processes have run it cycles back to the first process.

For example,

Let us take the example where we have the following three processes,

Burst time for different processes

Let us take the time quantum to be 4 milliseconds. Here, we have used the term “Time Quantum”, Are you clear with this term?

First 4 ms will be taken by the process P1 after which the algorithm will switch to process P2 since it only needs 3ms it will be completed in the time quantum itself, the same will happen for process P3. Now P1 still needs 20ms more so it will again run for the time quantum. Since it is the only process remaining in the ready queue it will continue executing till it ends.

Therefore, the Gantt chart for it will be as follows:

Gantt chart for scheduling

From the gantt chart, we can find the waiting time for all the processes,

Waiting time for P1 process = 6 ms

Waiting time for P2 process = 4 ms

Waiting time for P3 process = 7 ms

Therefore, Average waiting time = 17/3 = 5.66 ms

If we had used FCFS scheduling the average waiting time would be (24 + 27)/3 = 17ms. Thus we observe that Round Robin is a major improvement over First Come First Serve (FCFS) Policy.

The efficiency of this algorithm depends heavily on the size of the time quantum. In case we use a very small time quantum (like 0.5ms) there would be a large number of context switches.

For example, if a process is of 4 ms and we keep time quantum of 0.5 ms there would have to be 8 context switches, as opposed to 0 context switches and no overhead if we keep the time quantum as 4 ms. We should also be careful and not make the time quantum very large since it would result in the same performance as FCFS. We can see it by taking the above example and taking the time quantum as 25 ms.

Thus, we want the time quantum to be large with respect to the context switch time. If the context-switch time is approximately 10 percent of the time quantum, then about 10 percent of the CPU time will be spent in context switching. In practice, most modern systems have time quanta ranging from 10 to 100 milliseconds.

Important Points

In Round Robin Scheduling,

1. CPU is assigned to the process on the basis of FCFS for a fixed amount of time.
2. This fixed amount of time is called as time quantum or sometimes also known as time slice.
3. After the time quantum expires, the running process is preempted and sent to the ready queue.
4. Then, the processor is assigned to the next arrived process.
5. It is always preemptive in nature.

Image Source: Link

Therefore, Round Robin Scheduling is FCFS Scheduling with preemptive mode.

Code Snippet

The implementation of RR would be as follows -

Code to implement Round-Robin algorithm

Quiz Time

1. With increasing value of time quantum,

(a) Number of context switch decreases

(b) Response time increases

(c) Chances of starvation increases

(d) All of the above

2. Which of the following statements are true?

(a) When time quantum tends to infinity, Round Robin Scheduling becomes FCFS Scheduling.

(b) With increasing value of time quantum, Round Robin Scheduling tends to become FCFS Scheduling.

(c) The performance of Round Robin scheduling heavily depends on the value of time quantum. Therefore, the value of time quantum should be such that it is neither too big nor too small.

(d) All of the above

Conclusion (Wrap Up)

This blog has taught us about the Round Robin CPU Scheduling algorithm, which belongs to the pre-emptive group of scheduling algorithms. In addition, to this, we have also solved a numerical problem on the same.

This completes the part-5 of this blog series on CPU Scheduling.

Thanks for reading!

We hope you found the content interesting. If you enjoy it, please share it with your friends. Something not stated, or would you want to offer your thoughts? Please leave a remark below, and we will respond as soon as possible. 😉