Rate Monotonic Algorithm (RMS) & Earliest Deadline First (EDF) Video Lecture | Embedded Systems (Web) - Computer Science Engineering (CSE)

to the most fundamental scheduling
policies for real-time systems our rate
monotonic scheduling or RMS and earliest
deadline first or EDF will first look at
rate monotonic scheduling which is a
static priority system the priorities of
processes don't change during execution
RMS uses two parameters for processes TI
is the computation time of process I and
tau I is the period of process I the RMS
model makes several assumptions all
processes run on a single CPU context
switching takes zero time process
execution time is constant the
activation time for every process is at
the beginning of its period and the
deadline is at the end of the period and
the scheduling rule is that the highest
priority ready process runs now note
that this makes no assumptions about the
relationships between periods so for
example in a simple example you can have
p1 with these periods p2 with this
period p3 with very different period and
p4 with yet another period rate
monotonic analysis allows us to
determine what priorities should be
assigned to the different processes it
assumes static priorities response time
refers to the time required to finish a
process including all the interference
from other processes and in rate
monotonic analysis the critical instant
is the state of the schedule that gives
the absolute worst response time for a
process and that always happens when all
the higher priority processes are just
ready to execute so in this case p4 is
ready to execute but so are p1 p2 and p3
we have to make sure they all execute
before p1 we have to make sure they can
all execute before p2 we have to make
sure they all execute before p4 can
finish but p1 p2 and p3 don't just
execute once they'll execute several
times before p4 can finish this analysis
leads us to an interesting result the
optimal way to assign fixed priorities
to processes is based on period the
process with the shortest period gets
the highest priority
the next shortest period gets the next
highest priority and so forth so
priority is inversely proportional to
period if we have ties to processes that
have the same period we can break ties
arbitrarily so notice that this rule
doesn't depend upon the computation
times the tasks only the periods and no
fixed priority scheme does better let's
think for a minute about the utilization
of RMS for arbitrary deadlines the
critical instant doesn't always happen
remember that the critical instant
happens when all the processes line up
and are just ready to run that happens
occasionally but not all the time so the
schedule has to be designed to account
for this worst-case but when this worst
case doesn't happen the CPU has idle CPU
time that's only used during the
critical instant now of course some
combinations of deadlines can allow for
a hundred percent utilization but RMS in
general doesn't guarantee 100%
utilization of the CPU we can understand
this a little better with an asymptotic
analysis to see what happens when we
increase the number of processes so the
utilization is the sum of the ratios of
the computation time in the periods as
we increase the number of processes to
infinity with no restriction on the
relative periods you can prove that the
maximum utilization approaches 69% so
remember
that four particular combinations of
periods we can get a hundred percent
utilization but this asymptotic result
illustrates the fact that RMS doesn't
always use 100 percent of the CPU it
does however guarantee that it meets its
deadlines in contrast to RMS earliest
deadline first dynamically changes the
priorities of processes during execution
the priorities of processes in EDF are
determined by their distance to the
deadlines the task closest to its
deadline has the highest priority so the
priority of a task changes during
execution this timeline shows the
deadlines of processes so at this point
in the schedule p1 is closest to its
deadline so it has the highest priority
at this point p2 is closest to its
deadline so it would have the highest
priority and at this point p3 is closest
to its deadline so it has the highest
priority we can show that EDF is able to
schedule all of its tasks if the
utilization is less than or equal to 1%
of course if the CPU is overloaded the
failure analysis for EDF is more
complicated because the priorities of
the task change
let's compare RMS and EDF RMS is easier
to understand and it requires a little
less scheduling overhead but EDF can
schedule some tasks that RMS cannot this
example illustrates up set of processes
the EDF can schedule that RMS cannot the
colored boxes show the locations of the
deadlines of the different processes and
at the bottom we have lines for the RMS
schedule and for the EDF schedule so
this example has three processes p1 has
a computation time with 1 and a period
of 3 p2 has a computation time of 2 and
a period of 4 p3 has a computation time
one and a period of six we can see the
critical part of the schedule right here
at time 5 RMS schedules P 2 because that
has the highest priority in a static
priority system however EDF schedules P
3 because P 3 is closest to its deadline
at t 6 here so that allows P 3 to finish
this graph doesn't show the RMS schedule
past time 6 because at that point RMS
has missed the deadline for P 3 to
summarize rate monotonic scheduling
is a static priority scheduling policy
earliest deadline first uses dynamic
priorities each has its advantages and
disadvantages but both can be analyzed
to determine when they guarantee that a
set of processes will meet all their
deadlines