Shortest Remaining Time First(SRTF) Scheduling Algorithm with Example | Operating System

topic in society if that is shortest remaining time first CPU should any algorithm or you can say it is SJ with preemption so we have already discussed that non preemption case in the previous video and in this video I'm going to discuss with you the SJ with preemption so how the society offends different from last year what you can say SJ f with preemption is different from SJ with non preemption case C in SJ of basically we pick the JA from the ready prove it is having the smallest boss time we are located the CPU to that process and in non preemption that process will continue its execution till its termination you cannot forcefully remove that process from CPU in between the execution of that process but in case of preemption you can remove that process while it is executing before the termination of that process and what is that condition when you will remove that process from CPU okay that condition is if the newly-arrived process is having shorter bursts time then the remaining first time of the currently running process then you will remove the currently running process and allocate the CPU to the newly-arrived process and the currently running process will wait in the ready queue so say see here you can say whenever a new process arrived there may be preemption of the currently running process you cannot say that there will be preemption of the currently running process see that is not true it is not true that always whenever a new process arrives the currently running process will be preempted no that is not true may or may not be so when it would be preempted if the newly arrived process has shorter bursts time then the remaining burst time of the currently running process then only preemption will be there otherwise the currently running process will continue its execution if the newly arrived process have larger burst time than the remaining burst time of the currently running process fine you will get it better with the help of so I'm going to take the same example we have discussed this example with sjf with non preemption now we'll discuss this case with preemption okay now first of all draw the line chart this would be started from zero fine now check out at zero is there any any process which is in ready queue check out the arrival time of the process yes at zero one process has been arrived at as before now in ready queue we have one process only one process that is before now see if one process is there then you have you do not have any other choice you have to share Doon this process only you have to give CPU to this process although the burst time of this one is six and you can say that my main sure you can see that in shortest your first we we pick the job of having the shortest burst time and the shortest verse time is one and one then why we are picking this process why so because these processes are not in ready queue now they haven't arrived till now only one process we have that is p4 so only one process you have you have only one choice you have to share dude p4 right it is not like that p4 will continue its execution till 6:00 till its termination that is the case in SJ with non preemption but here in preemption what you will do you will check out after every unit of time see from 0 to 1 now at 1 you check out has any other process arrived at 1 we have p4 that is currently running now fine and after 1 see the p4 has been executed from 0 to 1 that is one unit of time now remaining time for p4 is 5 6 minus 1 that is 5 now check out at 1 is there a and has any other process arrived at 1 yes one process that is p2 now we have p2 also now available processes are p2 and p4 is currently running not checkout newly arrived processes p2 not check out the first time of P 2 that is 5 and the remaining time of p 4s fine which one is smaller both are same if both are same there is a tie then to break the tie viewers first come first so so firstly p4 has come after that p2 comes hope will continue with p4 on okay will not do the context switching again after one unit of time at two we would check has any other process arrived at two now a time poopy one has arrived and p5 has been arrived now as well as you have to update this time this remaining time also now p4 has been executed one more unit of time so remaining time is now for pi minus 1 that is for now out of the available resources or sorry out of the relevant processes find out which one is having the shortest burst time see we don't have this p3 because it will come at time 4 so out of 1 5 updated is 4 & 3 which one is which one is the shortest that is we have 1 so will allocate cpu to p1 for 1 unit of time only and this will require only one unit of time so this has been terminated now this has been done okay now check out at 3 has any idea has any other process arrived at 3 no because it will arrive at 4 only okay now p1 compete in p1 has been completed so remaining is p2 p4 and p5 p2 p4 and p5 so out of these 3 check out which one is minimum 5 4 and 3 3 is minimum so we'll pick this process p5 for one unit of time only 3 to 4 will check okay and now for at you'll check has any other process arrived at 4 yes p3 has been arrived and as well as you will update the time the remaining bursts time of the currently running process so after one unit of execution remaining time is 3 minus 1 that is 2 now we have P 4 P 2 P 5 and P 3 now out of these 4 see this has been done out of 5 1 4 n 2 which one is having minimum first time that is this one p3 this one is p3 and for one unit of time and it will require only one unit to complete its execution so p3 has been done p3 has been done now remaining is only three process now you have reached a point where all the processes see we have only five processes and all the processes has been arrived in ready queue now this algorithm will act as simple sjf algorithm okay you will not again and again check for in after one unit of time and then is there any other process arrived or not now after every process has been arrived in the ready queue from that point of time the society F will work as SJ f money fine let's make yogurt okay you will pick from all the available waiting processes you will pick the process which is having the shortest remaining time first you will allocate that process you will allocate the cpu to that process and continue that process will continue its execution till its termination okay now see now at five we are done with this p3 now remaining is p2 p4 and p5 out of these three which one is having shortest bus time this one is having that is two so this would be allocated to p5 for two unit of time no need to check for C no need to check for the 5 to 6 and then 6 to 7 you can check if you want but if all the processes has been arrived in the ready queue after that just follow the same process as in SJ of with non preemption case so it would require 2 unit of time so 5 plus 2 is 7 now this one is also done p5 remaining is now p4 and p2 p4 and p2 v + 4 which one is minimum that is P 4 P 4 having 4 unit of time 7 plus 4 is 11 in law one is p2 5 in a row time that is 16 say why we haven't checked here after each unit of time like this only we have checked here after each unit of time see here the main fund is if newly arrived process is having shorter bursts time then the remaining time of the currently running process then only preemption would be done but once all the processes has been arrived then there is no chance that any new process will arrive so no need to check after each after every amount of time see any other processor I do not any other processor I've ever known because you know all the processes has been arrived so no need to check after the arrival of all the processes I will check for each unit of time till all the processes arrives in the ready queue now see here also at last we have 16 and this would be same as the total burst time 5 plus 1 plus 1 plus 6 plus 3 that is 16 only and in previous case also we have got here 16 so this would be see the change would be only in the location of these processes the order of allocation of these processes now I will find out the completion time check out at what time p1 has been completed p1 has been completed see here we have p1 after that we don't have p1 so completion time of p1 is this 3 at three p1 has been completed right see you will not take this one because this is the starting time of p1 at 2 CPU has been allocated to p1 and this is the finishing time of p1 ok to the right of this p1 for p2 p2 it's 16 for p3 check out where is p3 here is p3 after that we don't have p3 so completion time is 5 for p4 see now you cannot say here we have p4 so you can write here - no company this is the completion time of p2y so because after waiting of some unit of time CP was allocated to p4 again fine so this is the waiting time so here you can say you cannot say this is the completion time check out here and after that there is no p4 so this is the completion time of people that does 11 okay now for p5 check out this is p5 yes now p5 here we have Wi-Fi from 3 to 4 so do not write for this is the completion time because here also we have p5 again CP was allocated to p5 here after that no p5 so 7 would be the completion time of p5 now what is turnaround time turnaround time would be word completion time - arrival time completion time 3 arrival time - 116 - 115 5 - 4 1 11 - 0 11 7 - 2 that is 5 next is waiting time would be done wrong time - boss time 1 minus 1 I hope you know the formula 5 minus 15 minus 10 is sorry 10 15 minus 5 is 10 1 minus 1 is 0 11 minus C 11 minus 6 we will take the original burst time not the updated 1 11 minus 6 is 5 5 minus 3 is 2 now find out the response time the time at which CPU was first floated to that process after the arrival of the process for p1 when the CPU was allocated first time to p1 here at time 2 and arrival of the p2 is also - the response time is C and when as when the process come then only PCP was allocated to that process so p1 didn't wait not for a single unit of time 2 minus 2 that is 0 response time I take use Co CPU millia at the Hugh's corresponds Millia from the CPU now what about p2 here we have p2 first time CP was allocated at time 11 check out the arrival time of this one that is 111 minus 1 that is 10 so p2 after arrival p2 has to wait for any unit of time ok and after 10 unit of time CP was allocated to p2 for the first time P 3 P 3 the here is P 3 that is 4 and arrival time is 4 4 - 4 0 4 p 4 C first time CP was allocated to 0 will not take this 7 because this is the second time CPUs are located 2p for first time you have to check first time at 0 CP was allocated to P for arrival time is also 0 0 - 0 0 P 5 first time at 3 CPUs are located 3 - arrival time is 2 3 - 2 that is 1 so here we cannot say that waiting time and response time would be same in the case of non-preemptive algorithm response time and waiting time would always be same but in case of pre-emptive algorithm this would not be same here you can see the difference here 5 here we have 0 here we have two here here 1 now you can find out the average waiting time of this algorithm so the average waiting time for this algorithm will would be 3 point 4 and this SI TF would give you the minimal average waiting time now what this minimal means for this numerical on this numerical you apply any algorithm maybe you you you device you develop your new algorithm after some modification and you apply that algorithm on this numerical but you will never get the average waiting time less than 3 point 4 so this that is why it is known as the optimal solution this will give you the minimal average waiting time so one more example I will discuss on this SR TF only till then take care bye bye

Channel: Jenny's lectures CS/IT NET&JRF

Views: 205,280

Rating: 4.8916564 out of 5

Keywords: preemptive scheduling, cpu scheduling algorithms, process scheduling, scheduling algorithms in os, turnaround time in os, sjf scheduling program in c, operating system notes, GATE computer science preparation, ugc net computer science study material, net computer science, ugc net syllabus, ravindrababu ravula, jenny's lectures, srtf scheduling algorithm, shortest remaining time first, sjf with preemption, fcfs scheduling algorithm, nonpreemptive scheduling

Id: _QcX99B-zbU

Length: 15min 15sec (915 seconds)

Published: Sat Mar 23 2019