«Real-time systems are one of the most important applications of computers, both in commercial terms and in terms of social impact. Increasingly, ...»
Work along these lines is presented in [Bertossi, et al., 2006]. If tasks are assigned in descending order of RM priority, the assignment of a new task can never aﬀect the schedulability of a previously assigned task (since all previously assigned tasks would be of higher priority than the one currently being assigned).
We have assumed in our discussion that the system is able to rapidly carry out the feasibility check of tasks as they arrive. A variation on this is where the incoming tasks are queued and there is a central scheduler which carries out the feasibility check every so often on the tasks that it ﬁnds in that queue [Manimaran and Murthy, 1998]. When faced with multiple tasks to be scheduled, the scheduler can either assign them one by one (without any concern for how the scheduling of one task may aﬀect the schedulability of others) or use some backtracking strategy. This strategy checks if scheduling one task creates constraints that make it impossible to schedule some other task; if so, it backtracks and tries to revise the schedule of the ﬁrst task to relax such a constraint.
Another variation consists of the classiﬁcation of backup tasks into passive and active. A passive task is constrained to execute within the interval between the ﬁnishing time of its primary and its deadline. If this interval is very short, then the available slack may not be suﬃcient to obtain a feasible schedule in many cases. Hence, if a passive backup cannot be feasibly scheduled, the algorithm might consider reclassifying it as active; this immediately relaxes the constraint that the backup be scheduled entirely after the scheduled ﬁnishing time of its primary. The algorithm can then make another attempt to assign it.
Further, note that we are assuming that an active backup needs to continue executing through to completion. We do need to start such a backup before we know whether or not its primary has failed; however, if such information becomes available before its active backup has ﬁnished executing, the backup can safely be aborted, thus yielding additional slack in the schedule. We can also split what would have been an active backup into two parts: the part that is scheduled for before the ﬁnish time of its primary and the rest. The former can remain designated an active backup while the latter can be made passive. An approach along these lines is outlined in [Tsuchiya, et al., 1995a, Tsuchiya, et al., 1995b].
In the approach covered above, any processor which does not carry the primary is a candidate for being allocated the backup. An alternative that has been suggested is that processors be organized into multiple groups with the proviso that both the primary and the backup must be allocated to processors within the same group [Al-Omari, et al. 2001]. Groups may be formed either statically or dynamically; dynamic groups oﬀer somewhat better guarantee rates.
Finally, there is the use of checkpointing [Ahn, et al. 1997, Speirs and Barrett, 1989]. A real-time task can checkpoint as it goes. Every so often, it records its state. If its processor should fail and the checkpoint is preserved by putting it in safe place, the backup can resume execution not from the beginning but from the latest checkpoint. Evaluation of such an approach should include the overhead for taking checkpoints.
6.2 Aperiodic and Non-Preemptive Tasks We now turn to scheduling a workload of aperiodic and non-preemptive tasks [Ghosh, et al., 1997].
Here, tasks arrive dynamically and the system has to build its schedule as it goes along. Since the workload is not known in advance, it cannot be checked for schedulability. Instead, when a task arrives (along with information about its worst-case execution time, and its deadline), the system determines if it has enough time to guarantee its execution. If so, the task is accepted;
if not, the task is rejected, and is no longer its responsibility.
As before, we use backup copies for fault-tolerance: the system will not guarantee a task unless it can feasibly schedule both its primary and backup.
The algorithm starts by scheduling the primary copy of the incoming task. As before, one can use a ﬁrst-ﬁt approach to choose the processor that will be allocated the primary. Alternatively, some other order may be chosen in which to try the processors. If we ﬁnd a processor that can feasibly schedule this primary, we try to identify a processor that can feasibly schedule its backup according to Principles A1 to A3 listed in Section 1. We evaluate the goodness of the backup scheduling on each of the processors (except, obviously, the one that has been assigned the primary) according to a ﬁgure-of-merit function which we will describe next. The backup is assigned to whichever processor maximizes this ﬁgure-of-merit. If no such processor is found, we have to look for some other processor which can accept the primary (and satisfying A1 to A3) and repeat this process to ﬁnd a home for its backup. If we are unable to ﬁnd such a pair of processors for the primary and backup copies, the system rejects the task.
The ﬁgure-of-merit mentioned in the algorithm arises because there are two, often contradictory, impulses driving the scheduling of the backup. One is to schedule the backup as late as possible. This is important because the backup can be deallocated once the primary succeeds;
having a long interval between when the primary succeeds and when the backup was scheduled to start gives the system a better opportunity to ﬁnd something else to ﬁll the slot vacated by the backup. The second impulse is to exploit the conditional transparency of backups and maximize the overlap between this backup and any others that may already be scheduled. Quite often, maximizing the overlap may lead us to schedule the backup for earlier than we otherwise might; while delaying the backup by as long as possible may reduce the overlap that we may otherwise be able to exploit.
This issue can be resolved by creating a ﬁgure-of-merit, composed of a weighted sum of the
F = α(tprimaryfinish − tbackupstart) + (1 − α)overlap length (12) where α ∈ [0, 1] is a tuning parameter. Users may experiment with various tuning parameters for the type of workloads they anticipate in order to pick a suitable one.
6.3 Integrating Task Cost Functions
We present now a dynamic programming approach [Krishna and Shin, 1986]. This is an oﬄine technique, in which two schedules are constructed for each processor. The ﬁrst is the backup schedule and the second a primary schedule. In the absence of faults, the primary schedule is executed. When a backup needs to be activated, this is done according to the backup schedule, with primary tasks having to give way to the backups. The primary schedule is constructed by invoking a dynamic programming algorithm, taking into account the notiﬁcation time of each backup, i.e., the time by which the system will be made aware of the need to execute that backup.
This dynamic programming approach allows the user to introduce cost functions for the various tasks. That is, the aim is not just to meet all real-time deadlines; in addition, each task Ti has a cost function Fi(Ri) of its response time, Ri, which represents the cost to the system of having such a response time. Such cost functions are relevant when the computer is in the control of some cyber-physical control system. In such a case, the computer is in the feedback loop of the controlled process and any incremental delay of the controller potentially contributes to a degradation in the quality of control provided. Such degradation is captured in the form of cost functions. It is beyond the scope of this paper to describe how these functions may be obtained: see [Krishna and Shin, 1987, Shin and Cui, 1995, Shin and Krishna, 1987] for ways by which the control dynamics of the controlled process can translate into cost functions.
Such cost functions can be used to calculate the total cost of a schedule: this is given by Fi(Ri).
i As a foundation upon which to construct fault-tolerant schedules, the dynamic programming approach can use any scheduling algorithm which consist of a task assignment part (Algorithm Alloc) and a uniprocessor scheduling part (Algorithm Sched) which is responsible for scheduling on each processor the tasks assigned to it by Alloc. Both Alloc and Sched may take both task deadlines and cost functions into account: they are heuristics which seek to reduce the total cost of the schedule while ensuring that all deadlines are met. These heuristics are not the focus of our discussion; rather, we are concerned with how they can be used as subroutines to obtain fault-tolerant schedules. That is, our focus is the fault-tolerant component which calls these subroutines.
The tasks assigned to a processor are numbered in order of their notiﬁcation time. In what follows, we will concentrate on showing how to schedule tasks on some processor, P: the same activity will be carried out independently for every other processor in the system. Denote by Pζ(1), Pζ(2), · · ·, Pζ(θ) the θ primaries and by Bψ(1), Bψ(2), · · ·, Bψ(γ) the γ backups assigned to processor P, respectively, where ζ(i) and ψ(i) denote the tasks whose primaries and backups are assigned to P, respectively. The backup task cost functions are all zero: the focus of their scheduling is on meeting deadlines.
Once a processor has been assigned a set of primary tasks, the holes in its schedule can be identiﬁed. A hole is a interval of time in which it is impossible to schedule any of the primaries allocated to that processor due to their release times and deadlines. For example, if we have a processor assigned a single aperiodic task whose release time is r and absolute deadline is d, then the following intervals are holes created by that task: [0, r) and (d, ∞). The hole resulting from a set of tasks is the intersection of the holes induced by each of them. Holes are important in that backups can be scheduled on them without aﬀecting the primary schedule. Assume that the set of primaries and backups assigned to a given processor are denoted by P and B, respectively.
We can improve the eﬃciency of the scheme by tuning Algorithm Sched to schedule backups in the holes to the extent possible and to allow it to overlap backups according to Principle A2. Let νBψ(1), νBψ(2), · · ·, νBψ(γ) be the notiﬁcation times of backups respectively assigned to that processor. For convenience, set νbψ (0) = 0, and νbψ(γ+1) = ∞. The algorithm generates a sequence of γ + 1 primary schedules, Sp0, Sp1, · · ·, Spγ, and then pieces them together.
The algorithm is shown in Figure 7. In Step 1, the task allocation algorithm, Alloc, is called, to assign tasks to processors. Such an assignment speciﬁes the holes in the schedule of each processor.
In Step 2, the uniprocessor scheduling algorithm is executed on a task set comprising the primaries and all the backups. The position of the backups in this schedule is recorded in a backup schedule, SB. The position of the primaries in the schedule is recorded in schedule Sp0.
In Step 5 (some auxiliary steps are taken in Steps 3 and 4), we move to the ﬁrst notiﬁcation time, νBψ(1). By this time, the system will know whether or not the primary (on some other processor) associated with backup Bψ(1) has failed. If not, then there is no need to reserve space in the schedule for backup Bψ(1): any space reserved for Bψ(1) beyond time νψ(1) in Sb can be released. We run algorithm Sched on a workload comprising the primary workload not scheduled over [0, νbψ(1) ]. Such scheduling is done based on the assumption that the processor is not available to the primaries over the periods occupied by backups in Sb. The schedule of tasks is obtained and recorded as Sp1.
We do the same thing with respect to each of the remaining notiﬁcation times as we proceed through the Step 5 loop. After exiting this loop, in Step 6, we schedule any remaining primary workload and end the algorithm.
The output of the algorithm is a backup schedule and and a set of primary schedules, Sp1, Sp2, · · ·, Spγ.
1. Record the holes as defined by the task allocation.
6. If all the primary workload has not yet been scheduled, schedule the remaining primary workload beyond νBψ(γ).
If any primary task cannot be scheduled to finish before its deadline, declare failure and exit.
Figure 7: Dynamic Programming Fault-Tolerant Scheduling Algorithm
Figure 8: Example of Schedules Followed by Dynamic Programming Algorithm
During operation, we use these schedules as a template as follows in the absence of any faults:
over the interval [νBψ(i), νBψi+1 ), we execute primaries according to schedule Spi. If backup bi is the ﬁrst one to have to be activated, the machine will follow Spi throughout and never switch to Spi+1. This is illustrated in Figure 8.
To illustrate this algorithm, consider the following example. Assume that primaries of aperiodic tasks T1, T2, T3 and T4, and backups of aperiodic tasks T5, T6, T7 and T8 have been assigned to some processor. Assume also (just for this example) that the execution time of the primary and backup copies of a task are the same and that the backups are not allowed to overlap since their primaries have been assigned to the same processor. We now show how a schedule for that processor is constructed.
We ﬁrst set up the schedule of backups: for this, schedule the entire primary and backup tasks and record the position of the backups in this schedule. Next, we list the positions of the primaries in this schedule: this becomes contingency schedule Sp0. Note that because of deadline considerations, we are forced to run T4 ahead of T1, even though it would incur less cost to do T1 ﬁrst. Similarly, we are forced to execute T3 before T2.
We now deal with what happens once we are notiﬁed that the backup of T6 will not have to be activated: this removes the need to reserve time in the schedule for T5. This information becomes available at time ν4 = 0. Once the need is removed to reserve the interval [8, 23] for the T5 backup, we now have the time to run task T1 ﬁrst and then T4. This is contingency schedule Sp1.