馃攳
L-2.4: Shortest Job First(SJF) Scheduling Algorithm with Example | Operating System - YouTube
Channel: Gate Smashers
[0]
Hello Friends, Welcome to Gate Smashers
[1]
Let's understand the concept of shortest
job first scheduling algorithm with a numerical
[7]
So in the numerical first we have given here
Four processes P1, P2, P3, P4
[12]
Their arrival time and burst time is given
It'll be given to you in almost all numerical
[17]
What we need to find is completion time,
turnaround time, waiting time and response time
[24]
So we have the algorithm here shortest job first
In shortest job first we have the criteria of burst time
[30]
Means we checks the burst time
[33]
Shortest job means a process whose burst time
will be lower, we'll select that process
[41]
Means we'll run that process first on the CPU
[45]
And the mode is non pre-emptive
[47]
Non pre-emptive means if we gave
one process to CPU to execute
[53]
then that whole process will get
executed without any interruption
[57]
Now let's start with the help of Gantt chart
because it'll make the process very easy
[63]
Time will start from zero always
So let's start with zero
[68]
So at zero, which process has arrived already
[72]
Now first you have to check if
there's any process arrived at zero
[77]
There's no process that has arrived at zero
You can get this type of numerical also in exams
[83]
So no problem, from zero to one
you can simply make it idle
[88]
Idle means CPU is idle from 0 to 1 limit of time
[94]
Alright if there's no process
then obviously CPU will be idle
[98]
Now at time 1, now we are at time 1
Now we are at time 1
[104]
Check at 1 first of all that which process has arrived
[107]
We'll check burst time criteria later,
[110]
first we have to find out which process arrived already
[114]
So I checked at 1,
then P1 and P3 arrived at 1
[120]
Means P1 and P3 both arrived at 1
Now should we pick P1 or P3
[126]
so for that I have to use the criteria i.e. Burst time
[133]
So first we checked Burst time of P1
P3's burst time checked 2
[139]
So which one is shortest out of two
That's 2,... Then we'll select P3 first
[145]
Because its burst time is lower
[148]
So now, Mode... Mode means non pre-emptive
Means it has to execute it completely
[153]
Executing completely means...
Its execution time is two,
[158]
So we executed it up to two times
Two means, we are at one and it'll take two more
[165]
I'll take 2 unit of time more
So 1+2... that'll become 3
[169]
So at 3, P3 got executed completely
Now we are at Time 3
[178]
So at time 3 first we have to check
that which process has arrived already
[183]
P1 has already arrived, P1 arrived at 1
but haven't executed yet, so we'll keep P1 here for now
[190]
Other than P1, which process has arrived at 3
[194]
If we'll check at 3, then yess P2
P2 has arrived at 2
[198]
So you can simply write here that yes,
P3 and P1 are already present in the ready queue
[204]
Now if these two processes are in ready queue,
[206]
then which one to select,
then we'll select it using burst time
[211]
Means first check the arrive
that which process has arrived
[216]
If only one has arrived
then there's no logic of burst time
[219]
We have to run that process only
[221]
But if too much process came
and arrived at that time
[225]
Then we have to use burst time
[227]
So in this case we have got P1 and P3
so let's check burst time first
[231]
P1's burst time is 3 and P2's burst time is....
[235]
Sorry it'll be P2 here
[240]
P2 came on 2 that's why P2... P3 already got
executed, so you can remove it now
[245]
Let's check P1 and P2's burst time
P1's burst time is 3
[248]
And P2's burst time is 4
Then P1's burst time is less out of two
[253]
So we'll get P1 executed for 3 unit of time
[257]
So 3 means, until 3+3 = 6 unit of time
P1 will get executed
[263]
Means now you can remove it also from here,
Because both of these got passed already
[267]
Now P1 gone already so I've P2 left now
[272]
But, check time first... It's 6
Now check which process has arrived at 6
[277]
P4 came now, because
it was supposed to come at 4
[281]
So it means P4 came to this point somewhere
[284]
So I can say there are two processes
in the ready queue i.e. P2 and P4
[290]
Now which process to select out of these two
Again we'll use criteria of burst time
[296]
So check burst time of P2... It's 4
And for P4... It's 4
[302]
Means Both of their burst time is same
[304]
Now I've created this type
of question in intentionally
[307]
so that we can cover
as much variations as possible
[310]
In this case, when P2 & P4's burst time is same
then which one to select
[316]
Because both of their burst time is same
[318]
So no problem whenever
you get conflict like this
[321]
then come a step back,
means check their arrival time
[325]
Check which one has lower arrival time
Means which one came first
[332]
Then you'll find out that P2 came first
[335]
Then which one to select
out of these two?... P2
[338]
Although burst time is same, but why are
we selecting P2, because of arrival time
[345]
In case, arrival time would be also same
[347]
Just as an example if we would assume
that arrival time is also same
[352]
So in that case you can simply come to process ID,
[355]
the one with lower process ID, you can simply select it
[359]
So in this case we are selecting P2 first and
we have to run P2 up to four Unit of time
[365]
6+4 i.e. 10
[369]
So we ran P2 up to 10 times, now after that
there's no problem because only P4 is left
[374]
So we selected P4 and
it also needs 4 unit of time
[379]
So 4 unit of time means 10 +4 i.e. 14
so P4 will be completed on at 14
[386]
Now write the completion time first of all
when P1 got completed?
[390]
Check on the right hand side of P1
in Gantt chart... It's 6, so It got completed on 6
[396]
P2 completed at 10
[398]
Now check P3... P3 completed at 3
[401]
Now we checked P4 and
it got completed at 14
[404]
So this is how we can
calculate the completion time
[407]
When completion time arrived, then
for TAT and WT just use the simple formula
[413]
Completion time - arrival time
i.e. turn around time
[416]
So its value will be 5... 10-2 = 8
3-1 = 2... 14-4 = 10
[426]
Now for waiting time... Turn around time - burst time
[431]
So turn around time is 5, burst time is 3
So it comes out to be 2
[436]
8-4 = 4.... 2-2 = 0..... 10-4 = 6
[442]
So this is the waiting time
[445]
Response time....
[446]
You don't need to find response time in case
of non pre-emptive because it'll be equal to waiting time
[453]
In case if they asked you,
then simply how we select response time?
[458]
The time at which a process gets the CPU first time
[463]
For example... When P3 got the CPU first time
At one... you can check the left side
[469]
And P3 came at one also
So 1-1 = 0
[476]
Means you don't have to do it
because it'll come equal to waiting time
[480]
But in case if they asks you
then you can calculate like this
[484]
Why it is not coming in it?... Response time
will come in case of pre-emptive only
[488]
because when a process gets CPU,
[491]
no matter at what time,
then that process will get completely executed
[495]
Then there's no chance of
getting the CPU 2nd or 3rd time
[499]
When it'll get it once then
it'll get completely executed
[503]
But what happens in pre-emptive case is
CPU switches... maybe it'll get its turn later again
[508]
So in this case it's no problem
if you won't find response time in this case
[512]
Because it'll come equal to waiting time,
so you can directly write it
[517]
So in this question after it
they can ask average turn around time
[522]
So average turn around time is
Just total it... It'll be 25
[529]
Divided by number of processes i.e. 4
So it comes out to be 6.25
[535]
Now we'll calculate average waiting time
[538]
Just total it first... 6+4+2 = 12,
divided by no. of processes i.e. 4
[544]
So average waiting time comes out to be 3
[547]
So this is how we can solve
the question of shortest job first
[552]
Thank You!!
Most Recent Videos:
You can go back to the homepage right here: Homepage