Page 81 - DCAP608_REAL TIME SYSTEMS

Real Time Systems

Notes In the classic model of real-time embedded systems we have a set of tasks T1, Tn that need
to be executed periodically. Each task Ti has an associated period (Pi) and worst case
execution time (Ci). The task Ti is released every Pi time units and is required to complete
its execution before some deadline which is typically defined as the end of its period, i.e.
it must finish before its next release.
Schedulers
The real-time DVS schedulers we consider are taken from [PS01], which are based on two
of the standard real-time schedulers, namely Rate Monotonic (RM) and Earliest-Deadline
First (EDF) schedulers.

 RM schedulers are static and assign the task priority according to the period of the
tasks- they always select the task with the shortest period that is ready to run.
 EDF schedulers are dynamic and order tasks by their deadlines, giving highest
priority to the released task with the most immediate deadline.
Static Voltage Scaling Schedulers
The first schedulers that consider simply extend RM and EDF by selecting the lowest
possible operating frequency that will allow the scheduler to meet all the deadlines of the
task set. The frequency is set statically and is only changed when the task set is changed.
When selecting the operating frequency, one must take into account that, if the frequency
is scaled by a factor of a(“(0,1]), then the worst case execution time is scaled by a factor of
1/a, while the period and deadline remain unchanged. Extending the standard schedulability
tests for RM and EDF schedulers in [PS01], the following static voltage scaling algorithms
were reached:
Static_RM:
rm_test(á):
if (“ Ti “ { T1, … ,Tn | P1d” … d”Pn }. ceil(Pi/P1) × C1 + … + ceil(Pi/
Pi) × Ci d” á)
return true else return false
select_frequency
use lowest frequency fi such that RM_test(fi/f1) is true
Static_EDF:
edf_test(á):
if (C1/P1+ … +Cn/Pn  ) return true
else return false
select_frequency
use lowest frequency fi such that EDF_test(fi/f1) is true
Cycle Conserving Schedulers
In general tasks are completed far sooner than their worst case execution time and the
following algorithms of aim to take advantage of this. In particular, when a task uses less
than its worst case execution time, the scheduler can use this fact to reduce the operating
frequency. Note that, when a task is released for execution we do not know how much
computation time it will require, and therefore at this point the algorithms make the
conservative assumption that the task will require its worst case execution time. However,
when a task completes, one can calculate the number of cycles that were not required by
the task, and hence at this time the algorithms recalculate the frequency taking into account
these unused cycles (hence the term “cycle conserving”).
Contd...

76 LOVELY PROFESSIONAL UNIVERSITY