Scheduling Algorithms - Round Robin Scheduling

so far we have discussed about three scheduling algorithms namely the first-come first serve scheduling the shortest job first and the priority scheduling so in this lecture we are going to discuss about the next scheduling algorithm which is also a very important scheduling algorithm and that is the round-robin scheduling so we will see what is this round-robin scheduling and how it works the round-robin scheduling algorithm is designed especially for time sharing systems so why is it designed for time sharing systems we will understand that as we move ahead and it is similar to the FCFS scheduling

but preemption is added to switch between processes so this round-robin scheduling algorithm in one way is similar to the first come first serve scheduling but preemption is added to switch between the processes and we will be seeing how it is done as we move ahead so here a small unit of time called a time quantum or a time slice is defined which is generally from ten 200 milliseconds so in this round robin scheduling what happens is that we define a small unit of time which is usually called the time quantum or a time slice and

this time quantum or time slice is generally defined from 10 200 milliseconds so it will for between 10 and hundred milliseconds and what happens is that each processes will be assigned this time quantum for its execution so whether the CPU burst of the process is greater than the time quantum or not does not matter but this specific time quantum is assigned to each process and a process will be allowed to execute only for that particular time quantum in the first round and after that the CPU will be given to the next process that is waiting

in the queue and that process also will be allowed to execute for that specific time quantum and then the CPU will be given to the next process and so on so what happens is the ready queue is treated as a circular queue and the CPU scheduler goes around the ready queue allocating the CPU to each process for a time interval of up to time quantum so that is what I just explained so here what will happen is the ready queue where the processes are waiting is treated as a circular queue so I have shown this

using this diagram over here so think of this as a circular queue so this is the ready queue and the processes are waiting in this circular queue waiting for its turn to get the CPU for its execution so here we are having ten processes processes P 1 P 2 P 3 up to P 10 so they are waiting in this queue and when a new process comes they will be added to the end of the queue or at the tail of the queue so this is process P 10 which is the last process so if

a new process arrives it will be added after this P 10 at the tail of the queue so you may not be able to visualize the tail of the queue because it is circular over here but actually it is not circular in shape but just to make you understand I have taken this diagram it is actually just a normal queue where the CPU scheduler will move from one end of the queue to the other end and then come back to the start and again move from the start to the end and it goes on like

that so that is why we have take today using a circular queue so we have processes P 1 2 P 10 waiting in this circular a ready queue waiting for getting the CPU for their execution so what happens is there is a CPU scheduler that will assign the CPU to this particular processes so first of all the CPU scheduler will come and assign the CPU to the first process that is there it is p1 so in this way it is going to start like a FCFS scheduling first-come first-serve so whoever is first will be first

given the cpu and for how long will it be given the cpu it will be given the CPU for a particular time quantum so there will be a particular quantum of time that will be defined and only for that amount or that period of time the CPU will be assigned to a particular process so let's say that the time quantum is 5 milliseconds so what will happen is the CPU will be given to p1 for 5 milliseconds so p1 gets a CPU and uses it for 5 milliseconds that is one time quantum so after that

the cpu scheduler will come and give the cpu to p2 which is a next process that is waiting in the circular queue so p2 will get the CPU and will also be allowed to execute for five milliseconds which is a particular quantum of time and after that p3 will be given the CPU and will be allowed to execute for five milliseconds and so on so it will go around like this in the circular queue and when it reaches the end of the queue what happened is that it will again come and check if p1 has

completed its execution or not so if p1 has completed its execution then p1 does not have to get the CPU again but if p1 did not complete its execution in the first quantum of time that it has received then the cpu will again be given to p1 and it will again be allowed to execute for one quantum of time which is 5 milliseconds in this example that we are talking about and then it will go on like that for the other processes as well so that is what happens in a round-robin scheduling now we will

see how this round-robin scheduling is implemented so if you understood the above example that I have taken it is very easy to understand the implementation of round-robin scheduling so let's see how it is implemented so what happens is we keep the ready queue as a first in first out queue of processes so we are keeping the ready queue as a FIFO queue as shown here so I have shown you a circular queue in the previous diagram so actually what it is just a first in first out queue so where we have a head of the

queue and we have the tail of the queue and new processes are added to the tail of the ready queue so whenever a new process arrives the process will be added to the tail of the queue then what happens is the cpu scheduler picks the first process from the ready queue sets a timer to interrupt after one time quantum and dispatches the process so after this what happens is the cpu scheduler will pick the first process that is at the head of the queue and it will set a timer to interrupt after one time quantum

so as I already explained the time quantum is a particular period of time that will be defined so for different cases we may have different quantum of times so sometimes it may be three milliseconds or four milliseconds or 50 millisecond and so on so we will define a time quantum and then once the cpu scheduler assigns the CPU to the first process that is there at the head of the queue at that moment a timer will be set and a timer will be running and then the timer will run for that one time quantum so

let's say if it was 5 milliseconds it will be running for 5 milliseconds so at the fifth millisecond the timer goes off and at that time the CPU scheduler will take control of the CPU away from this process that was using the CPU and it will give it to the next process it was waiting in the ready queue and it goes on like that even this process will use it for that particular time quantum then it will be given to the next process and so on so once it reaches the tail of the queue what

will happen is the CPU scheduler will again come back to the first process and see if it has completed its execution or not and if it has not completed its execution it will give the control of the CPU to this first process again and can again execute for one time quantum and then it will go on like that so we see that it is going in a circular fashion so that is why I have shown you a circular queue in the previous diagram all right so this is what happens now when the CPU scheduler picks

the first process from the ready queue sets a timer to interrupt after one time quantum and dispatches the process so after this what will happen so there are two cases that can occur after this so let us see what are those two cases so here are the two things that can happen so the first case is when the process gets the CPU the process may have a CPU burst of less than one time quantum so it means here is that we are having a time quantum which is a particular period of time as I already

told you and the CPU burst of the process may be less than the time quantum so let's say that the time quantum that we have defined is 5 milliseconds but the burst time is only 3 milliseconds so then what happens the process itself will release the CPU voluntarily because the process itself is having only 3 milliseconds of burst time but the time quantum that is assigned to it is 5 milli seconds so it does not have to use the CPU for five milliseconds so after using it for three milliseconds that process can release the CPU

and it will do so voluntarily so that is what we are talking about here so when the CPU is release voluntarily by that process what will happen the CPU scheduler will then proceed to the next process in the ready queue so when the CPU is released by that process it was using the CPU the CPU scheduler will then give the CPU to the next process waiting in the ready queue so this is one thing that can happen this is the case when the CPU bursts of the process is less than one time quantum so that

is what happens now what is the next case that we have so the next case that we have is the CPU burst of the currently running process is longer than one time quantum so if the CPU burst of the process is longer than one time quantum then what happens so for example if the time quantum that we have defined is five milliseconds but let's say that the burst time of the process is ten milliseconds then what will happen at the fifth millisecond the timer will go off and will cost and interrupt to the operating system

so when one time quantum period has completed the timer will go off and it will cause an interrupt to the operating system then what happens after that a context switch will be executed and the process will be put at the tail of the ready queue so that is what actually happens so let's say that this is the process that we are talking about arose at the head of the queue and it got the CPU for its execution and it was executing now the burst time of this process is actually greater than the time quantum that

we have so we are assuming that it is having a time quantum of ten milliseconds so if the time quantum is only five milliseconds so it will execute for the first five milliseconds and after that the timer goes off then what happens it did not actually complete its execution there are more five milliseconds remaining so what will happen this process will be taken from here and it will be put at the tail of the ready queue it comes from here to here it will come at the tail of the ready queue so that is what

will happen and then the CPU scheduler will then select the next process the ready queue so what would become the next process this will be the next process now because this has gone to the tail so this is the next process and this will begin its execution so remember that when a process has not completed its execution and when the CPU is taken away from it there is a context switch happening and at that time the current context of that process has to be saved because we know that this process did not complete its execution

so we have to save the current state of that process because when the CPU will be given to the process again later on we should know from where it has to continue its execution so the context or the state of that process has to be saved so that is also done in this case so this is what will happen in the case where the first time of the currently running process is longer than the time quantum so if you see clearly here from what I have explained we can understand that it is not actually the

CPU scheduler that is going around and wrong making a circle but the CPU scheduler is here always speaking the process at the head of the queue so what happens is when a process did not complete its execution but has exceeded one time quantum it is taken from the head of the queue and put at the tail then it continues in the straight way again so the CPU scheduler will always pick what is at the head of the queue so when this is put from the head to the tail this becomes a new head and the

CPU scheduler will pick that process so that is how it actually works so this is a very important scheduling algorithm and it is mostly used for time sharing systems so as we see the time is shared between the processes that we are having so here we have to be also very careful about choosing that time quantum if we are choosing a very big time quantum there may be some disadvantages and if we are choosing a very small time quantum there will be too many context switches that will happen so we have to strike a balance

between these two to make this algorithm work in an efficient way so if we are choosing a very large time quantum then this round-robin scheduling algorithm will become like a first come first serve scheduling algorithm like for example let's say that we have a time quantum of 50 milliseconds and then the process that is that the head of the queue is having a burst time of 40 milliseconds and then the other processes that are waiting in queue are having smaller burst times of let's say 3 4 5 milliseconds and so on so what will happen

the scheduler will pick the first process that is at the head of the queue and it will be assigned the CPU and the time quantum that we have assumed here is 50 milliseconds and the burst time of this process that we have assumed is 40 milliseconds so this process will be executing for that 40 milliseconds completely because the time quantum is anyway larger than that so for that 40 minutes against these processes will be keep on waiting for this process to release the CPU so it is becoming like a first-come first serve scheduling and again

these processes are starving for a long time for the CPU so if we are having a large time quantum that is what will happen and also if we are having a very small time quantum what will happen there will be too many context switches that is let's say that the time quantum is only one millisecond and if this process is having a worse time of 5 milliseconds we see that it will first get the CPU and it will be executed only for 1 millisecond then it will be switched then the next one will get and

so on so we see that this process that is having 5 milliseconds of burst time has to be switched a minimum or for 4 times so there are so many number of context switches happening so that is also not a very good thing for an efficient algorithm so we have to strike a balance between the two so that is how the round-robin scheduling algorithm is implemented and that is how it works so in the next lecture we will be discussing about how to calculate the average waiting times and the average turnaround times for a round-robin

scheduling and we will also see the factors on which these things depend so it is a bit different from the other scheduling algorithms that we have discussed so far so we will be taking it up as a different lecture so I hope this was clear to you thank you for watching and see you in the next one [Applause] you [Music]