Hardware Reference
In-Depth Information
system may run into a critical situation. In fact, if the failing task is left in execution,
it can cause a domino effect on the other tasks, breaking the entire schedule (timeline
break). On the other hand, if the failing task is aborted while updating some shared
data, the system may be left in an inconsistent state, jeopardizing the correct system
behavior.
Another big problem of the timeline scheduling technique is its sensitivity to appli-
cation changes. If updating a task requires an increase of its computation time or
its activation frequency, the entire scheduling sequence may need to be reconstructed
from scratch. Considering the previous example, if task B is updated to B' and the
code change is such that
C
A
+
C
B
>
25
ms
, then task B' must be split in two or
more pieces to be allocated in the available intervals of the timeline. Changing the
task frequencies may cause even more radical changes in the schedule. For example,
if the frequency of task B changes from 20 Hz to 25 Hz (that is
T
B
changes from 50 to
40 ms), the previous schedule is not valid any more, because the new Minor Cycle is
equal to 5 ms and the new Major Cycle is equal to 200 ms. Note that after this change,
since the Minor cycle is much shorter than before, all the tasks may need to be split
into small pieces to fit in the new time slots.
Finally, another limitation of the timeline scheduling is that it is difficult to handle ape-
riodic activities efficiently without changing the task sequence. The problems outlined
above can be solved by using priority-based scheduling algorithms.
4.3
RATE MONOTONIC SCHEDULING
The Rate Monotonic (RM) scheduling algorithm is a simple rule that assigns priorities
to tasks according to their request rates. Specifically, tasks with higher request rates
(that is, with shorter periods) will have higher priorities. Since periods are constant,
RM is a fixed-priority assignment: a priority
P
i
is assigned to the task before execu-
tion and does not change over time. Moreover, RM is intrinsically preemptive: the
currently executing task is preempted by a newly arrived task with shorter period.
In 1973, Liu and Layland [LL73] showed that RM is optimal among all fixed-priority
assignments in the sense that no other fixed-priority algorithms can schedule a task set
that cannot be scheduled by RM. Liu and Layland also derived the least upper bound
of the processor utilization factor for a generic set of
n
periodic tasks. These issues
are discussed in detail in the following subsections.
Search WWH ::
Custom Search