T sd ¼ T ad þ ðT u þ T r Þ
ð 7:1Þ
where T u is the time of unloading, and T r is the time of reloading the user task in
synchronous diagnostics. In order to have an upper bound on the checking overhead
at any given point in time, we propose here that at any given moment in time, the
diagnostic process can run on at most one processor.
Otherwise, as shown above, by accident, a simultaneous testing of all processors
would turn the system completely unresponsive. In this spirit, it is also necessary to
relax the strict order of the testing explained in Sect. 7.2, and allow the testing to be
done during task execution.
The recovery in this case would involve higher cost as the outcome of the last
task run cannot be trusted and must be repeated as well.
7.2.2 Diagnostic Process Algorithm
Suppose a computing system consists of n processes. If only synchronous SDD is
used, a loop embedded in the firmware or the task scheduler chooses the next unit,
which will be diagnosed by chance. The choosing overhead itself is considered as
negligible.
The real value of the asynchronous SDD depends on the sequence in which the
units are diagnosed. The most natural way to appoint a diagnostic process for a unit
is when the unit gets free. However, if a long-running task is assigned to a single
processor, it is not diagnosed for a long time. Therefore, in this special case, the
synchronous SDD are preferable.
On the other hand, time-critical tasks in a real-time system should not be
interrupted, and thus the asynchronous SDD should be applied. To decrease time
overheads but still provide completed testing, a combination of both diagnosis
modes seems to be ideal.
According to Blazewicz [3], even for the simple case of the problem P || Cmax
where a set of independent tasks is to be scheduled on identical processors without
preemption in order to minimize schedule length can be proved to be a problem of
complexity NP-hard [6]. Thus, our problem which imposes further restrictions on
the scheduling algorithm and is therefore is also NP-hard cannot be perfectly solved
in a real system with a high number of tasks. The use of an optimization algorithm
seems to be therefore the way to go.
In general, two main scheduling principles can be used: offline scheduling and
online scheduling. In offline scheduling, the whole schedule is computed during the
system design phase. In this case, the time efficiency of the used scheduler is of no
importance, and therefore, more complex algorithms can be used to calculate the
schedule. Chances to get a schedule that satisfies all constraints are higher, and it is
relatively easy to incorporate constraints such as deadlines or precedencies. During
program execution, the tasks are executed according to the precomputed schedule.
7.2 Analysis of Checking Process
77
ð 7:1Þ
where T u is the time of unloading, and T r is the time of reloading the user task in
synchronous diagnostics. In order to have an upper bound on the checking overhead
at any given point in time, we propose here that at any given moment in time, the
diagnostic process can run on at most one processor.
Otherwise, as shown above, by accident, a simultaneous testing of all processors
would turn the system completely unresponsive. In this spirit, it is also necessary to
relax the strict order of the testing explained in Sect. 7.2, and allow the testing to be
done during task execution.
The recovery in this case would involve higher cost as the outcome of the last
task run cannot be trusted and must be repeated as well.
7.2.2 Diagnostic Process Algorithm
Suppose a computing system consists of n processes. If only synchronous SDD is
used, a loop embedded in the firmware or the task scheduler chooses the next unit,
which will be diagnosed by chance. The choosing overhead itself is considered as
negligible.
The real value of the asynchronous SDD depends on the sequence in which the
units are diagnosed. The most natural way to appoint a diagnostic process for a unit
is when the unit gets free. However, if a long-running task is assigned to a single
processor, it is not diagnosed for a long time. Therefore, in this special case, the
synchronous SDD are preferable.
On the other hand, time-critical tasks in a real-time system should not be
interrupted, and thus the asynchronous SDD should be applied. To decrease time
overheads but still provide completed testing, a combination of both diagnosis
modes seems to be ideal.
According to Blazewicz [3], even for the simple case of the problem P || Cmax
where a set of independent tasks is to be scheduled on identical processors without
preemption in order to minimize schedule length can be proved to be a problem of
complexity NP-hard [6]. Thus, our problem which imposes further restrictions on
the scheduling algorithm and is therefore is also NP-hard cannot be perfectly solved
in a real system with a high number of tasks. The use of an optimization algorithm
seems to be therefore the way to go.
In general, two main scheduling principles can be used: offline scheduling and
online scheduling. In offline scheduling, the whole schedule is computed during the
system design phase. In this case, the time efficiency of the used scheduler is of no
importance, and therefore, more complex algorithms can be used to calculate the
schedule. Chances to get a schedule that satisfies all constraints are higher, and it is
relatively easy to incorporate constraints such as deadlines or precedencies. During
program execution, the tasks are executed according to the precomputed schedule.
7.2 Analysis of Checking Process
77