Scheduling in Linux: O(n), O(1) Scheduler, Operating System, CSE, GATE Video Lecture - Computer Science Engineering (CSE)

[Music]
hello in this lecture we will look at
scheduling in the Linux operating
systems essentially we will look at how
the schedulers in the Linux kernel
evolved over time so the reference for
this particular lecture is this
particular book understanding the Linux
kernel third edition by daniel bhavet
and Marcos's Tosti Linux classifies
processes into two types one is a
real-time process and the other is
normal processes essentially a process
could be in either real-time or an
anomoly process real-time processes are
those which have very strict deadlines
for instance they could be processes
involving control of a robot or a data
acquisition systems or gic controllers
the real-time processor should never
miss a deadline and they should never be
blocked by a low priority task the other
type of processes are the non real-time
processes or in generally called normal
processes so normal processes are of two
types they are interactive or batch an
interactive process constantly interacts
with the users therefore spends a lot of
time waiting for key presses and mouse
operations so typically you could
consider these as IO bound processes
when an input R is received the process
typically should break up within 50 to
150 milliseconds if it gets delayed more
than 150 milliseconds
then the system begins to look sluggish
in the sense that a user will not feel
very comfortable using this system on
the other hand batch processes are most
closely similar to the CPU bound
processes which do not require any user
interaction and they often run in the
background
for instance GCC compilation or some
scientific operations like MATLAB are
fall into these type of processes once a
process is specified as a real-time
process it is always considered as a
real-time process in the sense that once
a user specifies that a process is a
real-time process
then it is always going to be a
real-time process even though it does
nothing but sleeping on the other hand
for processes which are non real-time
that is the normal processes it can
behave as either an interactive process
at one point of time or at other points
in time as a batch process essentially a
normal process could behave as an
interactive process or a batch process
and this behavior could vary from time
to time so in order to distinguish
between interactive and batch processes
Linux uses sophisticated heuristics
based on past behavior of the process to
decide whether a given process should be
considered at a batch or an interactive
process so we will look more into detail
about this so looking from a historic
perspective over the years starting from
Linux 2.4 to 2.6 there was a scheduler
which was adopted which was known as the
ONC jeweller then from linux 2.6 to 2.6
0.2 to the shed EULA was called the Oh 1
scheduler and the shuttle is currently
incorporated is known as the CFS
scheduler now we will look at each of
these schedulers in the following
lecture so let's start with the ONC
shuttler Oh in sherrilyn means that the
Shedd Euler looks into the queue of
ready processes which could be at most
in size and it looks into each of these
processes and then makes a choice about
the process that needs to execute so
essentially at every context which the
ONC areolar would scan the list of
runnable processes compute priorities
and select the best process to run so
scanning the list of runnable processes
is an order in job essentially we have
assumed that the ready queue has up to n
processes present so this obviously is
not scalable it's not scalable because
as n increases in number that is as more
and more processes or tasks enter the
ready queue the time to make a context
which increases essentially the context
which overheads increase and this is not
something which is wanted for so these
scalability issues with the open
scheduler was actually noticed when Java
was introduced roughly the early 2000s
and essentially due to the fact that JVM
the java virtual machine spawns multiple
tasks and each of these tasks are
present in the ready queue so the
scheduler would have to scan through
this ready queue in order to make their
choice another limitation of the owin
scheduler was that it used a single
global run queue for SMP systems
essentially when you had multiprocessor
systems as we seen in the previous
lecture a single global run queue was
used so this again as we have seen is
not scalable so the next choice was
something known as the oven scheduler
the oven scheduler would make a
scheduling decision in constant time
irrespective of the number of jobs which
are present in the ready queue
essentially it would take a constant
time to pick the next process to execute
in the CPU so this quite obviously
scales even with large number of
processes that are present in the ready
queue in the oven scheduler processes
are divided into two types the real time
processes and normal processes as we
have seen so the real time processes are
given priorities from 0 to 99 with 0
being the highest priority and 99 being
the least priority of a real-time task
now normal processes on the other hand
are given priorities between 100 to 139
so 100 is the highest priority that a
normal process could have while 139 is
the lowest priority that any process
could have and as we have seen before
the normal processes could be either
interactive or batch we will see later
how the
cellular distinguishes between the
interactive and batch processes now we
will talk about scheduling in normal
processes that is the non real-time
processes essentially the scheduling
algorithm which is used is very similar
to the multi-level feedback you with a
slight variation essentially there in
this particular scheduler there are 40
priority classes which are labeled from
100 to 139 and as we have discussed
before the lowest priority is
corresponds to the class 139 while the
highest priority for the normal task is
at hundred so corresponding to each of
these tasks there is a ready queue so
every process or every task present in
the radicchio corresponding to a
particular priority class has equal
priority to be executed on the CPU on
the other hand a process present in the
hundredth priority class has a higher
priority to execute with respect to a
process present in 1:02
that is a process present in the ready
queue corresponding to 1 0 2 now based
on this priority class the scheduler
maintains to such queues so one is known
as the active run queues and the other
one is known as the expired run queues
when a context switch occurs the
scheduler which can the active run
queues starting from the hundredth run
queue and going up to 139 it picks the
run queue which has a non zero or a
non-empty queue present in that so for
instance over here it starts from 100
and picks this first particular process
and this process is executed in the CPU
at the end of the time slice this
process is put into the expired run
queue so gradually you will see that as
time proceeds and time slice is complete
the sheduled
keeps picking out processes from the
active run queues execute them and puts
them into the
expired on Q's after a while we would
have a point where the entire processes
in the active run queue is complete
essentially become to the point that
none of these priority classes have any
processes with them on the other hand
the expired run queue is now filled up
essentially because the scheduler has
been adding processes to each priority
class in the expired run queue when this
happens the scheduler would switch
between the active run cues and the
expired run cues now this is the queues
which actually becomes active while this
becomes the expired run queues now for
consecutive time slice completions the
scheduler would pick tasks from this
particular queue and execute these tests
after execution these stars would be
moved to this queue over here which is
now the expired run queue in this way
there's a toggling between these two
queues all tasks present in one queue
are executed and moved on to the tasks
in the other queue then all tasks over
here executed and after executing the
tasks are moved to the previous queue
and so on so this process goes on
continuously the main reason for having
such a technique in the linux kernel's
scheduler is that it prevents starvation
it ensures that every process gets a
turn to execute in the cpu recall that
we call this particular scheduler as an
o1 scheduler essentially this means it
is a constant time scheduler
irrespective of the number of processes
present in the ready queues now let us
analyze how this particular thing is
constant time now if we recall there are
two steps involved in scheduling a
process first is to find the lowest
number queue with at least one task
present in that corresponding ready
queue second choose the first task from
that ready queue now how are these two
things constant time it is quite obvious
that
the second step is constant time
essentially we are choosing from the
head of the queue and that is obviously
done in a fixed amount of time
irrespective of the size of the
processes next question is how is step
one constant time so essentially we know
that the scheduler scans through all the
priority queue starting from 100 and
going up to 139 and chooses the lowest
numbered queue which has at least one
task essentially it chooses the lowest
non-empty queue so this doesn't seem to
be constant time so how does the
scheduler actually implement this so
that the time taken to actually find the
lowest non-empty queue is independent of
the number of processes in order to do
this the shell Euler or the linux shell
Euler makes use of two things the first
is a bitmap this is a 40-bit bitmap
which tows the run queues with nonzero
entities essentially this particular
bitmap store 0 charisma for a class
which has which is empty and it stores
one for a class which has nonzero
entities second in it uses a special
instruction known as find first bit set
so this particular instruction for
example there is a B SFL instruction on
Intel would look at this 40 bit bitmap
and choose the lowest index which is
nonzero essentially this would give us
the lowest numbered nonzero bit in the
bitmap and this corresponds to the
lowest nonzero or other lowest non-empty
priority queue now let's look more at
the priorities of the o1 scheduler so we
have seen that a priority is 0 to 99 I
mean for real-time tasks while priority
100 is the highest priority that can be
given to a normal process while
priority 139 is the lowest priority that
a normal process could have now these
are the ranges of the priorities for the
normal process that is a normal process
could have anything from a priority of
100 to a priority of 139 the priority
120 is known as the base priority and
taken by default so whenever you start a
program for example whenever you start
an a dot out program it has given the
priority 120 now you could change this
base priority by using the command
called nice the nice command line is
used to change the default priority of
the process from something from 120 to
something else so the command would look
something like this way so nice minus n
capital n dot slash a dot out where the
capital n can take a value of plus 19 to
minus 20 so essentially this the value
that we specified here gets added to the
base priority so for example if I say
nice minus N and plus 19 a dot out so my
the process that I'm starting will have
a priority 1 20 plus 19 so that is 1 39
so this would be the least priority and
that it could have on the other hand you
could also specify a priority like nice
minus n minus 20 dot slash a dot out so
this would give the process a priority
of 100 so this is the highest priority
that the process could get considering
that it is a normal process so these are
the static priorities that the process
could get during the start of execution
besides the static priority the
sherrilyn also sets something known as
the dynamic priority this dynamic
priority is based on heuristics and is
set based on whether the process acts
like a batch process or an interactive
process essentially it's set based on
whether the process has more of a Oh
operations or is more CPU bound so the
scheduler uses some
heuristics which is present over here to
compute the dynamic priority essentially
it takes the static priority which we
have set which is either 120 by default
given at the start of execution or this
a priority based on the nice value and
subtract something known as the bonus
and adds +5 so it takes min of this that
is static priority - bonus + 5 + 1 39
and it then takes the max of 100 and
this value so for instance let us say we
start the process with the default
static priority that is 120 and we give
a bonus of say 3 so then we have like
120 minus 3 + 5 that is 122
so min of 122 and 139 is 122 and you
take max of 100 and 122 is 122 so the
dynamic priority for this particular
example was 122 now the crucial thing is
this bonus so how is this particular
bone is set so essentially this bonus
has a value between 0 and 10 if the
bonus is less than 5 it implies there is
less interaction with the user thus the
process is assumed to be more of a CPU
bound process the dynamic priority is
therefore decrease essentially the
dynamic priority goes towards 139 of a
low priority task if the bonus is
greater than 5 on the other hand it
implies that more there is more
interaction with the user that is the
process acts more like a IO bound
process and essentially the process
behaves more like an interactive process
the dynamic priority is therefore
increased that is it goes towards 100 so
you can take two examples for instance
we have seen a bonus of 3 and we have
seen that it resulted in a dynamic
priority of 122 implying that it is more
of a CPU bound process therefore is
given a lower priority in
system on the other hand if you take a
bonus of eight and compute the same
thing you will see that the dynamic
priority actually reduces so the crucial
part is now how do we actually set the
value of bonus so the bonus is in the
scheduler is determined by the average
sleep time of a process the assumption
here is I owe bound processes will sleep
or in other words will block more
therefore should have get a higher
priority so therefore the IO bond
processes will have higher value of
bonus on the other hand CPU bran
processes will sleep less therefore
should get a lower priority if you look
at this table and if we see that the
average sleep time for the process is
greater than 200 but less than 300
milliseconds it is given a bonus of two
so this is just a heuristic and followed
as a as a formula in the in the kernel
on the other hand if the process has an
average sleep time greater than or equal
to 800 millisecond but smaller than 900
millisecond we give it a larger bonus of
eight thus these processes process with
a high value of bonus that is those
processes which sleep more are
considered interactive processes and
given a dynamic priority which is closer
to hundred on the other hand processes
which sleeps less are assumed to be CPU
bound processes and given a bonus which
is low and as a result the priority is
lowered the dynamic priority is lowered
that is it goes towards 139 so how are
these dynamic priorities affecting the
shed willing algorithm essentially if we
come back to the active and expired run
queues the dynamic priority determines
which queue the particular process would
be placed in for instance when we choose
a particular process to execute say from
the hundredth priority class and after
it executes its average sleep time is
then used to compute the bonus and
thereafter used to compute the dynamic
priority and
then this process is placed in the
corresponding priority class so as a
result based on the average sleep time
when the process is placed back in the
expired run queue the class in which is
placed it is placed in would depend on
its dynamic priority so besides the
dynamic priority there is also the time
slice which is adjusted by the scheduler
essentially interactive processes have
high priorities but they are more of Io
bound processes and they are like too
likely to have short cpu burst times
these processes essentially interactive
processes are given the largest time
slice to ensure that it completes its
burst without being premium preempted so
in order to set the time slice we are
using more heuristics such as this so
essentially if the priority is less than
120 that is it is an interactive process
then the time slice is given as 140
minus priority into 20 milliseconds
however if it is more of a batch process
that is using more of CPU activity then
the time slice is set by the lower
statement that is time size equal to 140
minus priority into 5 milliseconds so as
a result of this if you see this
particular table you see that if you
have a static priority of 100 that is
obtained by having a nice value of minus
20 so it means that this is a
interactive process and it's given a
large time slice of 800 millisecond on
the other hand a process with a static
priority of 139 that is 120 Plus having
a nice value of 19 it is given the
lowest time slice or the smallest time
slice of 5 milliseconds so thus we see
that based on the priority of the
process the corresponding time slice
given to that process is fixed so
summarizing the o1 scheduler it is a
multi-level feedback you with 40
priority classes the base priority is
set to 120 but a modifier
viable by the use of this command
colonize the dynamic priority set by
heuristics is based on the processes
average sleep time the time / interval
for each process is set based on the
dynamic priority so the limitations of
the oven scheduler is as follows so the
oven scheduler uses a lot of complex
heuristics to distinguish between
interactive and non interactive
processes so essentially there is a
dependency between the time slice and
the priority and the priority and time
slice values are not uniform that is for
processes with the priority of 100
compared to processes with the priority
of 139 if you compute the time slices in
these two ranges you see that there is
it is not uniform if you look back in
the table over here you see from going
from a priority of 100 to 110 has a time
quantum of 200 milliseconds however
going from 130 to 139 has a time slice
difference of just 45 milliseconds so
with this we'll end this particular
video lecture so in the next lecture we
look at the CFS scheduler which is the
latest scheduler or the current schedule
which is used in Linux kernels thank you
[Music]
[Applause]