L-2.4: Shortest Job First(SJF) Scheduling Algorithm with Example | Operating System
Aug 15, 2023
L-2.4: Shortest Job First(SJF) Scheduling Algorithm with Example | Operating System
👉Subscribe to our new channel: / @varunainashots https://www.facebook.com/gatesmashers https://www.instagram.com/gate.smashers https://www.instagram.com/varunainashots https://t.me/gatesmashersofficial https://www.threads.net/@gate.smashers [email protected]
Content
0.4 -> Hello Friends, Welcome to Gate Smashers
1.971 -> Let's understand the concept of shortest
job first scheduling algorithm with a numerical
7.4 -> So in the numerical first we have given here
Four processes P1, P2, P3, P4
12.443 -> Their arrival time and burst time is given
It'll be given to you in almost all numerical
17.7 -> What we need to find is completion time,
turnaround time, waiting time and response time
24.486 -> So we have the algorithm here shortest job first
In shortest job first we have the criteria of burst time
30.243 -> Means we checks the burst time
33.1 -> Shortest job means a process whose burst time
will be lower, we'll select that process
41.986 -> Means we'll run that process first on the CPU
45.957 -> And the mode is non pre-emptive
47.929 -> Non pre-emptive means if we gave
one process to CPU to execute
53.129 -> then that whole process will get
executed without any interruption
57.314 -> Now let's start with the help of Gantt chart
because it'll make the process very easy
63.929 -> Time will start from zero always
So let's start with zero
68.2 -> So at zero, which process has arrived already
72.314 -> Now first you have to check if
there's any process arrived at zero
77.271 -> There's no process that has arrived at zero
You can get this type of numerical also in exams
83.657 -> So no problem, from zero to one
you can simply make it idle
88.357 -> Idle means CPU is idle from 0 to 1 limit of time
94.957 -> Alright if there's no process
then obviously CPU will be idle
98.643 -> Now at time 1, now we are at time 1
Now we are at time 1
104.514 -> Check at 1 first of all that which process has arrived
107.771 -> We'll check burst time criteria later,
110.571 -> first we have to find out which process arrived already
114.343 -> So I checked at 1,
then P1 and P3 arrived at 1
120.6 -> Means P1 and P3 both arrived at 1
Now should we pick P1 or P3
126.186 -> so for that I have to use the criteria i.e. Burst time
133.886 -> So first we checked Burst time of P1
P3's burst time checked 2
139.014 -> So which one is shortest out of two
That's 2,... Then we'll select P3 first
145.214 -> Because its burst time is lower
148.543 -> So now, Mode... Mode means non pre-emptive
Means it has to execute it completely
153.814 -> Executing completely means...
Its execution time is two,
158.2 -> So we executed it up to two times
Two means, we are at one and it'll take two more
165.371 -> I'll take 2 unit of time more
So 1+2... that'll become 3
169.657 -> So at 3, P3 got executed completely
Now we are at Time 3
178.629 -> So at time 3 first we have to check
that which process has arrived already
183.729 -> P1 has already arrived, P1 arrived at 1
but haven't executed yet, so we'll keep P1 here for now
190.243 -> Other than P1, which process has arrived at 3
194.114 -> If we'll check at 3, then yess P2
P2 has arrived at 2
198.157 -> So you can simply write here that yes,
P3 and P1 are already present in the ready queue
204.314 -> Now if these two processes are in ready queue,
206.971 -> then which one to select,
then we'll select it using burst time
211.786 -> Means first check the arrive
that which process has arrived
216.271 -> If only one has arrived
then there's no logic of burst time
219.686 -> We have to run that process only
221.443 -> But if too much process came
and arrived at that time
225.486 -> Then we have to use burst time
227.371 -> So in this case we have got P1 and P3
so let's check burst time first
231.671 -> P1's burst time is 3 and P2's burst time is....
235.786 -> Sorry it'll be P2 here
240.443 -> P2 came on 2 that's why P2... P3 already got
executed, so you can remove it now
245.043 -> Let's check P1 and P2's burst time
P1's burst time is 3
248.4 -> And P2's burst time is 4
Then P1's burst time is less out of two
253.186 -> So we'll get P1 executed for 3 unit of time
257.129 -> So 3 means, until 3+3 = 6 unit of time
P1 will get executed
263.1 -> Means now you can remove it also from here,
Because both of these got passed already
267.457 -> Now P1 gone already so I've P2 left now
272.2 -> But, check time first... It's 6
Now check which process has arrived at 6
277.657 -> P4 came now, because
it was supposed to come at 4
281.114 -> So it means P4 came to this point somewhere
284.586 -> So I can say there are two processes
in the ready queue i.e. P2 and P4
290.557 -> Now which process to select out of these two
Again we'll use criteria of burst time
296.8 -> So check burst time of P2... It's 4
And for P4... It's 4
302.057 -> Means Both of their burst time is same
304.557 -> Now I've created this type
of question in intentionally
307.5 -> so that we can cover
as much variations as possible
310.829 -> In this case, when P2 & P4's burst time is same
then which one to select
316.914 -> Because both of their burst time is same
318.857 -> So no problem whenever
you get conflict like this
321.586 -> then come a step back,
means check their arrival time
325.4 -> Check which one has lower arrival time
Means which one came first
332.1 -> Then you'll find out that P2 came first
335.343 -> Then which one to select
out of these two?... P2
338.4 -> 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.9 -> Just as an example if we would assume
that arrival time is also same
352.1 -> So in that case you can simply come to process ID,
355.443 -> the one with lower process ID, you can simply select it
359.729 -> So in this case we are selecting P2 first and
we have to run P2 up to four Unit of time
365.757 -> 6+4 i.e. 10
369.071 -> So we ran P2 up to 10 times, now after that
there's no problem because only P4 is left
374.886 -> So we selected P4 and
it also needs 4 unit of time
379.357 -> So 4 unit of time means 10 +4 i.e. 14
so P4 will be completed on at 14
386.257 -> Now write the completion time first of all
when P1 got completed?
390.4 -> 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.857 -> Now check P3... P3 completed at 3
401.857 -> Now we checked P4 and
it got completed at 14
404.543 -> So this is how we can
calculate the completion time
407.714 -> When completion time arrived, then
for TAT and WT just use the simple formula
413.757 -> Completion time - arrival time
i.e. turn around time
416.8 -> So its value will be 5... 10-2 = 8
3-1 = 2... 14-4 = 10
426.686 -> Now for waiting time... Turn around time - burst time
431.957 -> So turn around time is 5, burst time is 3
So it comes out to be 2
436.471 -> 8-4 = 4.... 2-2 = 0..... 10-4 = 6
442.957 -> So this is the waiting time
445.643 -> Response time....
446.957 -> You don't need to find response time in case
of non pre-emptive because it'll be equal to waiting time
453.857 -> In case if they asked you,
then simply how we select response time?
458.786 -> The time at which a process gets the CPU first time
463.557 -> For example... When P3 got the CPU first time
At one... you can check the left side
469.329 -> And P3 came at one also
So 1-1 = 0
476.5 -> Means you don't have to do it
because it'll come equal to waiting time
480.1 -> But in case if they asks you
then you can calculate like this
484.343 -> Why it is not coming in it?... Response time
will come in case of pre-emptive only
488.129 -> because when a process gets CPU,
491.729 -> no matter at what time,
then that process will get completely executed
495.971 -> Then there's no chance of
getting the CPU 2nd or 3rd time
499.486 -> When it'll get it once then
it'll get completely executed
503.057 -> But what happens in pre-emptive case is
CPU switches... maybe it'll get its turn later again
508.514 -> So in this case it's no problem
if you won't find response time in this case
512.829 -> Because it'll come equal to waiting time,
so you can directly write it
517.943 -> So in this question after it
they can ask average turn around time
522.5 -> So average turn around time is
Just total it... It'll be 25
529.457 -> Divided by number of processes i.e. 4
So it comes out to be 6.25
535.157 -> Now we'll calculate average waiting time
538.557 -> Just total it first... 6+4+2 = 12,
divided by no. of processes i.e. 4
544.7 -> So average waiting time comes out to be 3
547.129 -> So this is how we can solve
the question of shortest job first
552.286 -> Thank You!!
Source: https://www.youtube.com/watch?v=VCIVXPoiLpU
