Round Robin Scheduling - Solved Problem (Part 1)

in the previous lecture we have discuss about round-robin scheduling and we have also taken a small example and have seen how it works so in this lecture we will be solving another problem all around drop-in scheduling so let us see what is this problem so here it says consider the set of five processes whose arrival time and burst time are given below if the CPU scheduling policy is a round-robin with time quantum equals to 2 units calculate the average waiting time and average turnaround time so here in this problem we are given a set of

5 processes with process IDs P 1 2 P 5 and their arrival times are given here and the burst times are given here so we are required to find the average waiting time and the average turnaround time if the scheduling policy is a round-robin and the time quantum is 2 units so this is a little bit different from the previous example that we have discussed in the previous lecture because in the previous lecture the arrival times were not given and it was assumed that all the processes arrived at the same time so it was a

bit easy to calculate but in this example or in this problem the arrival times also are given for this set of processes so we have to keep in mind dis arrival times and there are many things that we have to keep in mind and be very attentive when we are solving this problem of this kind so this is going to be a bit lengthy because I am going to explain in detail about how it works so that is why I have divided this lecture into two parts so in this first part we will be seeing

how we can form the Gantt chart for this set of 5 processes which is the most crucial step and in the next part we will be calculating the average waiting time and their race turnaround time so keep in mind that this is a round-robin scheduling and we know that in round-robin scheduling each process is allowed to execute for a particular time quantum which is two units in this case and after the time quantum the process will be preempted after that the CPU will be given to the next process waiting in the queue and this pattern

continues so that is what happens in round-robin scheduling so since the arrival times also are given here there are many things that we need to keep in mind we have to solve it very attentively so it is not very difficult but you have to be very careful so let's see how we can form the Gantt chart for this set of five processes so I have copied down the same table over here and here keep in mind that the time quantum is two units and here I am having a clock which will help us to keep

track of the time and see what happens at different time units so you don't have to draw this clock in or when you are really solving the problem but in order to make you understand I am taking this example so let's see how the Gantt chart can be formed so here I have formed the Gantt chart for this set of processes and don't worry looking at this I am going to explain it in detail and also we are having a ready queue here so in this ready queue we will be putting the processes that are

coming and waiting in a ready queue so that will be represented here so remember that this right hand side will represent the head of the queue and the left hand side will be the tail of the queue so when the first process arrives it will be kept here and when the second process arrives it will be kept behind that and when the third processor halves will be kept behind that and so on so that is what we mean by the head and the tail of the queue so let us see how all these things work

so first of all let's look at this table and let's see what happens at different units of time so in this clock we'll be starting from the zero with unit of time so at time zero let's see what happens so at time zero the process p1 arrives so here we see that p1 is the first process to arrive so p1 is the process that comes and waits in the ready queue because it is a first process and it is ready to be executed so at time zero process p1 comes and it is ready to be

executed and since there were no other processes at this time so what will happen p1 will be given the cpu so p1 will be now coming to our Gantt chart which shows that it gone to CPU and it has begun its execution so we can remove p1 from the ready queue because in the ready queue the processes will be there when they are waiting for the CPU but once they get the CPU they will not be in the ready queue anymore so p1 is removed from the ready queue and it is now continuing its execution

in the cpu now let's see what will happen next so here we were at time zero now let's go to the next unit of time so the next unit of time is time one so let's see what happens at time one so at time 1 p1 is still continuing its execution we know that the time quantum is two units so p1 has not completed two units it is still within the time quantum of two units because we are just at time one so p1 continues his execution now let's see what happens in this table so

in this table we see that at time 1 p2 has arrived so p2 is arriving at time 1 but it cannot be given the cpu at this time because p1 is currently using the cpu and has not completed its time quantum of two units so what will happen pee-yew 2 will be placed in the ready queue so we have p2 in our ready queue now so that is all that happens at time one now let's see what will happen at the next unit of time so the next unit of time is time - so at

time two what happens there is an alarm ringing so why does the alarm ring the alarm rings because we know that the time quantum is two units so the ringing of his alarm signifies that the time quantum has ended and it is time to preempt the currently executing process and it is time to give the cpu to the next process waiting in the ready queue so that is what we have to do so at time two P 1 will be preempted and P 2 will be given the cpu because P 2 is the process that

is waiting at the head of the ready queue so that is what we have to do at time 2 now when P 1 is preempted what is the remaining burst time of P 1 even that we have to keep in mind so the burst time of P 1 is 5 units of time and here it has executed for 2 units of time so there is a remaining of 3 units of time that P 1 needs to execute so P 1 has not completed its execution so keep that in mind and since V 1 has also

not completed this execution P 1 will also be now placed in the ready queue so shall we place P 1 here wait before we place P 1 here let us also look if there were any other processes that has arrived at time 2 so if you see the table we see that P three also has arrived at time 2 so P 3 will be placed at the ready queue and after that this P 1 which was preempted will be placed behind that so P 2 will be now removed from the radiator because it is now

going to get the CPU for its execution so let's remove P 2 and place the other two processes so this is what our ridiculous like now P 2 got the CPU and is going to begin its execution and P 3 which has arrived at two units of time is placed at the head of the ridicu and P 1 which was preempted now and has a remaining burst time of 3 units of time is placed behind P 3 and the ready queue so this is what happens at time 2 so P 2 will now begin its

execution now let's see what will happen at the next unit of time so the next unit of time is 3 units so at 3 units let's see what happens so at 3 P 2 is still continuing its execution because it has not yet completed 2 units it can actually execute from 2 to 4 units of time so at time 3 P 2 is still executing and let's see our table what happens in this table we see that there is a new process P 4 that has arrived at time 3 so at 3 units of time

P 4 has arrived and P 4 has to be placed at the ready queue because right now this gunshot cannot be disturbed because P 2 is executing and it has not completed its time quantum so P 4 will now be placed at the ready queue so P 4 is now placed at the tail of the ready queue and this is what our ready Q looks like at time 3 now let's see what will happen at the next unit of time so the next unit of time is time for so at 4 unit of time what

happens the alarm rings again why did the alarm ring because the time quantum of two units are complete so from 2 to 4 the clock ran and that was 2 units of time so the alarm rings which signifies that the process that is currently executing should be preempted and the CPU should be given to the next process waiting in the ready queue so which was the process executing it was P 2 P 2 was the one using the CPU and at time 4 P 2 has to be now preempted and the next process should be

given the cpu so now which is the next process that should be given the CPU we have to see the ready queue so in the ready queue p3 is at the head of the ready queue so p3 will be given the CPU and P 2 will be preempted now when this happens what is the remaining burst time of p2 let's see the first time or the total burst time of p2 is 3 units of time and it has executed for 2 units here so there is a remaining of 1 unit so p2 has a remaining

of 1 unit of time which has to be executed later so p2 also has to be placed at the end of the ready queue but let's see if that is the case or if there were any other processes that arrived at time 4 so if you see at time 4 there is another process p5 that has arrived so p5 also has to be placed at the end of the ready queue so what we'll do is we'll first place p5 at the end of the ready queue and behind that we will be placing p2 which was

preempted so always remember that the process that is preempted will always be the last one in the queue so we'll first place p5 then p2 and p3 is the one getting the CPU and going to begin its execution so we can remove p3 from the ready queue so this is what our ready queue will look like now p3 is taken from the ready queue and it's put in the Gantt chart because it is using the CPU for its execution and p5 which has arrived at time 4 is capped at the ready queue and p2 which

is preempted is also kept at the end of the ready queue so this is what happens at time 4 now let's see what will happen at the next unit of time that is 5 units so at the fifth unit of time let's see what is happening so if you look at the Gantt chart p3 was a process that was executing now p3 gone to CPU at 4 units at the previous unit and what is a burst time of p3 the burst time of p3 is only 1 unit of time so it does not have to

use for the total 2 units that is the time quantum but it only has to use for one unit of time so at time 5 p3 will complete its execution and it will voluntarily release the CPU and the CPU will be given to the next process in the queue that is p1 p1 is on the head of the queues of p1 repeater one to get the cpu so here the alarm is not going to ring because the time quantum of two units were not complete and the bursts time of p3 was only one unit of

time which is less than the time quantum so p3 voluntarily releases the cpu and then gives the cpu to the next process in the queue that is p1 so we can remove p1 from the ready queue and put it into the Gantt chart again so p1 is now getting the cpu and it's continuing its execution so how long does it have to continue it can continue for only two units but also remember that it has a remaining of three units of time so p1 continuous execution and let's see what happens in the next unit of

time so the next unit of time is 6 so at the 6 unit what happens there are no new processes that are arriving and p1 is using the cpu and p1 needs to use it for 3 units of time what is allowed for only 2 units which is a time quantum and the time quantum is also not yet expired because p1 started this execution at 5 units and it will actually be allowed to execute up to 7 units 5 plus 2 is 7 so at the sixth unit of time nothing much happens it's just p1

continuing its execution and these processes still waiting in the ready queue now let's go to the next unit of time now the next unit of time is 7 units and at CERN unit the alarm rings now why does it ring because p1 was using the CPU for 5 up to 7 2 units that is a time quantum is complete so the alarm rings notifying that the present process has to be preempted and the next process should be given the cpu so p1 will now be preempted and the next process that is p4 will be given

the CPU because p4 is the one at the head of the ready cube so that is what will happen now did p1 finishes execution let's see p1 had a remaining burst time of 3 units of time but it has executed only for 2 units here so still there is a remaining of 1 unit of time that p1 needs to execute so p1 will again be put at the end of the ready queue because it still has to use a CPU before we can remove it from the readyq you know because it will get the CPU

here and P 1 which was preempted will be kept at the end of the ridicule so this is what I already Q looks like now before is taken from the ready queue and put into the Gantt chart because it is going to begin its execution and P 1 which was preempted is put at the end of the ridicule so before now begins its execution and it will have to execute for how long the burst time of P 4 is 2 units of time so anyway let's see what will happen at the next unit of time

so the next unit of time is 8 and at 8 we see that there are no processes newly arriving and also the present process that is executing is P 4 which has to execute for 2 units of time and at the 8th unit of time it has completed only 1 unit of its execution and has to execute for another 1 more unit of time so there is nothing much happening here it is just P for doing its execution and these processes waiting in the queue so let's go to the next unit of time now so

at the next unit of time that is at the ninth unit the alarm rings again why because the CPU was used from seven to nine units that is two units here so the time quantum is complete and the alarm rings and the process that was using the CPU that is P four has to be preempted so if you see here we also see that the bursts time of p4 is also two units of time so even though it is not preempted also it was going to release the CPU anyway after two units of time so

P four has completed its execution and P 4 will release the CPU now and the CPU will be given to the next process and what is the next process the next process is P 5 so P 5 is the one waiting in ready queue now so P 5 will be given the CPU and the remaining process here will continue to wait in the ready queue so P 5 is removed from the ready queue and is now in the Gantt chart beginning its execution so remember P 5 also needs to execute for 3 units of time

that is its burst time so the other processes P 3 we see that P 3 already completed and P 4 also we saw that it already completed so let us just strike them out so at time 9 what will and b5 got the CPU and it is beginning its execution so now let's go to the next unit so the next unit is 10 at 10 units of time what happens we see p5 is continuing its execution it is still within the time quantum so there is nothing new happening p5 is continuing his resolution and there

are no other processes that arrives so nothing much is happening only p5 is continuing its execution at time you need 10 so let's proceed to the next unit so the next unit of time is 11 so the 11th unit of time the alarm rings again why because the CPU was used from 9 to 11 that is 2 units that is a time quantum so the alarm rings notifying that the present process has to be preempted so which was a present process it was p5 so p5 will be preempted and the CPU should be given to

the next process in the ready queue and which is that it is p2 which is at the head of the ready queue now p5 did it complete its execution no because the burst time of p5 was 3 units of time and it has only executed for two units so there is a remaining of one unit that p5 has to execute later on so p5 will be put at the end of the ready queue and p2 will get the CPU so p2 can be removed from our ready queue so this is what our ready queue will

look like now p2 went here to the Gantt chart and p5 there was preempted is kept at the end of the ready queue so at time 11 p2 that got the CPU now will begin its execution so let's see what will happen at the next unit of time so the next unit of time is 12 units so at 12 units what happens so at 12 units we see that p2 was executing and we see that Peters remaining Burslem was only 1 unit of time so from 11 to 12 p2 executed and it took less than

the time quantum so there is no alarm going off but p2 has completed its execution and will voluntarily release the CPU so p2 here has completed its execution alright so what is the next process the next process is p1 that is waiting at the head of the ready cube so p1 will now be given the CPU so p1 is removed from the ready queue and put in the Gantt chart because p1 gets the CPU for its execution and let's see what will happen at the next unit of time now so the next unit of time

is I'm 13 so what happens at I'm 13 who was using the CPU p1 and what is the remaining burst time of p1 it was only 1 unit of time so p1 executes for 1 unit and at the 13th unit it completes its execution so the execution of p1 is complete and it took less than that time quantum of 2 units so there is no alarm going off in our clock so p1 will voluntarily or release the CPU at the 13th unit of time and will give the CPU to the last process that is waiting

in our ready queue that is p5 so p5 will now get the CPU at the 13th unit of time and how long it has to execute it has to execute for only one unit so p5 is removed from the ready queue and it comes to the Gantt chart and it gets the CPU for its execution so at the next unit of time that is at the 14th unit p5 will complete its execution because it has a remaining burst time of only one unit of time so p5 execution is also complete at the 14th unit of

time and there are no more processors waiting in the ready queue which signifies that all of the processes has completed their execution so even if you look at this table we see that there are no more processes that needs to be executed because all their burst times are complete and there are no processes in the ready queue so at the 14 unit of time all of the processes completed their execution so this is how you can form the Gantt chart for a set of processes that follow a round-robin scheduling and when the arrival times are

given given in the sense when there is a different arrival time so when they are having the same arrival time you don't have to keep this many things in mind but when the arrival times are different you need to keep all these things in mind so keeping all these things in mind if you can form the Gantt chart then the rest of the process will become very easy so I hope this formation of Gantt chart for this round-robin scheduling when arrival times are given is clear to you so thank you for watching and in the

next part we will be calculating the average waiting time and you have race turnaround time for this same set of processes for the same problem so see you in the next one [Applause] [Music]