CPU Scheduling: FCFS, SJF, SRTF, Round Robin, Operating System, CSE, GATE Video Lecture - Computer Science Engineering (CSE)

[Music]
hello in this lecture we will look at
CPU scheduling algorithms we have seen
in operating systems that a scheduler
present would choose a particular
process from the ready queue and that
process is assigned to run in the
processor now the question that we are
going to analyze now is how should this
shed Euler choose the next process
essentially how should the scheduler
choose a process to run on the CPU from
the existing queue of ready processes
now to analyze this we first look at
execution phases of a process now any
program has been known to have two
phases of execution one is when it is
actually executing instructions which is
known as a CPU burst while the other is
when it is blocked on an i/o or not
doing any operations so in this
particular case the CPU is idle thus as
we look with overtime a particular
process would have some amount of CPU
burst in which it would execute
instructions on the processor then it
would have and some idle time in which
it is waiting for an i/o operation then
there would be a burst of CPU time and
so on thus there is always this
interleaving between CPU bursts and idle
time that is awaiting for an operation
so based on this phases of execution one
can classify processes into two types
one is the i/o bound processes while the
other is the CPU bound process why do
you make this distinction between IO
bound and CPU bound processes
essentially this is from a scheduling
perspective we would like to give I Oh
bound processes a higher priority with
which they are allocated the CPU
essentially we want that IO bound
processes wait lesser time for the CPU
compared through CPU bound processes so
why is this required we can take with an
example so suppose we we are using a
word processor such as a node
or VI M and we are giving this i/o bond
process a very low priority now suppose
a user presses a key because it has a
low priority it does not get the CPU to
very often and therefore it would take
some time before that key pressed by the
user appears onto the screen so this may
be quite uncomfortable for the user
therefore we would like to give the i/o
bound process such as the word processor
higher priority with which it will get
the CPU so that the user interaction
with the CPU becomes more comfortable on
the other hand if we look at CPU bound
processes we could give it a lower
priority now for instance if you take
one of these applications the CPU bound
applications like for instance say let's
say GCC that is compiling a program and
let us say you are compiling a large
program which takes five minutes
now it will not affect this user much if
the time taken to compile that
particular program increases from five
minutes to say five point five minutes
thus CPU bound processes could work with
the lower priority this classification
between IO bound and CPU bound is not a
rigid classification that is a process
could be an i/o bound process at one
time and after some time it could behave
like a CPU bound process so to take an
example of a process which behaves both
like an i/o bound as well as CPU bound
you could take for instance Microsoft
Excel when we are actually entering data
into the various cells in Excel it acts
as IO bound process so it behaves like
an i/o bound process with small CPU burs
and large times of Io cycles while on
the other hand when you are actually
computing some statistic on the data
entered Excel will behave like a CPU
bound process where there is a large
portion of CPU activity or the time
taken to actually operate on that
particular data now let us come back to
the question about how the CPU scheduler
should choose from the
q of ready processes the next process to
execute in the CPU there could be
several ways in which the scheduler
could mix this choice essentially there
could be several CPU scheduling
algorithms which would look into the
queue and make a particular decision so
in order to compare these various
scheduling algorithms operating systems
textbooks or operating systems research
defines several scheduling criteria so
these criteria could be used to actually
compare various scheduling algorithms to
see the advantages and disadvantages of
each of them so let us go through each
of these scheduling criteria one by one
the first scheduling criteria is the CPU
utilization the scheduling algorithm
should be designed in such a way so as
to maximize CPU utilization in other
words the CPU should be idle as minimum
time as possible the next criteria we
will look at is the throughput
essentially scheduling algorithms would
try to complete as many processes as
possible per unit time a third criteria
is the turnaround time and this criteria
is looked at from a single process
perspective so turnaround time is
defined as the time taken for a single
process from start to completion the
fourth criteria is response time so this
is defined as the time taken from the
point that when the process enters into
the ready queue to the point when the
process goes into the running state that
is the time taken from the instant the
process enters the ready queue to the
time the CPU begins to execute
instructions corresponding to that
process another criteria is the waiting
time now this criteria is based on the
time taken by a process in the ready
queue now as we know processes ready to
run are present in the ready queue and
it is required that they do not wait too
long
in the ready queue so scheduling
algorithms could be designed in such a
way that the waiting time or the average
waiting time in the ready queue is
minimized the final criteria we will see
now is fairness
the scheduler should ensure that each
process is given a fair share of the CPU
based on some particular policy so it
should not be the case that some process
for instance takes say 90% of the CPU
while all other processes just get
around 10% of the CPU so all these
criteria need to be considered while
designing a shadowing algorithm for an
operating system a single scheduling
algorithm will not efficiently be able
to cater to all these criteria
simultaneously so therefore scheduling
algorithms are therefore designed for to
meet a subset of these criteria for
instance if you consider a real-time
operating system the scheduling
algorithm for that system would for
instance be designed to have minimum
response time other factors such as CPU
utilization and throughput may be of
secondary importance on the other hand a
desktop operating system like Linux
should will be designed for fairness so
that all applications running in the CPU
or in the system are given a fair share
of the CPU criteria such as response
time may be less important from that
perspective so we will now look at
several scheduling algorithms starting
from the simplest one that is the first
come first serve scheduling algorithm
and go to more complex scheduling
algorithms as we proceed so let us look
at the first-come first-serve of the
FCFS scheduling algorithm the basic
scheme in this case is that the first
process that requests the CPU would be
allocated the CPU or in other words the
first process which enters into the
ready queue would be allocated the CPU
so this is a non pre-emptive scheduling
algorithm which means that the process
once
allocated the CPU will continue to
execute in the CPU until it's burst
cycle completes let's see this with an
example let's say we have a system with
four processes running the processes are
labeled P 1 P 2 P 3 P 4 and they have an
arrival time so the arrival time is
present in the second column so the
arrival time is defined as the time when
these processes enter into the ready
queue so for this particular a very
simple example so we will consider that
the that all processes enter the ready
queue at the same time that is at the
0th time instant the third column is the
cpu burst time so it gives the amount of
cpu burst for each process for instance
p1 has a cpu burst of seven cycles p2
has a burst of four cycles thus this
particular table we have like four
processes which all enter simultaneously
into the ready queue at the time
instance zero and they have different
CPU burst times for instance p1 has
seven cycles p2 for cycles p3 two cycles
and p4 five cycles now we will see how
these four processes get scheduled into
the CPU or how these four processes get
allocated the CPU since all of these
processes arrive at the same time the
scheduler does not actually have a
choice to make
so he would pick randomly a particular
ordering for instance let us say the
scheduler picks p1 to run so p1 runs for
seven cycles and when it completes the
scheduler picks P 2 and P 2 runs for 4
cycles after p2 completes its burst when
P 3 executes in the CPU for 2 cycles and
then finally P 4 is scheduled in to
execute for five CPU cycles so this is
represented by a grant
so a grand chart is a horizontal bar
chart developed as a production tool in
1917 by Henry L grant who was an
American engineer and a social scientist
so essentially in the grand chart we
have like several blocks over here and
each block represents a cycle of
execution so for instance p1 executes
for seven cycles so it has like seven
blocks 1 2 3 4 5 6 7 p2 then executes
for 4 cycles so it's given like 4 blocks
then p3 executes for 2 cycles so it's
given 2 blocks and finally people
execute for 5 blocks five cycles so it's
given five blocks so we could compute
the average waiting time for this
particular case we see that process p1
enters into the ready queue at the
instance zero and immediately gets to
execute in the cpu thus it does not have
to wait at all the second process p2
arrives also at zero that is also
arrives at this point but gets to
execute only after p1 executes that is
after seven cycles thus its wait time is
for process P 2 is 7
similarly process p3 which also enters
in the zeroth cycle gets to execute only
after process p1 and p2 completes in
other words it has to wait 7 cycles in
the fourth process in a similar way
needs to wait for 13 cycles therefore
the average waiting time in this
particular case is 7 point 7 5 cycles
now we can look at an other scheduling
criteria which is the average response
time so average response time in this
case is the same as the average waiting
time so the average response time is the
time taken for a particular process to
begin executing in the CPU minus the
time it actually enters into the ready
queue so for instance
the two enters into the ready queue at
this instant but begins to execute in
the CPU only after seven cycles so
therefore the response time for process
P 2 is 7
similarly process P 3 has a response
time of 11 because it has waited for 11
cycles to actually begin executing in
the CPU so on average the average
response time is seven point seven five
just like the average waiting time now
one characteristic of the FCFS
scheduling algorithm is that the order
of scheduling matters in the previous
slide that is in this slide we had
assumed that P one executes then P 2
excuse then P 3 and then P 4 and we have
got a bridge waiting time and average
response time of seven point seven five
cycles now suppose we just change the
ordering and let us say the ordering is
now as follows that P 2 execute then P 3
execute then P 4 and finally P 1 in such
a case if we compute the average waiting
time it we see that it gets reduced from
seven two point seven five cycles to
five point two five cycles similarly if
you compute the average response time
you will see that the response time is
also five point two five cycles in a
similar way you could compute the other
criteria which we have mentioned over
here and you will be able to actually
see the difference with the to ordering
schemes another characteristic of the
FCFS scheduling algorithm is the convoy
effect essentially in this particular
case we see that all processes wait for
one big process to get off the cpu so
for instance in this case until or
rather even though all processes enter
the CPU at the same time all processes
have to wait for P 1 to complete only
then that they could be scheduled so if
we have a large process over here for
instance we have a process P 1 instead
of a burst time of seven takes
a bur storm of of say hundred all other
processes p2 p3 and p4
would wait for 100 clock cycles before
they actually be able to get to execute
in the cpu so this is a huge drawback of
the FCFS scheduling scheme however FCFS
scheduling algorithm have several
advantages but the first thing is it is
extremely simple so the scheduling
algorithm could complete very quickly
and therefore the time taken by the
scheduling algorithm will be very less
and you would end up with very less
context delays while changing the
context another advantage of the FCFS
scheduling algorithm is that it is fair
as long as no process hogs the cpu every
process will eventually run or in other
words as long as every process
terminates at some point every other
process in the ready queue will
eventually get to execute in the cpu now
the drawback or the disadvantage of the
FCFS schedulers as we have seen is that
the waiting time depends on the arrival
order so we have seen the example in the
previous slides another disadvantage is
that short processes are stuck in the
ready queue waiting for long processes
to complete or rather this is the convoy
effect that we have looked at now let us
look at another scheduling algorithm
known as the shortest job first
shadowing algorithm in this particular
scheduling algorithm the job or the
process with the shortest cpu birth time
is scheduled before the others now if
you have more than one process with the
same cpu burst time then the standard
FCFS scheduling is used there are two
variants of the shortest job first
shadowing algorithm the first is the no
preemption variant while the second one
is the shortest job first with
preemption now in the STF with no
preemption the process will continue to
execute in the cpu until its cpu burst
completes
in the second variant with preemption it
may be possible that the process which
may get preempted when a new process
arrives into the ready queue
we'll see you more on this later but
first we will start with the shortest
job first variant with no preemption
so let's take the same example that we
have seen in the previous case we have
the four processes P 1 2 P 4 and all of
them are arriving at the instant 0 that
is at instant 0 these four processes P 1
2 P 4 get into the ready queue and each
of these processes have a different CPU
burst time that is 7 4 2 and 1
respectively now in the first instant
the cpu scheduler will look at the
various burst times and find the one
which is minimum so in this case we see
that p 4 has the minimum CPU burst time
so that is scheduled first so first the
process P 4 gets scheduled until it
completes in this particular case it
completes in one cycle then among the
remaining three we see that P 3 has the
lowest CPU burst time so process P 3
gets scheduled and complete still and
execute till it completes its burst then
P 2 get scheduled because it has a burst
time of 4 while P 1 has a higher burst
time of 7 and finally P 1 gets to
execute till completion now the average
wait time if we compute this is 2.75
while the average response time is also
2.75 as in the wait time case now let us
look at another example of shortage job
first without preemption so we will take
the same processes P 1 2 P 4 and each of
these processes have the same burst time
as before that is 7 4 2 and 1
respectively
however they arrive at different
instants that is the moment the instant
in which they enter into the ready queue
would be different so P 1 enters at the
zeroth instant P 2 in the second instant
P 3 at the 4th instant and P 4 in the
7th instant now this is a slight
modification in the grant chart
we're in addition to showing which
process is executing in the CPU it also
shows the order in which processes
arrive it shows that P by P one arrives
first then P 2 in the second instant
then P 3 and fine finally P 4 in the
seventh instant
now when the shady loop begins to
execute at this particular instant the
only process that has arrived at this
particular point is p1 therefore it
should use p1 to execute so p1 executes
for its entire burst that is of seven
cycles and then at this particular cycle
the scheduler enters again or shed Euler
begin execute again and this time it has
got three processes to choose from all P
2 P 3 as well as P 4 have arrived in the
ready queue and out of them P 4 has the
shortest burst time therefore it is
chosen for execution therefore P 4
executes in the CPU and then P 3 because
P 3 has a shorter bursts time than P 2
and finally P 2 gets executed so if we
compute the average wait time we see
that it is 3 cycles so the advantages of
the shortest job first scheduling
algorithm is that is optimal that it
will always do you the minimum average
waiting time and as a result of this the
average response time also decreases the
main disadvantages of the STF scheduling
algorithm is that it is not practical
essentially it is very difficult to
predict what the burst time would be so
another drawback of the STAAR shadowing
algorithm is that some jobs may get
stabbed
essentially if you have a process which
has an extremely long CPU burst time
then it may never get a chance to
actually execute in the cpu now we will
look at the shortage job first
scheduling algorithm or with preemption
so this is also the shortest remaining
time first so the basic idea in this
algorithm is that if
you process arrives into the ready queue
and this process has a shorter birth
time then the remaining of the current
process then there is a context switch
and the new process gets scheduled into
the CPU this further reduces the average
waiting time as well as the average
response time however as in the previous
case that is the shortest job first with
no preemption here also it is not
practical so let us understand more on
this with an example so let us take the
same example of four processes with
burst time seven four two and one and
arrival times at zero two four and seven
we will develop the grant chart as the
time processes so at the instant zero
the only process which is present is p1
and therefore the scheduler has no
choice but to schedule p1 onto the CPU
thus p1 would execute for two clock
cycles now after the second clock cycle
the process p2 has entered into the
ready queue now you see that p2 has a
burst of four cycles
however p1 has a remaining burst of 5
cycles so what we mean by this is that
out of the CPU burst time of seven
cycles p1 has completed two cycles so
what remains is 5 now the shed you will
see that p1 has 5 cycles which is
greater than p2 which has burst of 4
cycles therefore it will do a context
switch and schedule p2 to run so p2 will
run for 2 clock cycles and then p3
arrives at the fourth clock instant so
at this particular instant the shed
Euler will find out that p3 has a burst
time of 2 cycles while p2 has a
remaining burst time of 2 cycles we
achieved two because out of the 4 cycle
burst time for p2 it has completed two
so what remains is two more cycles since
p2 the old process which is running on
the CPU has a two cycle remaining burst
time and p3 the new process also has
cycle burst I'm therefore there is no
preemption and p-two will continue to
execute now after p2 completes in this
particular case p3 executes for two
cycles and then p4 enters now after
which if you will verify will not cause
any preemption
so after p3 completes the scheduler
decides to run either p4 or p1 so we see
that people has a burst cycle of 1 while
p1 has a remaining birth cycle of 5
therefore the shed EULA will decide to
choose p4 over p1 so p4 runs on the cpu
and after it completes p1 will execute
for its remaining burst time so if you
compute the average wait time you see
that it reduces to 2.5 while the average
response time reduces considerably to
0.75 however as we mentioned before just
like the shortest job first
this scheduling algorithm is also not
feasible to be implemented in practice
because it is very difficult to actually
identify what the burst time of a
process is and even more difficult to
identify what the remaining burst time
of the process would be now we will look
at another shedding of algorithm known
as the round-robin scheduling algorithm
so essentially with the round-robin
scheduling algorithm a process runs for
a time slice that is a process executes
for a time slice and when the time slice
completes it is moved on to the ready
queue so in order to achieve this
round-robin scheduling algorithm which
is also a pre-emptive scheduling
algorithm now in order to achieve the
round-robin scheduling we need to
configure the timer in the system to
interrupt the CPU periodically at every
timer interrupt the colonel would
preempt the current process and choose
another process to execute in the cpu
let us discuss the round-robin
scheduling algorithm with an example so
one difference with respect to the other
building algorithms that we have seen so
far is the notion of time slice so this
is the grant chart so especially see
that periodically in this case with the
period equal to 2 that is we have
keeping our time slice equal to 2 there
is a timer interrupt that occurs and the
timer interrupts would result in the
scheduler being run and potentially an
other process being scheduled into the
CPU so a data structure which is very
useful in implementing the round-robin
scheduling algorithm is the FIFO so that
this particular people
Stowe's the processes that need to be
executed next into the CPU for example
in this particular case P 2 is at the
top of the FIFO so it is the next
process which gets executed in the FIFO
so P 2 gets executed over here so for
our example we will still consider the
four processes as we have done before
that is P 1 2 P 4 and we will assume
that all of them arrive at the instance
0 and go into the FIFO or the ready
queue and they have burst times of 5 4 2
& 3 respectively
so let us say for discussion that the
scheduler starts off with this
particular order P 1 P 2 P 3 and P 4 so
and it first chooses to execute P 1 so P
1 executes for two cycles and then there
is a interrupt which occurs leading to a
context switch and then the top of the
FIFO in this particular case P to get
scheduled into the CPU while P 1 gets
pushed into the FIFO so P 2 then
executes for 2 cycles until the next
timer interrupts in which case the time
slice of two cycles completes and then
it gets pushed into the FIFO so P P 2
now is at the bottom of the FIFO while P
3 which is at the top of the FIFO gets
scheduled to run so in this way every
two cycles a new process may get
scheduled into
the CPU and execute so if we compute the
average waiting time so in this
particular case we will see that the
average waiting time and the average
response time is different
so what is the average waiting time for
p1 so the p1 executes two cycles here
two cycles here and a completes
execution over here so it waits in the
in the ready queue in the remaining of
the cycles so the number of cycles it
waits is 1 2 3 4 5 6 7 8 9 so p1 waits
for nine cycles now p2 waits for eight
cycles 1 2 3 4 5 6 7 8
p3 for 4 cycles and p4 for 10 cycles so
the average waiting time is 7 point 7 5
cycles now to compute the average
response times as we defined it before
the response time is the time the
process enters into the ready queue to
the time it begins to execute in the CPU
that latency would be the response time
so p1 for instance has a response time
of 0 because it enters into the ready
queue or in enters into the FIFO and
gets executed immediately p2 on the
other hand enters in the zeroth cycle
but gets to execute only after two
cycles so it has a response time of 2
similarly p3 enters at zero but executes
only at this point so at rather at this
instant therefore it has a response time
of 4 and p4 has a response time of 6
therefore the average response time is 3
now the number of context switches that
occur are is 7 so in this case 1 2 3 4 5
6 and a context switch occurs over here
because the process p4 is a is exiting
out and p1 gets continues to execute
so the number of contexts which is over
here are seven that is one two three
four five six and the seventh context
which occurs over here when P four exits
and P 1 gets switched into the CPU now
let us take another more complex example
of round-robin scheduling where we also
have arrival times which are not the
same so P 1 is arriving at the 0 to
instant P 2 at the second P 3 and P 4 at
the third and ninth respectively
so we can similarly draw the grant chart
and the states of the FIFO for this case
so to start with in the zeroth instant
the only process which has arrived is P
1 and therefore P 1 executes for two
cycles and at this particular point when
the timer interrupt occurs no other
process is present as yet therefore P 1
will continue to execute for another 2
cycles for another time slice however in
this time slice we have two processes
which have entered into the ready queue
these are the process P 2 and P 3 so P 2
arrives at this interval while P 3
arrives at this interval and they get
added into the FIFO so at the second
time slice completion there is a context
switch and P 2 gets scheduled into into
the CPU to execute while P 1 which was
executing will then go into the FIFO so
P to execute for two cycles then P 3
executes for two cycles then P 1
executes for two cycles and at that time
for P 4 has arrived and gets added into
the FIFO so now we have three processes
P 1 P 2 and P 4 and these get scheduled
to run over a period of time so the
average waiting time in this case is 4
point 7 5 while the average response
time is 2 so how is the average waiting
time for 0.75
it means that process p1 has waited for
seven cycles so before it completes so
that is one two three four five six and
seven
while process p2 has waited for six
cycles so it is one two three four five
six process three has waited for three
cycles and process for has been waited
for three cycles the average response
time can be verified to be equal to 2
and the number of context switches was
as before seven now let's take the same
example as we have done before but with
a time slice of one that is we have
reduced the time size from two and we
have made it one so we see that in every
instant we have a timer interrupt and
potentially a context switch that can
occur if we compute the average waiting
time and average response time for this
particular case we see that the average
response time in particular has reduced
why has this occurred is because once
the process has entered into the queue
it has to wait for lesser cycles before
it gets scheduled into the CPU on the
other hand the number of context
switches has increased from 7 to 11
since we are having timer interrupts
which are more frequent therefore there
is more likely that a context switch
will occur now if we take the same
example but with the time slice of 5
instead of 1 and if we compute the
average waiting time and average
response time we see that the response
time increases considerably to 2.75
while the number of context switches
reduces quite a bit to 4 on the other
hand we see that the scheduling begins
to behave more and more like the first
come first serve the response time is
bad because due to the large time slice
the scheduling behaves more and more
like the first come first serve which we
know has a bad response time so from all
these
examples that we have seen so far we
seen we can conclude that the duration
of a time slice is very critical so it
affects both the response time as well
as the number of context switches so
essentially if we have a time slice
which is of a very short quantum the
advantage is that processes need not
wait too long in the ready queue before
they get scheduled into the CPU
essentially this means that the response
time of the process would be very good
or it would have a less response time on
the other hand having a short time slice
is bad because we would have very
frequent context switches and as we have
seen before context switches could have
considerable overheads therefore it
degrades the performance of the system a
long time slice or a long quantum has
the drawback that processes no longer
appeared to execute concurrently it
appears more like a first-come
first-serve type of scheduling algorithm
and so this again in turn may degrade
system performance so typically in a
modern day operating systems the time
slice duration is kept anything from 10
milliseconds 200 milliseconds so xv6
programs programs the timer to interrupt
every 10 milliseconds so the advantage
of the round-robin scheduling algorithm
is as follows the algorithm is fair
because each process gets a fair chance
to run on the CPU the average wait time
is low especially when the burst times
vary and the response time is very good
on the other hand the the drawbacks of
the round-robin scheduling algorithm are
as follows there is an increased number
of context switching that occurs and as
we have seen before context switching
has considerable overheads and the
second drawback is that the average wait
time is high especially when the burst
times have equal links the xp6
scheduling policy is a variant of the
round-robin scheduling policy the source
code is shown over here
so essentially what
the sv6 sheduled does is that it passes
through the pea table array so we have
seen pea table before which is an array
of procs and the shed Euler passes
through this particular array and finds
the next process that is runnable and
invokes the switch so this is where you
invoke the context switch so every time
the scheduler executes the next process
in this array that is runnable gets
scheduled to execute so next we will see
shadowing algorithms which are based on
priority so these are the priority based
scheduling algorithms thank you
[Music]
[Applause]