in this lecture we'll be discussing a salt problem on the shortest job for scheduling in the previous lecture we have already discussed about this algorithm and we have seen how it works and what are its properties so here we'll be seeing a salt problem on this sjf scheduling algorithm and this problem was also asked in gauge 2014 in computer science alright so let's see what is this problem and how we can solve it so here is a problem an operating system uses a shortest remaining time first scheduling algorithm for pre-emptive scheduling of processes consider the following set of processes with their arrival times and births times in milliseconds so what the question says is that an operating system uses the shortest remaining time for scheduling algorithm so we have already seen in the previous lecture that shortest remaining time for scheduling algorithm is another name for this shortest job for scheduling algorithm and it is using a pre-emptive type of scheduling for the processes and then the arrival times and burst times are given in milliseconds as shown in this table so we have four processes P 1 2 P 4 and arrival times are given here in milliseconds and the burst times are given here in milliseconds now the question is the average waiting time in milliseconds of the processes is blank so we are supposed to find out what is the average waiting time of this processes and we have four options a 4.5 B 5.0 C 5.5 and D 6.5 so let's see how we can solve this and how we can find the average waiting time for these four processes if they are using shortest remaining time first scheduling algorithm for pre-emptive scheduling of processes so remember it is pre-emptive that means when a process is using the CPU if other processes of shorter time comes then that process will be preempted means a process that was using the CPU can be preempted the CPU can be taken away from it and given to the process that has the shorter remaining time all right now let us solve this problem I have just copied down the above table here so that it fits on the screen is the same table so in order to solve the problem we have to find the waiting times for each of these processes one by one and after that we have to calculate the average waiting times so for that what we have to do is we have to first form the Gantt chart for this set of four processes so let us see how can we plot the Gantt chart for this set of four processes so here is a Gantt chart for this set of four processes P 1 2 P 4 so if we look at this table we see that the first process to arrive was process P 1 at time 0 so process P 1 arrived at time is 0 and then since it was a first process to arrive and since there were no other processes at that time the CPU was given to process P 1 so here in the Gantt chart we see that at time 0 P 1 arrives and P one gets the CPU at time 0 and begins its execution now if we look at this table we see that at time 2 P 2 has arrived so when P 2 arrives we see that the burst time of P 2 is 4 which is less than that of P 1 which is 12 so P 2 has to be given the CPU so what will happen is P 1 would be preempted that means the CPU will be taken away from P 1 and P 2 will be given the CPU because it has a shorter bursts time as compared to P 1 so at the second millisecond lead to arrives and the CPU is given to P 2 P 1 is taken out so P 2 is now executing and if you look at the table P 3 arrives at time 3 order third millisecond and what is the best time for P 3 it is 6 milliseconds now let's see what was happening in the gunshot P 2 was executing so P 2 started its execution from the second millisecond and at the third millisecond what happened P 2 completed 1 millisecond of its execution so what is the worst time of P 2 it is 4 so at the third millisecond P 2 completed 1 millisecond of its execution so at time 3 P 2 s first time or the remaining time is now 3 milliseconds now P 2 is having 3 milliseconds to be executed and at that time P 3 arrives and the burst time of P 3 is 6 milliseconds which is greater than that of P 2 so P 2 will not be disturbed it will be allowed to continue its execution so it is continuing its execution and up to what up to the sixth millisecond because P twos burst time is 4 milliseconds so 2 plus 4 is 6 so up to the sixth millisecond p2 continues its execution now if we see at the six millisecond p2 releases the CPU so now who is going to get the CPU next is it before no it is not before because the arrival time of p4 itself is 8 milliseconds but we are only at the sixth millisecond right now so what are the other processes that we have now we have p1 and let us see what is the burst time of p1 is it 12 it is not 12 now because p1 already completed 2 milliseconds of its execution so the burst time of p1 is now 10 milliseconds so we have p1 with burst time of 10 milliseconds and p2 has already completed his execution so p2 is not to be considered anymore and we have p3 whose first time is 6 milliseconds so we have p1 and p3 so p1 it is 10 and P 3 is 6 so which is a smaller one it is p3 so p3 will get the CPU at the 6 millisecond here so p3 begins its execution and now let's see what happens so as p3 begins its execution it goes from 6 millisecond to seven millisecond and from seven millisecond to eight millisecond and at that 8 millisecond p4 arrives and the burst time of p4 is 5 milliseconds so will p4 get the CPU if you just look at this table we were think that yuppie 4 should get the CPU because before burst time is 5 which is less than that of P 3 which is 6 but if we closely observe in this table we know that p4 arrived at the 8 millisecond so let us see what is the status of p3 at the 8 millisecond at the 8th millisecond p3 already completed 2 milliseconds of execution from 6 to 7 and 7 to 8 so let us see what is the total bus time of p3 it is 6 millisecond so since it already executed 2 milliseconds 6 minus that 2 will give us 4 milliseconds so at the time 8 when p4 arrives the remaining burst time of p3 is 4 milliseconds which is less than that of p4 that is 5 so Petrie's remaining time is 4 milliseconds which is less than that of the burst time of p4 which is five milliseconds so p3 will not be disturbed p3 will be allowed to continue its execution and it will continue until it finishes so the total bust time of p3 is 6 milliseconds so 6 plus 6 is 12 so up to the 12th millisecond p3 execute now what are the remaining processes that we have let us see so p2 has completed PT also has completed now we have only p4 and p1 now what are the burst times we know that P ones remaining burst time is 10 milliseconds and p4 which has not even got the CPU once its bursts time is 5 milliseconds so if we compare p1 and p4 the smaller one is p4 so p4 is the one going to get the cpu so p4 gets the CPU at 12 millisecond and it will execute for how long for 5 milliseconds so 12 plus 5 is 17 now at the 17 millisecond the last one which is p1 will get the CPU and it will continue execution for 10 milliseconds so 17 plus 10 is 27 so at the 27th millisecond p1 complete its execution and here we have the complete Gantt chart for this set of 4 processes so we have to always keep in mind that this is preemptive and whenever a process arrives we have to closely observe what is the status of the process that is executing currently we have to see it's a remaining burst time not the total burst time but the remaining burst time and depending upon that you have to compare with the process that arrives and whichever is lesser will get the CPU so that is how you form the Gantt chart for a preemptive shortest remaining time first scheduling so how do we calculate the waiting times we have already discussed the formula in the previous lecture so this is the formula the waiting time is the total waiting time minus number of milliseconds a process executed - the arrival time so the waiting time of a process is calculated by seeing the total waiting time which is visible in this Gantt chart and from that we subtract the number of milliseconds of process executed prior to the total waiting time and from there we subtract the arrival time so that will give us the waiting time for a particular so let us calculate that one by one for processes P 1 2 P 4 so here are the waiting times or processes P 1 2 P 4 so for P 1 what is the waiting time the total waiting time of P 1 so let us see where is P 1 P 1 lastly executed over here and what was a total waiting time it was 17 milliseconds so we have 17 minus the number of millisecond the process executed prior to that what is that if you see in this Gantt chart P 1 already executed 2 milliseconds before coming here so minus that number of milliseconds a process executed which is 2 milliseconds - the arrival time of P 1 that is 0 so if you subtract this will get 15 milliseconds which is a waiting time for P 1 and similarly for P 2 what is the total waiting time we see that P 2 is seen only here in the Gantt chart and the total waiting time was 2 milliseconds and the number of milliseconds of crosses executed before that we see that P 2 never executed before that so it is 0 and the arrival time of P 2 that is 2 milliseconds so minus 2 that will give us 2 - 0 - 2 that is 0 milliseconds so if you look in this Gantt chart also we can understand that P 2 arrived at the second millisecond and as soon as it arrived it got the CPU so it did not have to wait so we have 0 then similarly for P 3 what is the total waiting time P 3 got the CPU at the sixth millisecond so the total waiting time for P 3 is 6 milliseconds - the number of millisecond it executed prior to that we don't have P 3 before so that is also 0 and then the arrival time of P 3 that is 3 milliseconds so 6 minus 0 minus 3 is 3 milliseconds and then finally for P 4 if you see what is the total waiting time it is 12 milliseconds so 12 - number of millisecond it executed prior to that we don't have P 4 prior to that so it is 0 and then the arrival time of P 4 is 8 milliseconds so 12 minus 0 minus 8 which gives us 4 milliseconds so here we have calculated the waiting times for processes P 1 2 P 4 now we can easily calculate the average waiting time so the average waiting time is 50 plus zero plus three plus four divided by the total number of processes which is four and that gives us five point five milliseconds so this is the average waiting time for the processes P 1 2 P 4 so we are getting 5.5 milliseconds so let us see if we have 5.5 milliseconds in our option so coming back to the question if we see the options here we have option C which is 5.5 milliseconds so option C is the answer to this question so I hope this was clear to you how we calculate the waiting times for a operating system that uses the shortest remaining time for scheduling for pre-emptive scheduling of processes so thank you for watching and see you in the next one [Applause] [Music]