7.2.3 Procedure T1
First, it is necessary to sort the units u i 2 U in increasing order according to their
completion time. This step is skipped in the algorithm as any standard sorting
algorithm could be applied. Keep in mind that all units (processors) are identical,
which means that T ad is constant for all units.
The most time-consuming part of the algorithm T1 (Fig. 7.6) is the sorting
which has an average complexity of O(nlog(n)) [7].
We discuss the introduced algorithm according to the example in Fig. 7.7. First,
we discuss case (1) where T c and all task completion times are known. In this case,
it is heuristically checked if t i + 1 > t i + T ad . If this is the case (case a. of Fig. 7.7),
no testing process will be ongoing when the task t i ends, and therefore, the testing
process can immediately be started. This case corresponds to step 3 of procedure
T1, when unit u j = u i+1 is set to asynchronous testing mode.
Now, if this condition does not hold (case b. of Fig. 7.7), the task on unit
u j = u i+1 finishes while the unit u i is diagnosed. Remember that the task on unit u j
Fig. 7.6 Procedure T1
7.2 Analysis of Checking Process
79