U ¼
X n
i¼1
c i
t i
n
ffiffi ffi
2
2
p À 1
Taking into account that lim n!1 n
ffiffi ffi
2
2
p À 1
À
Á ¼ ln2 % 0:6931 we see that every
problem is schedulable with this scheduler, as long as the system utilization is
below ln2. This does not necessarily mean that for a system with higher utilization no
feasible scheduling can be found with this algorithm, it just proves that for every
system with lower utilization than ln2, the rate monotonic scheduler finds a solution.
We now want to apply the above introduced principle of task and test to a system
with preemption, based on the static RM scheduler. We use here the same constraints
as applied for T2, i.e., the tasks are ready at an arbitrary time t ri and every task has a
given running time t i = t ri + t pi and an assigned hardware-checking time t adi .
We do not consider here any dependencies between tasks, or any task switch
times. We assume that the system provides a periodic time tick that calls the
scheduler. As the scheduling must be calculated for every time slot, we introduce
the remaining task processing time r i for every task and the deadline d i for each
task. The current time is given by T
*
, the scheduler interval by dt.
The static algorithm that we show here calculates for every scheduler tick
whether a test for a specific task should be started or not. We further calculate only
a schedule for one T c cycle, with the assumption that the T c cycle corresponds to the
global period of a control loop system.
Under this assumption, we get T c = max(d i ). The deadlines themselves must for
the sake of simplicity be a multiple of dt.
Performing an asynchronous or a synchronous test involves the same steps as
shown in Sect. 7.2, i.e., the used resources of a task still must be freed even if the
task is currently preempted.
Thus, it is preferable to test the resources in asynchronous mode. As tasks in
general have a smaller finishing time than their respective deadline (t i
d i ), the
main idea is to schedule their asynchronous test in the timeframe t i to d j .
Of course, t i + t adi
d i must hold; otherwise, the task is not schedulable. In
case of synchronous test, even t i + t sdi
d i is required. Therefore, we formulate
the following rule:
The test of task i is performed asynchronously, if it is possible to schedule it in the
timeframe t i to d i as long as all other tasks can still meet their deadlines and only
one test is executed simultaneously. Otherwise, execute the test synchronously.
In order to keep the algorithm T3 (Fig. 7.10) short and understandable, we
separate the scheduling itself from the decision algorithm. By doing this, the task
finishing times are known and can thus be used for the sorting of the tasks.
Therefore, we first perform the scheduling according to the RM scheduler and
then sort the tasks according to two criteria, first according to the deadline of the
84
7 Testing, Checking, and Hardware Syndrome
X n
i¼1
c i
t i
n
ffiffi ffi
2
2
p À 1
Taking into account that lim n!1 n
ffiffi ffi
2
2
p À 1
À
Á ¼ ln2 % 0:6931 we see that every
problem is schedulable with this scheduler, as long as the system utilization is
below ln2. This does not necessarily mean that for a system with higher utilization no
feasible scheduling can be found with this algorithm, it just proves that for every
system with lower utilization than ln2, the rate monotonic scheduler finds a solution.
We now want to apply the above introduced principle of task and test to a system
with preemption, based on the static RM scheduler. We use here the same constraints
as applied for T2, i.e., the tasks are ready at an arbitrary time t ri and every task has a
given running time t i = t ri + t pi and an assigned hardware-checking time t adi .
We do not consider here any dependencies between tasks, or any task switch
times. We assume that the system provides a periodic time tick that calls the
scheduler. As the scheduling must be calculated for every time slot, we introduce
the remaining task processing time r i for every task and the deadline d i for each
task. The current time is given by T
*
, the scheduler interval by dt.
The static algorithm that we show here calculates for every scheduler tick
whether a test for a specific task should be started or not. We further calculate only
a schedule for one T c cycle, with the assumption that the T c cycle corresponds to the
global period of a control loop system.
Under this assumption, we get T c = max(d i ). The deadlines themselves must for
the sake of simplicity be a multiple of dt.
Performing an asynchronous or a synchronous test involves the same steps as
shown in Sect. 7.2, i.e., the used resources of a task still must be freed even if the
task is currently preempted.
Thus, it is preferable to test the resources in asynchronous mode. As tasks in
general have a smaller finishing time than their respective deadline (t i
d i ), the
main idea is to schedule their asynchronous test in the timeframe t i to d j .
Of course, t i + t adi
d i must hold; otherwise, the task is not schedulable. In
case of synchronous test, even t i + t sdi
d i is required. Therefore, we formulate
the following rule:
The test of task i is performed asynchronously, if it is possible to schedule it in the
timeframe t i to d i as long as all other tasks can still meet their deadlines and only
one test is executed simultaneously. Otherwise, execute the test synchronously.
In order to keep the algorithm T3 (Fig. 7.10) short and understandable, we
separate the scheduling itself from the decision algorithm. By doing this, the task
finishing times are known and can thus be used for the sorting of the tasks.
Therefore, we first perform the scheduling according to the RM scheduler and
then sort the tasks according to two criteria, first according to the deadline of the
84
7 Testing, Checking, and Hardware Syndrome