The changes in the algorithm are twofold. First, the task checking time is no
longer constant, thus we replace k Tad by the sum of the task checking times t sum .
Second, as not all tasks are ready at t = 0, it is possible that some processors are
free at some given time, which allows us to test the hardware used by tasks
asynchronously even if they are not currently running. This is possible due to the
nature of the applications in our case, namely, reoccurring periodic tasks in a closed
control system.
Case d0 in Fig. 7.9 shows the special case of a continuously running process.
This task is synchronously tested at a time where no other processor is being tested.
7.2.5 Testing of Time-Sharing Systems
In the above introduced algorithm T1 and T2 and the sketched scheduling algorithm, task preemption was not allowed. In contrast to scheduling without preemption where it can be shown that the problem to find a schedule with minimal
scheduling length is NP-hard, a static schedule with minimal length for systems that
allow preemption can be found in polynomial time [3]. For dynamic scheduling
with preemption, even O(1) schedulers are known and implemented [4, 8].
Consider the well-known Rate Monotonic (RM) scheduling where the task with
highest priority is executed. The priorities in are derived from their deadlines, which
correspond to their period. Thus w i = 1/p i with w i representing the priority of task
i and p i the period of task i. As the deadlines and therefore also the priorities do not
change during the lifetime of a system, this is a static algorithm.
Liu and Layland [9] proved that for a set of n periodic tasks with unique periods,
an RM schedule can always be found as long as the processor utilization U is
below.
Fig. 7.9 Task examples for extended testing
7.2 Analysis of Checking Process
83
longer constant, thus we replace k Tad by the sum of the task checking times t sum .
Second, as not all tasks are ready at t = 0, it is possible that some processors are
free at some given time, which allows us to test the hardware used by tasks
asynchronously even if they are not currently running. This is possible due to the
nature of the applications in our case, namely, reoccurring periodic tasks in a closed
control system.
Case d0 in Fig. 7.9 shows the special case of a continuously running process.
This task is synchronously tested at a time where no other processor is being tested.
7.2.5 Testing of Time-Sharing Systems
In the above introduced algorithm T1 and T2 and the sketched scheduling algorithm, task preemption was not allowed. In contrast to scheduling without preemption where it can be shown that the problem to find a schedule with minimal
scheduling length is NP-hard, a static schedule with minimal length for systems that
allow preemption can be found in polynomial time [3]. For dynamic scheduling
with preemption, even O(1) schedulers are known and implemented [4, 8].
Consider the well-known Rate Monotonic (RM) scheduling where the task with
highest priority is executed. The priorities in are derived from their deadlines, which
correspond to their period. Thus w i = 1/p i with w i representing the priority of task
i and p i the period of task i. As the deadlines and therefore also the priorities do not
change during the lifetime of a system, this is a static algorithm.
Liu and Layland [9] proved that for a set of n periodic tasks with unique periods,
an RM schedule can always be found as long as the processor utilization U is
below.
Fig. 7.9 Task examples for extended testing
7.2 Analysis of Checking Process
83