tasks and in case of the same deadline according to the task finishing time derived
by the scheduling algorithm, both in increasing order.
These separate steps can of course be combined in one algorithm that works
incrementally and therefore much faster. However, we believe that for the sake of
understanding the algorithm, separating these steps is useful.
If T c proves to be too short, for example, due to a very short system control loop, T c
can also be extended to cover multiple loops of the control system with the disadvantages that more data must be stored for recovery and increased recovery time.
Figure 7.11 shows an example of tasks sorted according to the just given rules.
After the two (here not shown) first steps, all tasks are scheduled according to their
priorities and sorted. As preemption is allowed, the task times t i do not reflect the needed
processing time of a task, but the absolute time when a task will finish its processing.
Due to preemption, t i can be much longer than the pure processing time of task i.
For every task, it is now inserted its test in the schedule based on the rules given
above. Whenever a test is inserted, however, the remaining tasks on this processor
must be possibly shifted further in the timeline to get a large enough timeframe for
the test. As this shifting might violate the rules of the RM scheduler, the schedule
on all processors after the test insertion must be checked and updated.
If no time slot can be found to perform the testing asynchronously in the
timeframe t i to d i the task test must be performed synchronously. A timeframe of
i = 1,R = u 1 . . . u i , t last = 0
while i ≤ n do
If (t i ≤ T c − t adi )
t i possible candidate for asynchronous testing
if (t last < t i ) then
start test of task i asynchronously
R = R − {u i }
t last = t last + t adi
else
possible candidate for future asynch. testing
if t last + t adi ≤ d i then
starting time of asynch. testing of task i = t last
t last = t last + t adi
else
search largest timeslot in t ri to t i with no ongoing testing
schedule test
end
end
end
update scheduling;
i = i + 1
end
Fig. 7.10 Procedure T3
7.2 Analysis of Checking Process
85
by the scheduling algorithm, both in increasing order.
These separate steps can of course be combined in one algorithm that works
incrementally and therefore much faster. However, we believe that for the sake of
understanding the algorithm, separating these steps is useful.
If T c proves to be too short, for example, due to a very short system control loop, T c
can also be extended to cover multiple loops of the control system with the disadvantages that more data must be stored for recovery and increased recovery time.
Figure 7.11 shows an example of tasks sorted according to the just given rules.
After the two (here not shown) first steps, all tasks are scheduled according to their
priorities and sorted. As preemption is allowed, the task times t i do not reflect the needed
processing time of a task, but the absolute time when a task will finish its processing.
Due to preemption, t i can be much longer than the pure processing time of task i.
For every task, it is now inserted its test in the schedule based on the rules given
above. Whenever a test is inserted, however, the remaining tasks on this processor
must be possibly shifted further in the timeline to get a large enough timeframe for
the test. As this shifting might violate the rules of the RM scheduler, the schedule
on all processors after the test insertion must be checked and updated.
If no time slot can be found to perform the testing asynchronously in the
timeframe t i to d i the task test must be performed synchronously. A timeframe of
i = 1,R = u 1 . . . u i , t last = 0
while i ≤ n do
If (t i ≤ T c − t adi )
t i possible candidate for asynchronous testing
if (t last < t i ) then
start test of task i asynchronously
R = R − {u i }
t last = t last + t adi
else
possible candidate for future asynch. testing
if t last + t adi ≤ d i then
starting time of asynch. testing of task i = t last
t last = t last + t adi
else
search largest timeslot in t ri to t i with no ongoing testing
schedule test
end
end
end
update scheduling;
i = i + 1
end
Fig. 7.10 Procedure T3
7.2 Analysis of Checking Process
85