Priority Scheduling (Solved Problem 1)

in the previous lecture we have discussed about priority scheduling and we have seen how it works so in this lecture we'll be discussing a solved problem on priority scheduling and this question was also asked in gate cs 2017 alright so let's see what is the question and let's see how we can solve it so here is a problem consider the set of processes with arrival time given in milliseconds CPU bursts time given in milliseconds and priority where 0 is the highest priority is shown below none of the processors have iovers time the average waiting time

in milliseconds of all the processes using pre-emptive priority scheduling algorithm is blank all right first of all let's try to understand what this question is trying to ask so here it says that we are given five processes with process IDs P 1 2 P 5 and their arrival times given in milliseconds which is shown here and there both times also given in milliseconds which is shown here and then we are having the priority of each of these processes shown in this last column and then 0 is the highest priority so if you see 0 this

is the highest priority and the next highest priority will be 1 then 2 & 3 & 4 so we are given this much of information and then also it is said that none of the processors have IO births time so what they mean by this is that here we are given the birth time so birth time is the time that a process spends execution in the CPU and IO burst time is the time that the process spends for input/output operations so here it says that it does not have any i/o births time so we just

need to consider only the CPU births times which are given here all right so given these informations we are to calculate the average waiting time in milliseconds of all the processes given above using preemptive priority scheduling algorithm so we need to assume that the CPU is following a pre-emptive priority scheduling algorithm and if it is following a pre-emptive priority scheduling algorithm then what will be the average waiting time for this set of 5 processes so that is what we are asked and we are given four options a 29 B 30 C 31 and D thirty

two so these options are very similar to each other so if you are trying to guess then you may have a hard luck so let us see how we can solve this in the correct way and find out what is the answer so coming to the solution I have just copied down that same table here and we are going to first form the Gantt chart for this so the most important thing in solving this kind of problems related to scheduling is forming the Gantt chart so if you are able to form the Gantt chart correctly

you can easily solve any problems related to this so first of all let's see how we can form the Gantt chart and keep in mind that this is a priority pre-emptive scheduling it is preemptive so when a process of higher priority arrives then if the priority of that process is higher than that of the currently executing process then the currently executing process can be preempted or the CPU can be taken away from it so keep this in mind all right so let's see how the Gantt chart for this can be formed so here is a

Gantt chart for this set of processes if they are following a pre-emptive priority scheduling so if we look at this table let's see which is the first process to arrive so we see that p1 arrives at time 0 so p1 is the first process to arrive and what is the priority of p1 it is 2 since p1 is the first process to arrive and since there were no other processes at that time so p1 will be the first one to get the cpu in this case so p1 gets the cpu and begins its execution and

how long will p1 execute it has to execute for 11 milliseconds that is the burst time of p1 so did p1 execute for 11 milliseconds no let's see why that is because the next arrival time that we have is 2 at the second millisecond p4 has arrived so p4 arrives at 2 milliseconds and let's see what is the priority of p4 the priority of p4 is 1 so is the priority of p4 higher than that of the currently executing process which was p1 let's see P once priority was 2 and P Force priority is 1

so always keep in mind that the lesser the value the higher the priority so here p4 is having the lesser value which is 1 that means the priority of p4 is higher than that of p1 so what will happen P 1 will be preempted and p4 will get the CPU so the CPU is taken away from p1 and p4 gets the CPU at 2 milliseconds so how long did p1 execute p1 executed just for 2 milliseconds and the burst time of p1 was 11 milliseconds so if we subtract 2 from 11 p1 has a remaining

of nine milliseconds to execute so p1 will still have to execute for nine milliseconds the next time it will get the CPU so right now p4 got the CPU and it's beginning its execution so let's see before continues its execution and let's see what happens so what is the next arrival time that we have after p4 it is p2 which arrives at 5 milliseconds so p2 arrives at 5 milliseconds and let's check the priority of P 2 it is 0 so 0 is the highest priority that we have so the priority of p2 is higher

than that of before which was currently executing so what will happen p4 would also be preempted and p2 will get the CPU so the CPU is taken away from p4 and p2 gets the CPU for its execution so how long did p4 execute before executed from 2 to 5 milliseconds so that means it completed 3 milliseconds of its execution and what is a total burst time of p4 it is actually 10 milliseconds so from the 10 milliseconds if we subtract this 3 milliseconds which was already executed we have a remaining of 7 milliseconds for p4

so p4 will again have to execute for 7 milliseconds later engine gets the CPU alright so let's see so p2 now got the CPU and it's continuing its execution now if you look at this table after p2 let's see what are the other processes that arrives so after p2 which arrived at 5 milliseconds the next process to arrive is p5 which arrived at nine milliseconds and after that even p3 arrived at the 12th millisecond so this nine and this 12 all fall under this 5 to 33 that means during the execution time of p2 these

two processes p5 and p3 arrived but did they get the CP you know why did they not get the cpu because the priority of p5 is actually 4 which is less than that of p2 and then the priority of p3 is also 3 which is also less than that of p2 so p2 as I told you has zero priority which means the highest priority so no processes will preempt p2 because it is of the highest priority so p2 will actually execute for its total burst time of 28 milliseconds so from the fifth millisecond when p2

got the CPU up 2 or 33 milliseconds 5 plus 28 is 33 so up to the 33 milliseconds p2 uses the CPU for its execution all right now at 33 milliseconds t2 will release the CPU and let's see what are the next processes that we have and who is going to get the CPU next now if we look here let's just cross out P 2 because p2 has completed its execution now in the remaining processes which is the process having the highest priority so we have p1 with a burst time of 9 p3 with a

burst time of 2 and p4 with a burst time of 7 and p5 with a burst time of 16 now the arrival times doesn't matter because they have all arrived and they are all waiting in the ready queue so among these four processes that are present in the ready queue the process with the highest priority will be the next to get the CPU so let's see here we have p1 with a priority of 2 then p3 with priority of three p4 with priority of 1 and p5 with priority of 4 so which is the highest

priority we have 2 3 1 4 so one is the highest priority that we have among these 4 so p4 will be the one to get the CPU now so p4 gets the CPU and it is continuing its execution so how long will p4 execute p4 has to execute for 7 milliseconds because it has already executed 3 milliseconds before and 7 was the remaining time it has so it will execute for 7 milliseconds so p4 continue to execution from 33 plus 7 which is up to the 40th millisecond now before also completes its execution so

let's just cross it out now in the remaining processes that we have which is P 1 P 3 and P 5 who is having the highest priority P 1 is 2 then P 3 is 3 and B 5 is 4 so among 2 3 and 4 the highest priority is of P 1 which is 2 so P 1 will be the next one to get the CPU so P 1 gets the CPU at the 40th millisecond when P 4 releases the CPU and how long will P 1 execute P 1 will execute for nine milliseconds

so 40 plus 9 is 49 so up to the 49 millisecond P 1 executes and after that let's see what are the processes that we have now so P 1 also finishes then the only remaining two processes that we have are P 3 and P 5 so among P 3 and P 5 which is the highest priority P 3 is parity is 3 and P 5 s priority is 4 so the higher priority is that of P 3 which is 3 so P 3 will now get the CPU and it will execute for how long

P 3 will execute only for 2 milliseconds that is the burst time of P 3 so from 49 up to 51 P 3 execute and completes its execution now the only remaining process is P 5 so P 5 will finally get the CPU and P 3 releases it at the 51st millisecond so P 5 gets the CPU and how long will it execute it will execute for 16 milliseconds so P 5 executes from 51 plus 16 that is up to 67 milliseconds so P 5 executes up to the 65 millisecond and at this point all

the processors have completed their execution so this is how we form the Gantt chart for a set of processes that follow up pre-emptive priority scheduling so we saw that whenever a process of higher priority arrives if the executing process is of lower priority than the one that has arrived then the process having the higher priority is given the CPU and the process that was executing currently was preempted so there was a simple rule that we followed and keeping that in mind we have formed this Gantt chart now if we have formed this Gantt chart now

the rest of the things becomes very easy now we have to calculate the waiting time so that is what our question was so how do we calculate the waiting time for a set of processes that we have so here is how we do it waiting time is equal to total waiting time minus number of milliseconds a process executed before - the arrival time so using this formula let's calculate the waiting time for processes P 1 2 P 5 and then see the average waiting time so the waiting time for process P 1 will be the

total waiting time of P 1 what is the total waiting time for P 1 so to see the total waiting time what do you have to do is you have to look at the Gantt chart and see where did P 1 occur the latest so P 1 occurred latest over here this was the last occurrence of P 1 so what is the waiting time for P 1 during its last occurrence it was 40 it caught the CPU at the 14 millisecond so that is a total waiting time of a particular process so for P 1

it is 40 minus the number of milliseconds the process executed before so before executing here did P 1 execute any time before and if yes how long did it execute so if you see in this Gantt chart P 1 executed even here so and how long did it execute for 2 milliseconds so minus 2 and minus the arrival time for that you have to look at this table so the arrival time of P 1 was 0 so we have 40 minus 2 minus 0 which gives us 38 milliseconds so that is the waiting time for

P 1 so similarly for P 2 the waiting time is the total waiting time of P 2 so where is P 2 the last occurrence of P 2 is here P 2 actually occurred only one time so P twos total waiting time was 5 5 milliseconds - a number of milliseconds it executed before so we see that P 2 did not execute before so it is 0 and then the arrival time of P 2 what is arrival time of P 2 it is 5 so 5 minus 0 minus 5 which is 0 milliseconds so we

see that in this table P 2 arrive at the fifth millisecond and since it was of the highest priority among this set of processes it was immediately given the CPU when it arrived and it did not have to wait and it was not preempted by any other processes because it is of the highest priority so that is why the waiting time of P 2 is 0 and what about p3 let's see the total waiting time of p3 so the last occurrence of p3 is over here and the total waiting time is 49 milliseconds 49 and

did p3 execute any time before no so the number of milliseconds the process executed earlier was zero and then the arrival time of p3 for that we see it is stable and see it is 12 so 49 minus zero minus 12 is 37 milliseconds and similarly for p4 what is the total waiting time p4 was here and also here so the last occurrence of p4 is this one so how long did it wait 33 milliseconds minus the number of milliseconds the process executed before so we see that p4 executed for some time even before this

that is here and how much is it it was for 3 milliseconds 2 to 5 3 milliseconds so minus 3 minus the arrival time of p4 what is the arrival time it is 2 so 33 minus 3 minus 2 is 28 milliseconds and in the waiting time for p5 finally how much is it we see that p5 was the last one to get the CPU and it got at the 51st millisecond not anywhere before that so the total waiting time is 51 milliseconds for p5 number of milliseconds it executed before we see that p5 never

executed before so it is 0 and then the arrival time of p5 was nine milliseconds so 51 minus zero minus 9 is 42 milliseconds so we have got the waiting times for this set of five processes now calculation of the average waiting time is very easy so the average waiting time is 38 plus zero plus 37 plus 28 plus 42 divided by the number of processes which is 5 so that gives us 1 45 divided by 5 which is twenty nine milliseconds so this is the answer to our question so let's see if we have

this 29 milliseconds in our options so if we see our question we see that option a is 29 milliseconds so the answer to the question is option A which is 29 milliseconds that we have just calculated so that is how you calculate the average waiting time for a preemptive priority scheduling algorithm and always keep in mind that whenever you are solving this kind of problem the most important thing is to form the Gantt chart so quickly formed a Gantt chart correctly and after that it becomes very easy to solve the problem so I hope this

was clear to you thank you for watching and see you in the next one [Applause] [Music]