Round Robin(RR) CPU Scheduling Algorithm in OS with example

the topic is round-robin scheduling algorithm so we'll discuss first of all the theory about this two or three points important points and then we'll discuss this with the help of one numerical see this type of scheduling algorithm is used in multitasking operating system or you can say time sharing operating system we have discussed many types of operating systems the there in the that video we have discussed what is multitasking operating system see let us take an example when you are working on your laptop then at same time you're you know maybe listening songs and the same time they are surfing on internet and as well as some background processes are also running at the same time so many processes are running and it seems that all the processes are running parallel but it is not true it is based on that time quantum every process the operating system will allocate some unit of time to each process maybe 2 millisecond ok maybe for 2 millisecond the CPU will be allocated to that your process which is running your Windows Media Player and another 2 for 2 unit or for 2 unit of time or 2 millisecond some background processes running may be that maintaining the system clock of your laptop something like this ok and this is the switching between these processes see and this switching is so fast that it looks like that all the processes are running parallel xr4 sorry processor inori but i sending you there that is not actually true this is what the multitasking operating system or you can say time sharing operating system so in those kind of operating system this for sure dueling the processes which kind of scheduling algorithm is use that is a round-robin scheduling algorithm ok so this algorithm is similar to first-come first-serve but with some time quantum one extra thing is what with some time quantum and this algorithm is what the mode of this algorithm is what it is always pre-emptive scheduling algorithm okay now what is this time quantum you can say time quantum is the time or the period of time for which a process is allowed to run uninterrupted in a pre-emptive multitasking operating system in one go okay in this case it is not like that we pick one process based may be based on some may be the criteria of arrival time or burst time and will complete that process and after that another process will be pegged and completed sex equation it's not like that we pick one process the criteria is what the time quantum plus arrival time also okay arrival time plus time quantum the criteria fine we'll pick one process which has been arrived in the ready queue will control the CPU da locator to that process that process will continue its execution till the time quantum expires maybe it's too unit of time three unit of time four unit of time okay for that time quantum that process will continue its execution and after that if that process has been completed then it's fine it will go to the terminated state terminated state but still after the expire of the time quantum still it needs some time to complete it its execution then again that process will go to the ready queue and another process will be picked and CPU would be elevated to that process okay so this would be done in a in a round robin fashion or you can say circular fashion so in this case we will also maintain one ready queue and then we will draw the Gantt chart right so main advantage of this algorithm is what it would give you the deterministic response time to each process or you can say in case of the average response time it is one of the best algorithm now let us take this example we are given five processes arrival time of these five processes and this is the burst time of these processes we are just considering the CPU bound processes none of the process will go for any i/o device doing its execution okay see now we will also maintain a ready queue if you will maintain our ready queue also in this case along with the Gantt chart then there will very less chance that you will get it you will get the answer wrong okay so I highly recommend you to maintain already q in this case in town dropping by solving the numerical zone round-robin scheduling okay now the Gantt chart would be started I assume that would be started from the time so along with this Gantt chart will maintain a ready queue also fine so at first in the ready queue see the criteria is what arrival time arrival time plus time quantum it's not like check out the time quantum only and just draw the game shot you have to check that I will time also now suppose in this case the arrival time known you can see the time quantum or time slice which is given is that is three unit of time so here time quantum given is three unit of time and arrival time is given this one now at first at 0 p1 has arrived in ready queue now suppose in ready queue we have p1 okay at time 0 now only one process is there at time 0 in ready queue will delete this process from ready queue and this would be CP would be located to this process for how much unit of time now the criteria is arrival time we have checked plus time quantum l toy time point ms 3 unit of time so in a locate the cpu to p1 for only 3 unit of time also take the burst time of this process the total burst time of P 1 is 5 still this process require 5 unit of time to complete its execution fine because CPUs are located for only 3 unit of time ok now at 3 this P 1 would be removed from the CPU and again go to the ready queue but before putting this p1 again to the ready queue you have to check maybe there would be another process their processes which have been arrived so fine while this p1 was running so check out the rival time of another processes see arrival time of p2 is 5 so this one is not there in ready queue now arrival time of p3 is 1 so while p1 was running so sometime at 1 p3 has arrived so p3 is now in ready queue now this would come at 6 and this would come at 8 so before 3 only one process has arrived and went into the predicate now at 3 P 1 would be removed from the CPU and again P 1 will go to ready now check out the ready queue next processes p3 will remove the process p3 and allocate CPU to p3 for how many unit of time check out the time for no.43 unit of time now it's not like that after p1 p2 is there so we'll write p2 here you have to check out arrival time also maybe sometimes they can give you they will not always give you the time arrival time any increasing order like 0 1 2 3 4 5 4 0 5 6 7 8 something like this maybe the arrival time of p2 is C 5 and P 3 is 1 so P 3 will come before p2 this is this an example ok now see P 3 P 3 will require 7 unit of time but we can allocate CPU to p3 for only 3 unit of time in one go after that you can remove this process forcefully because the version is what pre-emptive version so 3 4 3 4 3 note of time that is 6 so the remaining burst time of this one is 7 minus 3 that is 4 p 3 still needs 4 unit of time for completing for completing its execution now update the ready queue also now it's not like that at 6 we'll remove the speed 3 and we put the p3 in ready queue maybe before this p3 while p3 was running maybe another process would have come in the ready queue so check out that also before 6:00 see ya at 5:00 people came at 5:00 now see at 6:00 p4 came and at 6:00 this would be preempted so say this maybe you can have you can say that first of all you'll write P 3 and then we'll write P 4 well another option is first write P 4 then write P 3 because time is same at 6 new process game and then 6 also we preempted this process from the cpu so the funda is what if this kind of situation is there then we'll always put the newly-arrived process in the ready queue first this is the condition fine so we'll put P 4 here and then we'll preempt this P 3 and again this P 3 would be in the predicate this process will commit it so this is not in the ready queue now now next P 1 will be removed from ready queue and CP would be allocated to P 1 P 1 would need 5 minute of time but we can allocate CPU for 3 unit of time so 6 plus 3 is 9 and the remaining is what to the net of time right now at 9 P 1 will go and again we'll be there in the ready queue but before putting this P 1 in this ready queue we will check is there any process who has come while the Steven was running yes we have one process while the time was 8p v came in the ready queue and now P 1 will go and P 1 will be in the ready queue now next is P 2 in the ready queue will delete P 2 and CPU would be located to P 2 check out the burst time for P 2 is 3 sorry - so we cannot say that 9 + 3 we will allocate this CPU for 3 unit of time 9 plus 3 is 12 you have to check also the first time p2 will require only that's 2 unit of time so we'll allocate CPU to p2 for 2 unit of time ok then now p2 s then will not put p2 again in the ready queue because Peter is done with its execution and it's now culminated now next is will run this p4 for how many unit of time for 3 unit of time because time quantum is 3 as well as check the both time CP 4 would need only 3 unit of time for completing its execution ok so 11 plus 3 is 14 now p4 will not go back to the ready queue why so because p4 has completed beaver before got completed because it required only 3 unit of time for its execution ok now next process is p3 not J the burst time for p3 is still it need 4 unit of time but we can allocate CPU for only 3 unit of time because time quantum is 340 in plus 3 is 17 still it will need one more unit of time for completing its execution now it will go back to the ready queue because it is still left with 1 unit of time ok p3 will go back to the ready queue now while p3 was running we didn't check any process has come to the ready queue why so because all the processes all the processors have come till the time it ok so no process will come now now PCL are going again back to the ready queue no next processes p5 delete this p5 if allocate CPU to this p5 the required burst time is 5 so 4 3 unit of time will execute this and then when again put this 2 into 2 and again put the p5 into ready through 17 plus 3 is 20 now p5 will again back to ready queue now next is p1 now the remaining time of p1 is what only 2 unit of time will require so we'll continue will run the speed 404 only to you need to frame 20 tell 22 now p1 is also done now next is p3 now p3 would require only one unit of time okay now we'll run this p3 for only one unit of time 22 + 2 + 123 now p3 is also done and the remaining is p5 so p5 see now you have to update this burst time also p-51 CP was allocated to P 5 4 3 unit of time so remaining time was 2 and now it will it need only 2 unit of time that is why I will run this for - you need to find 23 + 2 is 25 so no process is there in the ready queue now ready queue is empty so we'll stop this round-robin algorithm so this is what the gain chart of round-robin algorithm now you have to find out the average waiting time tongue wrong time and response time also now the completion time for each process is what check out for p1 for completion time you can check out from the right side of the Gantt chart see at last we have a p1 here only so to the right size check out the time to the right of this p1 that is 20 to completion time of p1 is 22 now for p2 here we have P 2 that is 11 for p3 here we have p3 that is 23 completion time for p4 here we have P for completion time is 14 for p5 it's 25 now what is the turnaround time turn around I would be what completion time - arrival time completion time 22 arrival time 0 20 2-0 11 - 5 6 23 - 120 240 minus 6 that is 825 minus 8 that is 17 now next is waiting time now waiting time would be what turnaround time - births time turnaround time is 22 - births time see births time will not check the updated births time you have to take you have to check the the total burst I'm the original burst time which was given in the question that was 8 so 22 - and that would be 14 6 - 2 for 22 minus 7 that would be 15 8 minus 3 that is 5 + 17 minus 5 that is 12 now response time would be check out for p1 at what time cpus are located first time to p1 after the arrival at a 0 only an arrival time is 0 0 - 0 0 p2 c at 9 cpu was allocated to p2 so we cannot say nine - minus zero and that is nine you have to check out arrival time of that process also arrival time of p2 is what five so nine minus five right that is four for p3 the first time CP was allocated at time three arrival time of P 3 is 1 3 minus 1 that is 2 for P for first time CPUs are located at time 11 arrival time is 6 11 minus 6 that is 5 for p5 first time at 17 CP was allocated to p5 17 minus arrival time is 8 so that would be 9 and if you want to calculate the average then do the total of days and divide by the number of processes that is 5 so the answer would be so I guess the average turnaround turnaround time would be 15 average waiting time would be 10 and average the response time would be 4 so if I talk about the advantages and drawbacks of this round draw my algorithm so in advantages you can write that it would give the deterministic response time but you can say in case of the average response time it is one of the best algorithm okay in case of response time but drawback is what we cannot say it is better than FCFS see when the case is if time quantum is very large suppose time quantum in Kees is 10 then in that case this algorithm round-robin will work as first-come first so same as first-come first-serve you can apply this round-robin taking the time quantum 3 on this numerical and then you will solve you solve this numerically the first confessor you will get the same answer same turnaround time and waiting time and response time so if you say that we take the time quantum very small we say that would take it 1 so that response time would be increased so you you can say that more and more processes would get the CPU very soon if time quantum is 1 but in that case tropic is what number of context switching would be increased because when pure the CP would be allocated to p1 suppose time quantum is 1 for one unit of time then again p1 will go to the ready queue so this is known as context switching so here you can say context switch one context switch like this so if time quantum is very less then this number of context switching would be increased and number of context switches will also take some time well also you know in the context switching means what you have to store the you have to store the current position of this currently running process and load the you know status of the next process so this will also take some time and in that case average waiting time but also increased so we cannot take very large time quantum and we cannot take very less time quantum but yeah advantage is that it gives you the deterministic response time so somewhere it is written as that idle time quantum is between 10 200 milliseconds it should not be greater than 100 it should not be less than 10 milliseconds note seconds right so I'll see in the next video till then bye bye take care you

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

Views: 263,818

Rating: 4.8760695 out of 5

Keywords: schedule, process scheduling, scheduling algorithms, preemptive scheduling, round robin scheduling program in c, cpu scheduling algorithms, round robin scheduling, scheduling algorithms in os, round robin scheduling example, GATE computer science study material, operating system notes, ugc net computer science preparation, NTA UGC NET june 2019, ugc net syllabus, ravindrababu ravula, jenny's lectures, time quantum, RR scheduling, non preemptive scheduling

Id: -jFGYDfWkXI

Length: 19min 46sec (1186 seconds)

Published: Tue Apr 23 2019