L-2.7: Round Robin(RR) CPU Scheduling Algorithm with Example - YouTube

Hello friends, Welcome to Gate Smashers

Let's solve a question on round robin CPU scheduling

So in the question we have given 4 processes Arrival time and burst time is given

The criteria of round robin scheduling is Time quantum let's see first what does Time quantum means

When processes are in ready queue

Means first we bring all the processes in ready queue in the RAM, ready queue lies in the RAM

From there we selects a process and takes it in the running queue

Running queue means... CPU

Means we selects a process and gives to CPU to execute it

In non preemptive case,

when we give a process in running state then it'll get execute completely

But in Round robin, here CPU uses time quantum Time quantum means...

Let's say time quantum is 2... Then CPU will run this P1 process up to two times

Means CPU doesn't care about its burst time It'll just run it up to 2 time unit

and after 2 time unit, that process will go back in ready queue

then we'll bring a different process in the running state and will run that process also up to 2 time quantum

And then will take it back to ready queue if there's still it's burst time left

Means if a process have burst time 2 only then it'll get complete

It'll obviously get complete in that 2 time quantum or even in 1

But if burst time is more than 2 then obviously some of its portion is complete then we sent it back in the ready queue

So ready queue's sequence is the main important thing here

That how processes are coming in ready queue and how they are getting pre-empt and going back to ready queue

which we call context switching... that I'll explain here

So most important thing you have to keep in mind is sequence

Sequence of processes in ready queue

So to bring the sequence properly in the ready queue We placed a ready queue separately here

Until now we used to keep a running queue in all questions, which we call Gantt chart also

We used to maintain that running queue

But in round robin, you can maintain 2 queue because it's very important to maintain 2 queue

It'll be clear to you that why you have to make a separate ready queue

So let's solve this question and mode is pre-emptive and round robin can never be pre-emptive

Because after every given time quantum CPU will get switch

then after second time quantum CPU will switch again

so the CPU keeps switching between the processes

So here at time 0... which processor is ready

Ready means... obviously if it's ready then it came in RAM

Now we'll pick that process from the RAM and will give it to CPU

So we checked which process is ready up to 0 time

At 0, only one process is ready i.e. p1 Then placed it in ready queue first

If there's any other processes ready also then place them in ready queue first

And you have to place them according to their arrival time

Now in this portion only one process came at 0 i.e. P1 and we placed it

Now, extract P1 from here and place in running queue

Obviously our aim is to execute it so for that I have to bring it i running queue

But up to how much time you have to run? For that you have given time quantum i.e. 2

So we'll run P1 from 0 to 2

If we ran P1 from 0 to 2 then burst time of reduced from 5 to 3

Now first check if P1 got completed? NO, P1 is not completed yet

Now we are at point 2, because this is showing time here, and I reached at time 2

So check which processes are ready at 2, we saw at 2, P2 & P3 are both ready

P2 is ready at 1 and P3 is ready at 2 so both of these processes got ready

So first place both these processes in the ready queue sequence wise according to their arrival time

So according to arrival time P2 came first, so we placed P2 first

then P3 came and we placed it also

Meanwhile what's going on in the running state We ran P1 from 0 to 2

Now after 2 CPU will say, Take P1 out of the running state, preempt it and bring another process

Now we call it here context switching Right now, context switching is happening here

Context switching means...

Save the running process and bring the new one

Saving the context of running process means... Context means PCB, process control block

PCB contains all the information of that process

So I have to save the context of the process that we were running here

Because when that process will come again in future, then I don't have to run it again from 0

I've to resume it not restart

There'll be advantage only if we'll resume it If we'll restart then the work we did here will be waste

So for this we should save the context of this process and bring a new process here

We'll bring P2 here and here you have to check that this P1 ran from 0 to 2 but 3 is still left

Because 3 is still left then when P1 will go in ready queue then it'll come behind P1

First reason is when context switching was going on here then we are saving P1's values fast

And at that time P2 and P3 came in ready queue

And other reason is if we'll write P1 here

then P1 was running continuously, where was context switching??

P1 is again running after P1 like that

So this is the case of CPU scheduling round robin That it'll switch to some other process after 2 time unit

But for that we placed P2 & P3 first, if P1 is still left then we added it in the last

Now we took out P2 from here and inserted here

And for how much time we'll run it? Again time quantum is 2 then we'll run up to 2

The moment we ran up to 2, then this value became two

This 2 is still left right?... Yess

First check which processes are ready at 4, this was already in ready

P4 also got ready, so P4 got ready then first of all place P4 in the ready queue

First place the processes, then you have to check if P2 is left

Yess, P2 is still left 2

So now place P2 in ready queue after it because here when we are saving context of P2

At the same time P4 already came in the ready queue

And we saved P2's context and successfully sent it in the ready queue

So that we can bring some new process i.e. P3 So we brought P3 here for two time quantum

So we brought P3 here for 2 time quantum Means the value became 6, so I ran it here

But if you'll see here then P3 got complete

It's burst time was 2 and we ran it Up to 2 and it got completed

Now check at 6 if there's any new process ready

All the process already came in ready queue There's no any new ready process

If there'd be any new process then we'll place it in ready queue

but all processes are in ready queue already

Then we have to check if P3 is still left

If P3 is still left, then we'd add it here but P3 is already completed

So P3 is already done terminated So we can remove P3 from here

Now you just have to move it forward simply Take out P1 from here

When we executed P1 for 2 time quantum Means from 6 to 8

And we reduced the burst time also So time reduced from 3 to 1

Now first you have to check if some new process came on 8

No new process came because all 4 processes have already been in the ready queue

What else we have to check is, if P1 is still left Yess, P1 is still left 8 times... So we'll place P1 in the read queue

First you have to check... if there came any new process at the current point

If there arrived some new process then bring it first, then in 2nd step you have to check if P1 is still left

So no new process came there, but P1 is still remaining so we placed P1 here

Next P4... You have to take out from here 1 by 1

we took out P4 from here and placed in ready queue for 2 time quantum

But if you'll see that P4 need only one time then why would you run up to 2

We ran from 8 to 9, P4 got executed and got terminated

So in this case you don't have to run from 8 to 10 Many students can do mistake her

that if we'd run 8 to 9 then 9 to 10 then what will happen in 9 to 10... It'll stay idle

But you don;t have to keep CPU Idle, so that's why run it up to 1 time only

and at 9 you can bring some new process

Because P4 left already, P4 is not there if it'll be left then we'll add it here

So next process is P2, we took out P2 from here and bought here for 2 time...

so it became 11 and P2 completed here

After a certain time round robins gets very easy

it just gives little bit problem in staring in maintaining ready queue, after that round robin gets normal

When all process came in ready queue once then it'll be very easy for you

Now check if P2 is still left... No it's over so there's no need to put anything in end

Then we have P1, we ran P up to 11 because it has just one type left

We made it 0 also after running up to 12 Means all process got completed at 12

This is why the ready queue is very important

otherwise if this sequence got even bit changed then your question will get wrong

And you can't remember this sequence in mind without making ready queue

That's why it's very important to make this sequence

Just keep picking up from this sequence and placing them here

Where P1 got completed?... Check in the last

Now there's no use of ready queue, now we'll check running queue only

P1 is written in the last here i.e. 12 So 12 is its completion time

Check where is P2 written in the last.... It's here, 11

Where's P3 written in the last... Here it's 6 And P4 in last here, it's 9... so completion time will be this

Turn around time = completion time - arrival time So simply... 12... 10.... 4.... 5

And waiting time = turn around time - burst time Burst time which was original & given in starting

Don't do mistake here... 12-5 = 7 10 - 4 = 6...... 4 - 2 = 2...... 5 - 1 = 4

So this is the waiting time... This is the waiting time here

We used waiting time here and along with that if you want to calculate avg. waiting time or turnaround time

then you can total it and divide by no. of processes

Let's calculate response time here first... RT = CPU first time - AT

So when did P1 got CPU first time? How to check it?

Where's P1 written first time in Gantt chart... It's here It got CPU at 0 and it arrived at 0 also

So 0 - 0 = 0... Simple

Now check P2... P2 is written first time here In it's left in the substrate below it's two

It came at 1... So 2 - 1 = 1

So when P3 got first time... At 4 So 4 - 2 = 2

And P4 is written first time here It got CPU at 8, and it arrived at 4

So 8 - 4 = 4,

So this is how we have to calculate the turnaround time, waiting time and response time

If they would ask average, then you can total it divide by number of processes

That's important... but other that there's one more thing important here i.e. Context switches

Means many times they ask how many times context switching happened

So context switching means...

saving the running process, sending it back and loading the new process

So check how many times you did it? You did it in starting?... NO

In starting we bought new process, didn't load the old one

But at this point we did... At this point we saved P1, and called P2

At this point we saved P2, and called P3

At this point we saved P3, and called P1

At this point we saved P1, and called P4

Means all these are your context switches Means 1... 2... 3... 4.. 5... 6..

Neither you have to calculate first one nor you have to calculate the last one... Because in last also you saved P1

But didn't called any new process, so we don't have to calculate the first and last line

Just count the lines in between, that will become the number of context switches

So this is all about the round robin process scheduling

Thank You!