A Fault-Tolerant Dynamic Scheduling Algorithm for Multiprocessor Real-Time Systems and Its Analysis.
AbstractMany time-critical applications require dynamic scheduling with predictable performance. Tasks corresponding to these applications have deadlines to be met despite the presence of faults. In this paper, we propose an algorithm to dynamically schedule arriving real-time tasks with resource and fault-tolerant requirements on to multiprocessor systems. The tasks are assumed to be nonpreemptable and each task has two copies (versions) which are mutually excluded in space, as well as in time in the schedule, to handle permanent processor failures and to obtain better performance, respectively. Our algorithm can tolerate more than one fault at a time, and employs performance improving techniques such as 1) distance concept which decides the relative position of the two copies of a task in the task queue, 2) flexible backup overloading, which introduces a trade-off between degree of fault tolerance and performance, and resource reclaiming, which reclaims resources both from deallocated backups and early completing tasks. We quantify, through simulation studies, the effectiveness of each of these techniques in improving the guarantee ratio, which is defined as the percentage of total tasks, arrived in the system, whose deadlines are met. Also, we compare through simulation studies the performance our algorithm with a best known algorithm for the problem, and show analytically the importance of distance parameter in fault-tolerant dynamic scheduling in multiprocessor real-time systems.
Introduction
Real-time systems are defined as those systems in which the correctness of the system depends not only
on the logical result of computation, but also on the time at which the results are produced [22]. Real-
This work was supported by the Indian National Science Academy, and the Department of Science and Technology.
time systems are broadly classified into three categories, namely, (i) hard real-time systems, in which the
consequences of not executing a task before its deadline may be catastrophic, (ii) firm real-time systems,
in which the result produced by the corresponding task ceases to be useful as soon as the deadline expires,
but the consequences of not meeting the deadline are not very severe, and (iii) soft real-time systems,
in which the utility of results produced by a task with a soft deadline decreases over time after the
deadline expires [25]. Examples of hard real-time systems are avionic control and nuclear plant control.
Online transaction processing applications such as airline reservation and banking are examples for firm
real-time systems, and telephone switching system and image processing applications are examples for
soft real-time systems.
The problem of scheduling of real-time tasks in multiprocessor systems is to determine when and on
which processor a given task executes [22, 25]. This can be done either statically or dynamically. In
static algorithms, the assignment of tasks to processors and the time at which the tasks start execution
are determined a priori. Static algorithms are often used to schedule periodic tasks with hard deadlines.
However, this approach is not applicable to aperiodic tasks whose characteristics are not known a priori.
Scheduling such tasks require a dynamic scheduling algorithm.
In dynamic scheduling, when a new set of tasks (which correspond to a plan) arrive at the system, the
scheduler dynamically determines the feasibility of scheduling these new tasks without jeopardizing the
guarantees that have been provided for the previously scheduled tasks. A plan is typically a set of actions
that has to be either done fully or not at all. Each action could correspond to a task and these tasks
may have resource requirements, and possibly may have precedence constraints. Thus, for predictable
executions, schedulability analysis must be done before a task's execution is begun. For schedulability
analysis, tasks' worst case computation times must be taken into account. A feasible schedule is generated
if the timing constraints, and resource and fault-tolerant requirements of all the tasks in the new set can
be satisfied, i.e., if the schedulability analysis is successful. If a feasible schedule cannot be found, the
new set of tasks (plan) is rejected and the previous schedule remains intact. In case of a plan getting
rejected, the application might invoke an exception task, which must be run, depending on the nature
of the plan. This planning allows admission control and results in reservation-based system. Tasks are
dispatched according to this feasible schedule. Such a type of scheduling approach is called dynamic
planning based scheduling [22], and Spring kernel [27] is an example for this. In this paper, we use
dynamic planning based scheduling approach for scheduling of tasks with hard deadlines.
The demand for more and more complex real-time applications, which require high computational
needs with timing constraints and fault-tolerant requirements, have led to the choice of multiprocessor
systems as a natural candidate for supporting such real-time applications, due to their potential for high
performance and reliability. Due to the critical nature of the tasks in a hard real-time system, it is
essential that every task admitted in the system completes its execution even in the presence of failures.
Therefore, fault-tolerance is an important issue in such systems. In real-time multiprocessor systems,
fault-tolerance can be provided by scheduling multiple versions of tasks on different processors. Four
different models (techniques) have evolved for fault-tolerant scheduling of real-time tasks, namely, (i)
Triple Modular Redundancy (TMR) model [12, 25], (ii) Primary Backup (PB) model [3], (iii) Imprecise
Computational (IC) model [11], and (iv) (m; k)-firm deadline model [23].
In the TMR approach, three versions of a task are executed concurrently and the results of these
versions are voted on. In the PB approach, two versions are executed serially on two different processors,
and an acceptance test is used to check the result. The backup version is executed (after undoing the
effects of primary version) only if the output of the primary version fails the acceptance test, either
due to processor failure or due to software failure. In the IC model, a task is divided into mandatory
and optional parts. The mandatory part must be completed before the task's deadline for acceptable
quality of result. The optional part refines the result. The characteristics of some real-time tasks can be
better characterised by (m; k)-firm deadlines in which m out of any k consecutive tasks must meet their
deadlines. The IC model and (m; k)-firm task model provide scheduling flexibility by trading off result
quality to meet task deadlines.
Applications such as automatic flight control and industrial process control require dynamic scheduling
with fault-tolerant requirements. In a flight control system, the controllers often activate tasks depending
on what appears on their monitor. Similarly, in an industrial control system, the robot which monitors
and controls various processes may have to perform path planning dynamically which results in activation
of aperiodic tasks. Another example, taken from [3], is a system which monitors the condition of several
patients in the intensive care unit (ICU) of a hospital. The arrival of patients to the ICU is dynamic.
When a new patient (plan) arrives, the system performs admission test to determine whether the new
patient (plan) can be admitted or not. If not, alternate action like employing a nurse can be carried out.
The life criticality of such an application demands that the desired action to be performed even in the
presence of faults.
In this paper, we address the scheduling of dynamically arriving real-time tasks with PB fault-tolerant
requirements on to a set of processors and resources in such a way that the versions of the tasks are
feasible in the schedule. The objective of any dynamic real-time scheduling algorithm is to improve the
guarantee ratio [24] which is defined as the percentage of tasks, arrived in the system, whose deadlines
are met.
The rest of the paper is structured as follows. Section 2 discusses the system model. In Section 3,
related work and motivations for our work are presented. In Section 4, we propose an algorithm for
fault-tolerant scheduling of real-time tasks, and also propose some enhancements to it. In Section 5, the
performance of the proposed algorithm together with its enhancements is studied through simulation,
and also compared with an algorithm proposed recently in [3]. Finally, in Section 6, we make some
concluding remarks.
System Model
In this section, we first present the task model, followed by scheduler model, and then some definitions
which are necessary to explain the scheduling algorithm.
2.1 Task Model
1. Tasks are aperiodic, i.e., the task arrivals are not known a priori. Every task T i has the attributes:
arrival time (a i ), ready time (r i ), worst case computation time
2. The actual computation time of a task T i , denoted as c i , may be less than its worst case computation
time due to the presence of data dependent loops and conditional statements in the task code, and
due to architectural features of the system such as cache hits and dynamic branch prediction.
The worst case execution time of a task is obtained based on both static code analysis and the
average of execution times under possible worst cases. There might be cases in which the actual
computation time of a task may be more than its worst case computation time. There are techniques
to handle such situations. One such technique is "Task Pair" scheme [28] in which the worst case
computation time of a task is added with the worst case computation time of an exception task.
If the actual computation time exceeds the (original) worst case computation time, the exception
task is invoked.
3. Resource constraints: A task might need some resources such as data structures, variables, and
communication buffers for its execution. Each resource may have multiple instances. Every task
can have two types of accesses to a resource: a) exclusive access, in which case, no other task can
use the resource with it or b) shared access, in which case, it can share the resource with another
task (the other task also should be willing to share the resource). Resource conflict exists between
two tasks T i and T j if both of them require the same resource and one of the accesses is exclusive.
4. Each task T i has two versions, namely, primary copy and backup copy. The worst case computation
time of a primary copy may be more than that of its backup. The other attributes and resource
requirements of both the copies are identical.
5. Each task encounters at most one failure either due to processor failure or due to software failure,
i.e., if the primary fails, its backup always succeeds.
6. Tasks are non-preemptable, i.e., when a task starts execution on a processor, it finishes to its
completion.
7. Tasks are not parallelizable, which means that a task can be executed on only one processor. This
necessitates the sum of worst case computation times of primary and backup copies should be less
than or equal to (d that both the copies of a task can be schedulable within this interval.
8. The system has multiple identical processors which are connected through a shared medium.
9. Faults can be transient or permanent, and are independent, i.e., correlated failures are not considered

10. There exists a fault-detection mechanism such as acceptance tests to detect both processor failures
and software failures.
Most complex real-time applications have both periodic and aperiodic tasks. The dynamic planning
based scheduling approach used in this paper is also applicable to such real-time applications as described
below. The system resources (including processors) are partitioned into two sets, one for periodic tasks
and the other for aperiodic tasks. The periodic tasks are scheduled by a static table-driven scheduling
approach [22] onto the resource partition corresponding to periodic tasks and the aperiodic tasks are
scheduled by a dynamic planning based scheduling approach [21, 22, 13] onto the resource partition
corresponding to aperiodic tasks.
Tasks may have precedence constraints. Ready times and deadlines of tasks can be modified such
that they comply with the precedence constraints among them. Dealing with precedence constraints
is equivalent to working with the modified ready times and deadlines [11]. Therefore, the proposed
algorithm can also be applied to tasks having precedence constraints among them.
2.2 Scheduler Model
In a dynamic multiprocessor scheduling, all the tasks arrive at a central processor called the scheduler,
from where they are distributed to other processors in the system for execution. The communication
between the scheduler and the processors is through dispatch queues. Each processor has its own dispatch
queue. This organization, shown in Fig.1, ensures that the processors will always find some tasks (if there
are enough tasks in the system) in the dispatch queues when they finish the execution of their current
tasks. The scheduler will be running in parallel with the processors, scheduling the newly arriving tasks,
and periodically updating the dispatch queues. The scheduler has to ensure that the dispatch queues
are always filled to their minimum capacity (if there are tasks left with it) for this parallel operation.
This minimum capacity depends on the worst case time required by the scheduler to reschedule its tasks
upon the arrival of a new task [24]. The scheduler arrives at a feasible schedule based on the worst case
computation times of tasks satisfying their timing, resource, and fault-tolerant constraints.
The use of one scheduler for the whole system makes the scheduler a single point of failure. The
scheduler can be made fault-tolerant by employing modular redundancy technique in which a backup
scheduler runs in parallel with the primary scheduler and both the schedulers perform an acceptance
test. The dispatch queues will be updated by one of the schedulers which passes the acceptance test. A
simple acceptance test for this is to check whether each task in the schedule finishes before its deadline
satisfying its requirements.
tasks
Task queue
Current schedule
dispatch queues
Dispatch queues
(Feasible schedule) Processors
Scheduler
Min. length of
P2Fig.1 Parallel execution of scheduler and processors
2.2.1 Resource Reclaiming
Resource reclaiming [24] refers to the problem of utilizing resources (processors and other resources) left
unused by a task (version) when: (i) it executes less than its worst case computation time, or (ii) it is
deleted from the current schedule. Deletion of a task version takes place when extra versions are initially
scheduled to account for fault tolerance, i.e., in the PB fault-tolerant approach, when the primary version
of a task completes its execution successfully, there is no need for the temporally redundant backup
version to be executed and hence it can be deleted.
Each processor invokes a resource reclaiming algorithm at the completion of its currently executing
task. If resource reclaiming is not used, processors execute tasks strictly based on the scheduled start
times as per the feasible schedule, which results in making the resources remain unused, thus reducing the
guarantee ratio. The scheduler is informed with the time reclaimed by the reclaiming algorithm so that
the scheduler can schedule the newly arriving tasks correctly and effectively. A protocol for achieving this
is suggested in [24]. Therefore, any dynamic scheduling scheme should have a scheduler with associated
resource reclaiming.
3 Background
In this section, we first discuss the existing work on fault-tolerant scheduling, and then highlight the
limitations of these works which form the motivation for our work.
3.1 Related Work
Many practical instances of scheduling problems have been found to be NP-complete [2], i.e., it is
believed that there is no optimal polynomial-time algorithm for them. It was shown in [1] that there
does not exist an algorithm for optimally scheduling dynamically arriving tasks with or without mutual
exclusion constraints on a multiprocessor system. These negative results motivated the need for heuristic
approaches for solving the scheduling problem.
Recently, many heuristic scheduling algorithms [21, 13] have been proposed to dynamically schedule
a set of tasks whose computation times, deadlines, and resource requirements are known only on arrival.
For multiprocessor systems with resource constrained tasks, a heuristic search algorithm, called myopic
scheduling algorithm, was proposed in [21]. The authors of [21] have shown that the integrated heuristic
used there which is a function of deadline and earliest start time of a task performs better than simple
heuristics such as earliest deadline first, least laxity first, and minimum processing time first.
In [10], a PB scheme has been proposed for preemptively scheduling periodic tasks in a uniprocessor
system. This approach guarantees that (i) a primary copy meets its deadline if there is no failure and
(ii) its backup copy will run by the deadline if there is a failure. To achieve this, it precomputes tree
of schedules (where the tree can be encoded within a table-driven scheduler) by considering all possible
failure scenarios of tasks. This scheme is applicable to simple periodic tasks, where the periods of the
tasks are multiples of the smallest period. The objective of this approach is to increase the number of
primary task executions.
Another PB scheme is proposed in [19] for scheduling periodic tasks in a multiprocessor system. In
this strategy, a backup schedule is created for each set of tasks in the primary schedule. The tasks are
then rotated such that primary and backup schedules are on different processors and they do not overlap.
This approach tolerates up to one failure in the worst case, by using double the number of processors
used in the corresponding non-fault-tolerant schedule.
In [7], processor failures are handled by maintaining contingency or backup schedules. These schedules
are used in the event of a failure. The backup schedules are generated assuming that an optimal
schedule exists and the schedule is enhanced with the addition of "ghost" tasks, which function primarily
as standby tasks. The addition of tasks may not be possible in some schedules.
A PB based algorithm with backup overloading and backup deallocation has been proposed recently
[3] for fault-tolerant dynamic scheduling of real-time tasks in multiprocessor systems, which we call as
backup overloading algorithm. The backup overloading algorithm allocates more than a single backup in
a time interval (where time interval of a task is the interval between scheduled start time and scheduled
finish time of the task) and deallocates the resources unused by the backup copies in case of fault-free
operation. Two or more backups can overlap in the schedule (overloading) of a processor, if the primaries
of these backups are scheduled on different processors. The concept of backup overloading is valid under
the assumption that there can be at most one fault at any instant of time in the entire system. In [3],
it was shown that backup deallocation is more effective than the backup overloading. The paper also
provides a mechanism to determine the number of processors required to provide fault-tolerance in a
dynamic real-time system. Discussion about other related work on fault-tolerant real-time scheduling
can be found in [3].
3.2 Motivations for Our Work
The algorithms discussed in [7, 19] are static algorithms and cannot be applied to dynamic scheduling,
considered in this paper, due to their high complexities. The algorithm discussed in [10] is for scheduling
periodic tasks in uniprocessor systems and cannot be extended to the dynamic scheduling as it expects
the tasks to be periodic. Though the algorithm proposed in [3] is for dynamic scheduling, it does not
consider resource constraints among tasks which is a practical requirement in any complex real-time
system, and assumes at most one failure at any instant of time, which is pessimistic.
The algorithm in [3] is able to deallocate a backup when its primary is successful and uses this
reclaimed (processor) time to schedule other tasks in a greedy manner. The resource reclaiming in such
systems is simple and is said to be work-conserving which means that it never leaves a processor idle
if there is a dispatchable task. But, resource reclaiming on multiprocessor systems with resource constrained
tasks is more complicated. This is due to the potential parallelism provided by a multiprocessor
and potential resource conflicts among tasks. When the actual computation time of a task differs from
its worst case computation time in a non-preemptive multiprocessor schedule with resource constraints,
run-time anomalies may occur [4] if a work-conserving reclaiming scheme is used. These anomalies may
cause some of the already guaranteed tasks to miss their deadlines. In particular, one cannot use a work-conserving
scheme for resource reclaiming from resource constrained tasks. Moreover, the algorithm
proposed in [3] does not reclaim resources when the actual computation times of tasks are less than their
worst case computation times, which is true for many tasks. But, resource reclaiming in such cases is
very effective in improving the guarantee ratio [24].
The Spring scheduling approach [27] schedules dynamically arriving tasks with resource requirements
and reclaims resources from early completing tasks and does not address the fault-tolerant requirements
explicitly.
Our algorithm works within the Spring scheduling approach and builds fault-tolerant solutions around
it to support PB based fault-tolerance. To the best of our knowledge, ours is the first work which addresses
the fault-tolerant scheduling problem in a more practical model, which means that our algorithm
handles resource constraints among tasks and reclaims resources both from early completing tasks and
deallocated backups. The performance of our algorithm is compared with the backup overloading algorithm
in Section 5.5.
4 The Fault-tolerant Scheduling Algorithm
In this section, we first define some terms and then present our fault-tolerant scheduling algorithm which
uses these terms.
4.1 Terminology
1: The scheduler fixes a feasible schedule S. The feasible schedule uses the worst case
computation time of a task for scheduling it and ensures that the timing, resource, and fault-tolerant
constraints of all the tasks in S are met. A partial schedule is one which does not contain all the tasks.
Definition 2: st(T i ) is the scheduled start time of task T i which satisfies r
the scheduled finish time of task T i which satisfies r
Definition 3: EAT s
k ) is the earliest time at which the resource R k becomes available for shared
(exclusive) usage [21].
Definition 4: Let P be the set of processors, and R i be the set of resources requested by task T i . Earliest
start time of a task T i , denoted as EST(T i ), is the earliest time when its execution can be started, which
is defined as: EST (T i
denotes the time at which the processor P j is available for executing a task, and the third term denotes
maximum among the available time of the resources requested by task T i , in which shared
mode and exclusive mode.
Definition 5: proc(T i ) is the processor to which task T i is scheduled. The processor to which task T i
should not get scheduled is denoted as exclude proc(T i ).
Definition is the scheduled start time and f t(Pr i ) is the scheduled finish time of primary copy
of a task T i . Similarly, st(Bk i ) and f t(Bk i ) denote the same for the backup copy of T i .
Definition 7: The primary and backup copies of a task T i are said to be mutually exclusive in time,
denoted as time exclusion(T i
Definition 8: The primary and backup copies of a task T i are said to be mutually exclusive in space,
denoted as space exclusion(T i
A task is said to be feasible in a fault-tolerant schedule if it satisfies the following conditions:
ffl The primary and backup copies of a task should satisfy: r i - st(Pr
This is because both the copies of a task must satisfy the timing constraints and it is assumed
that the backup is executed after the failure in its primary is detected (time exclusion). Failure
detection is done through acceptance test or some other means only at the completion of every
primary copy. The time exclusion between primary and backup copies of a task can be relaxed
if the backup is allowed to execute in parallel [5, 30] (or overlap) with its primary. This is not
preferable in dynamic scheduling as discussed below.
ffl Primary and backup copies of a task should mutually exclude in space in the schedule. This is
necessary to tolerate permanent processor failures.
Mutual exclusion in time is very useful from the resource reclaiming point of view. If the primary
is successful, the backup need not be executed and the time interval allocated to the backup can be
reclaimed fully, if primary and backup satisfy time exclusion, thereby improving the schedulability [15].
In other words, if primary and backup of a task overlap in execution, the backup unnecessarily executes
(in part or full) even when its primary is successful. This would result in poor resource utilization,
thereby reducing the schedulability. Moreover, overlapping of primary and backup of a task introduces
resource conflicts (if the access is exclusive) among them since they have the same resource requirements
and forces them to exclude in time if only one instance of the requested resource is available at that time.
4.2 The Distance Myopic Algorithm
The Spring scheduling [27] approach uses a heuristic search algorithm (called myopic algorithm [21])
for non-fault-tolerant scheduling of resource constrained real-time tasks in a multiprocessor system, and
uses Basic or Early start algorithms for resource reclaiming. One of the objectives of our work here
is to propose fault-tolerant enhancements to the Spring scheduling approach. We make the following
enhancements to the Spring scheduling to support PB based fault-tolerance:
ffl a notion of distance is introduced, which decides the relative difference in position between primary
and backup copies of a task in the task queue.
ffl flexible level of backup overloading; this introduces a tradeoff between number of faults in the
system and the system performance.
ffl use of restriction vector (RV) [15] based algorithm to reclaim resources from both deallocated
backups and early completing tasks.
4.2.1 Notion of Distance
Since in our task model, every task, T i , has two copies, we place both of them in the task queue with
relative difference of Distance(Pr positions. The primary copy of any task always precedes
its backup copy in the task queue. Let n be the number of currently active tasks whose characteristics
are known. The algorithm does not know the characteristics of new tasks, which may arrive, while
scheduling the currently active tasks. The distance is an input parameter to the scheduling algorithm
which determines the relative positions of the copies of a task in the task queue in the following way:
distance for the first (n \Gamma (n mod distance)) tasks
mod distance for the last (n mod distance) tasks,
The following is an example task queue with assuming that the deadlines of
tasks are in the non-decreasing order.
The positioning of backup copies in the task queue relative to their primaries can easily be achieved
with minimal cost: (i) by having two queues, one for primary copies (n entries) and the other for backup
copies (n entries), and (ii) merging these queues, before invoking the scheduler, based on the distance
value to get a task queue of 2n entries. The cost involved due to merging is 2n.
4.2.2 Myopic Scheduling Algorithm
The myopic algorithm [21] is a heuristic search algorithm that schedules dynamically arriving real-time
tasks with resource constraints. It works as follows for scheduling a set of tasks. A vertex in the search
tree represents a partial schedule. The schedule from a vertex is extended only if the vertex is strongly
feasible. A vertex is strongly feasible if a feasible schedule can be generated by extending the current
partial schedule with each task of the feasibility check window. Feasibility check window is a subset of
first K unscheduled tasks. Larger the size of the feasibility check window, higher the scheduling cost and
more the look ahead nature. If the current vertex is strongly feasible, the algorithm computes a heuristic
function, for each task within the feasibility check window, based on deadline and earliest start time of
the task. It then extends the schedule by the task having the best (smallest) heuristic value. Otherwise,
it backtracks to the previous vertex and then the schedule is extended from there using a task which has
the next best heuristic value.
4.2.3 The Distance Based Fault-tolerant Myopic Algorithm
We make fault-tolerant extensions to the original myopic algorithm using the distance concept for scheduling
a set of tasks. Here, we assume that each task is a plan. The algorithm attempts to generate a feasible
schedule for the task set with minimum number of rejections.
Distance Myopic()
1. Order the tasks (primary copies) in non-decreasing order of deadlines in the task queue and insert
the backup copies at appropriate distance from their primary copies.
2. Compute Earliest Start Time EST (T i ) for the first K tasks, where K is the size of the feasibility
check window.
3. Check for strong feasibility: check whether EST (T i is true for all the K tasks.
4. If strongly feasible or no more backtracking is possible
(a) Compute the heuristic function for the first K tasks, where W is an
input parameter.
ffl When Bk i of task T i is considered for H function evaluation, if Pr i is not yet scheduled,
set EST (Bk i
(b) Choose the task with the best (smallest) H value to extend the schedule.
(c) If the best task meets its deadline, extend the schedule by the best task (best task is accepted
in the schedule).
ffl If the best task is primary copy (Pr i ) of task T i
This is to achieve time exclusion for task T i .
This is to achieve space exclusion for task T i .
(d) else reject the best task and move the feasibility check window by one task to the right.
(e) If the rejected task is a backup copy, delete its primary copy from the schedule.
5. else Backtrack to the previous search level and try extending the schedule with a task having the
next best H value.
6. Repeat steps (2-5) until termination condition is met.
The termination condition is either (i) all the tasks are scheduled or (ii) all the tasks are considered
for scheduling and no more backtrack is possible. The complexity of the algorithm is the same the
original myopic algorithm, which is O(Kn).
It is to be noted that the distance myopic algorithm can tolerate more than one fault at any point
of time, and the number of faults is limited by the assumption that at most one of the copies of a task
can fail. Once a processor fault is detected, the recovery is inherent in the schedule meaning that the
backups, of the primaries scheduled on the failed processors, will always succeed. In addition, whether
the failed processors will be considered or not for further scheduling depends on the type of fault. If it is
a transient processor fault, the processor on which the failure has occurred will be considered for further
scheduling. On the other hand, if it is a permanent processor fault, the processor on which the failure
has occurred will not be considered for further scheduling till it gets repaired. If the failure is due to
task error (software fault), it is treated like a transient processor fault.
4.2.4 Flexible Backup Overloading in Distance Myopic
Here, we discuss as how to incorporate flexible level of backup overloading into the distance myopic
algorithm. This introduces a tradeoff between the number of faults in the system and the guarantee
ratio. Before, defining the flexible backup overloading, we state from [3] the condition under which
backups can be overloaded.
If Pr i and Pr j are scheduled on two different processors, then their backups Bk i and Bk j can overlap
in execution on a processor:
The backup overloading is depicted in Fig.2. In Fig.2, Bk 1 and Bk 3 which are scheduled on processor
in execution, whose primaries Pr 1 and Pr 3 are scheduled on different processors P 1 and P 3 ,
respectively. This backup overloading is valid under the assumption that there is at most one failure, in
the system (at any instant of time). This is a too pessimistic assumption especially when the number of
processors in the system is large.
Processor 1
Processor 2
Processor 3
Primary 1
Primary 2 Primary 4
Primary 3
Time
Backups 1 and 3
Fig.2 Backup overloading
We introduce flexibility in overloading (and hence the number of faults) by forming the processors
into different groups. Let group(P i ) denote the group in which processor P i is a member, and m be the
number of processors in the system. The rules for flexible backup overloading are:
Every processor is a member of exactly one group.
ffl Each group should have at least three processors for backup overloading to take place in that
group.
ffl Size of each group (gsize) is the same, except for one group, when (m=gsize) is not an integer.
ffl Backup overloading can take place only among the processors in a group:
ffl Both primary and backup copies of a task are to be scheduled on to the processors of the same
group.
The flexible overloading scheme permits at most d(m=gsize)e number of faults at any instant of time,
with a restriction that there is at most one fault in each group. In the flexible overloading scheme, when
the number of faults permitted is increased, the flexibility in backup overloading is limited and hence
the guarantee ratio might drop down. This mechanism gives the flexibility for the system designer to
choose the desired degree of fault-tolerance. In Section 5.2.5, we study the tradeoff between the number
of faults and the performance of the system.
4.2.5 Restriction Vector Based Resource Reclaiming
In our dynamic fault-tolerant scheduling approach, we have used restriction vector (RV) algorithm for
resource reclaiming. RV algorithm uses a data structure called restriction vector which captures resource,
precedence, and fault-tolerant constraints among tasks in a unified way. Each task T i has an associated
m-component vector, RV i [1::m], called Restriction Vector, where m is the number of processors in the
system. RV i [j] for a task T i contains the last task in T !i (j), where T !i (j) is the set of tasks which
are scheduled to finish before T i begins. Before updating the dispatch queues, the scheduler computes
the restriction vector for each of the tasks in the feasible schedule. For computing RV of a task T i , the
scheduler checks at most k tasks (in the order of latest finish time first) which are scheduled to finish on
other processors before T i starts execution. The latest task on processor j which has resource conflict or
precedence relation with the task T i becomes RV i [j]. If no such task exists, then the k-th task is RV i [j].
The RV algorithm [15] says: start executing a task T i only if processor on which T i is scheduled is
idle and all the tasks in its restriction vector have successfully finished their execution.
Performance Studies
In this section, we first present the simulation studies on various algorithms, and then present an
analytical study based on Markov chains which highlights the importance of distance parameter in
fault-tolerant dynamic scheduling. The simulation experiments were conducted in two parts. The first
part highlights the importance of distance parameter and the second part highlights the importance of
each of the guarantee ratio improving techniques, namely, distance concept, backup deallocation, and
backup overloading. For each point in the performance curves (Figs.4-15), the total number of tasks
arrived in the system is 20,000. The parameters used in the simulation studies are given in Fig.3. The
tasks for the simulation are generated as follows:
1. The worst case computation times of primary copies are chosen uniformly between MIN C and
MAX C.
2. The deadline of a task T i (primary copy) is uniformly chosen between r
2.
3. The inter arrival time of tasks (primary copies) is exponentially distributed with mean 1=(-   m)
(MIN C +MAX C)=2.
4. The actual computation time of a primary copy is chosen uniformly between MIN C and its worst
case computation time, if aw-ratio is random (rand). Otherwise, it is aw-ratio times the worst case
computation time.
5. The backup copies are assumed to have identical characteristics of their primary copies.
parameter explanation value taken when
(varied) (fixed)
MIN C minimum computation time of tasks (-) (40)
MAX C maximum computation time of tasks (-) (80)
- task arrival rate (0.2,0.3,.,0.7) (0.5 or 0.4)
R laxity parameter (2,3,.,7) (4)
UseP probability that a task uses (0.1,0.2,.,0.5) (0.4)
a resource
ShareP probability that a task accesses (-) (0.4)
a resource in shared mode
K size of feasibility check window (1,3, ., 11) (3)
W weight of EST(T i ) in the H function (-) (1)
aw-ratio ratio of actual to worst case (0.5,0.6,.,1.0) (rand)
computation times
FaultP probability that a primary fails (0.1,0.2,.,0.5) (0.2)
distance relative difference in positions of primary (1,5,9,13) (5)
and backup copies in the task queue
m number of processors (5,6,.,10) (8)
NumRes number of resources (-) (2)
NumInst number of instances per resource (-) (2)
Fig.3 Simulation parameters
5.1 Experiments Highlighting Distance Parameter
In this section, we present the simulation results obtained for different values of distance parameter
by varying K, -, UseP , and FaultP parameters. For this study, the - value is taken as 0.5 when
fixed. The algorithms studied here reclaims resources both from early completing tasks and deallocated
backups. The actual computation time of a task is chosen uniformly between MIN C and its worst case
computation time.
5.1.1 Effect of Feasibility Check Window
Fig.4 shows the effect of varying distance for different values of K. Note that for larger values of K, the
number of H function evaluations and EST() computations are also more, which means higher scheduling
cost. The interplay between the distance and size of the feasibility check window is described below.
ffl When distance is small, the position of backup copies in the task queue is close to their respective
primary copies and hence the possibility of scheduling these backup copies may get postponed
(we call this, backup postponement) due to time and space exclusions. This makes more and more
unscheduled backup copies getting accumulated. When this number exceeds K, the scheduler is
forced to choose the best task (say T b ) among these backup copies, which results in creation of a
hole 1 in the schedule since EST(T b ) is greater than the available time (avail time) of idle processors.
This hole creation can be avoided by moving the feasibility check window till a primary task falls
into it. However, we do not consider this approach since it increases the scheduling cost.
ffl When distance is large, the position of the backup copies in the task queue is far apart from
their respective primary copies, i.e., tasks (backup copies) having lower deadlines may be placed
after some tasks (primary copies) having higher deadlines. This may lead to backtracks (and hence
rejection, if no backtrack is possible) when the feasibility check window reaches these backup copies
(we call this, forced backtrack).
The guarantee ratio increases with increasing K for a given distance for some time (growing phase)
and then starts decreasing for higher values of K (shrinking phase). From Fig.4, the shrinking phase
starts at K values 7,5,5, and 7, for distance values 1,5,9, and 13, respectively. The reason for this is
that the backup postponement is very high at the beginning of the growing phase, decreases along with
it and reaches the lowest value at the end of it (equivalently, beginning of the shrinking phase), and the
number of forced rejections is very low at the beginning of the shrinking phase and increases along with
it. This reveals two facts: (a) increased value of K (increased look ahead nature) does not necessarily
increase the guarantee ratio and (b) the optimal K for each distance is different. The right combination
of K and distance offers the best guarantee ratio. From Fig.4, the best guarantee ratio is obtained when
9. Suppose two distance values give the same (best) guarantee ratio, the one
with lower K is preferable because of lower scheduling cost.
5.1.2 Effect of Resource Usage, Task Load, and Fault Probability
In Fig.5, the probability that a task uses a resource (UseP ) is varied. For a fixed value of ShareP
(= 0.4), higher UseP means more resource conflicts among tasks. From Fig.5, it can be seen that the
guarantee ratio decreases as UseP increases. This is applicable for all values of distance. From Fig.5,
for most of the values of UseP , better guarantee ratio is obtained when distance is 9.
The task arrival rate has been varied in Fig.6. Higher - means lower inter arrival time and hence
higher task load. From Fig.6, it can be seen that increasing - decreases the guarantee ratio for all values
unusable processor time for scheduling.
of distance. From Fig.6, for most of the values of -, better guarantee ratio is obtained when distance is
5 and 9 compared to other values.
In Fig.7, the probability that a primary copy encounters a failure is varied. As FaultP increases,
the guarantee ratio decreases. This is applicable for all values of distance. From Fig.7, when distance
is 5 and 9, better guarantee ratio is obtained compared to the other values of distance.50602 4
Guarantee
ratio
Size of feasibility check window
Fig.4 Effect of feasibility check window5060708090
Guarantee
ratio
Resource usage probability
Fig.5 Effect of resource usage probability507090
Guarantee
ratio
Task arrival rate
Fig.6 Effect of task load52566064
Guarantee
ratio
Primary fault probability
Fig.7 Effect of primary fault probability
5.1.3 Choice of Distance
Based on the observations of simulation studies, a simple heuristic to select good K and distance value
is based on the number of processors, and the number of resources and their usage. If there are few
resources with high UseP and low ShareP , then there exists more resource conflicts among tasks. In
such cases, the EST() of a task is mostly decided by the resource available time rather than processor
available time or task ready time. Therefore, large value of K might help in such situations. The value
of distance may be approximately equal to a value in the range [m/2, m] since at most m consecutive
primaries or backups can be scheduled in the worst case. The value of K may be less than the distance
since larger K means higher scheduling cost, which might nullify or reduce the gain obtained.
5.2 Experiments Highlighting GR Improving Techniques
In this section, we show through simulation the importance of each of the guarantee ratio (GR) improving
techniques, namely, distance concept, backup deallocation, and backup overloading. For this
experiments, we have taken the - value to be 0.4, when fixed. The actual computation time of a task is
chosen uniformly between MIN C and its worst case computation time. The plots in Figs.8-13 correspond
to the following algorithms:
Myopic. This is a fault-tolerant version of myopic algorithm with distance = 1. This
algorithm reclaims resources only from early completing tasks.
Distance concept. This is same as algorithm A0 except that distance = 5 (this
value for distance is chosen based on the previous experiments and discussions).
deallocation. This is algorithm A1 together with resource
reclaiming from deallocated backups as well.
overloading. This is algorithm A2
together with backup overloading. For this full overloading is considered, i.e., gsize = m. This
algorithm permits at most one failure, whereas the other algorithms can tolerate more than one
failure.
The difference in guarantee ratio between algorithms: (i) A0 and A1 is due to distance concept,
(ii) A1 and A2 is due to backup deallocation, and (iii) A2 and A3 is due to backup overloading. From
Figs.8-13, it can be see that each of the guarantee ratio improving techniques improves the guarantee
ratio of the system, with very minimal increase in scheduling cost. That is, algorithms A0, A1, A2,
and A3 offer non-decreasing order of guarantee ratio. The distance concept and backup deallocation are
more effective compared to backup overloading.
5.2.1 Effect of Task Laxity, Resource Usage, and Task Load
The effect of task laxity (R) is studied in Fig.8. As the laxity increases, the guarantee ratio also
increases. For lower laxities, the difference in guarantee ratio between algorithms is less and increases
with increasing laxity. This is because, for lower values of laxity, the deadlines of tasks are very tight
and due to which the guarantee improving techniques have less flexibility to be more effective.
In Fig.9, the probability that a task uses a resource (UseP ) is varied. The increase in UseP , for
a fixed ShareP , increases the resource conflicts among tasks and hence the guarantee ratio decreases.
This is true for all the algorithms.
The effect of task load is studied in Fig.10. As load increases, the guarantee ratio decreases for all
the algorithms. For lower values of task loads (when to 0:3), the guarantee ratio of all the four
algorithms is more or less the same. This is because, at such low load, the system has enough processors
and resources to feasibly schedule the tasks. When the load increases, the difference in guarantee between
algorithms also increases, which means that the proposed techniques are effective at higher loads.
5.2.2 Effect of Number of Processors
The effect of varying the number of processors (m) is studied in Fig.11. For this, the task load is fixed
to be the load of 8 processors. The increase in number of processors increases the guarantee ratio for all
the four algorithms. The difference in guarantee ratio for two successive values of m (i.e., m and m+ 1)
is very high when m is small, and decreases as m increases. This is because of limited availability of
resources, i.e., the bottleneck is the resources and not the processors. This means that if m is increased
beyond 10, there cannot be much improvement in the guarantee ratio.6670747882
Guarantee
ratio
Task laxity
A3
Fig.8 Effect of task laxity65758595
Guarantee
ratio
Resource usage probability
A3
Fig.9 Effect of resource usage probability
Guarantee
ratio
Task arrival rate
A3
Fig.10 Effect of task load50607080
Guarantee
ratio
Number of processors
A3
Fig.11 Effect of number of processors7072747678
Guarantee
ratio
Actual to worst case computation ratio
A3
Fig.12 Effect of actual to worst case computation
Guarantee
ratio
Primary fault probability
Fig.13 Effect of primary fault probability
5.2.3 Effect of Actual to Worst Case Computation Time Ratio
The ratio between actual to worst case computation time (aw-ratio) of tasks is varied in Fig.12. In
this experiment, the actual computation time of a task is taken to be aw-ratio times the worst case
computation of the task. From Fig.12, an increase in aw-ratio decreases the guarantee ratio for all the
algorithms. When aw-ratio=1.0, the reclaiming is only due to backup deallocation (wherever applicable).
For example, for algorithms A0 and A1, when aw-ratio=1.0, no resource reclaiming is possible. When
aw-ratio=1.0, the difference in guarantee ratio between A0 and A1 is purely due to distance concept,
between A1 and A2 is purely due to backup deallocation, and between A2 and A3 is purely due to
backup overloading.
5.2.4 Effect of Fault Probability
The probability that a primary encounters a fault (FaultP ) is varied in Fig.13. Here, only three algorithms
(A0, A1, and A2) are plotted because the number of faults (for a given FaultP ) generated
while studying A3 is different (very less), because of at most one fault at a time, compared to the other
algorithms. When there is no fault in the system, which means that every backup is
deallocated. The guarantee ratio of algorithms A0 and A1 is flat for all values of FaultP since they do
not deallocate backups. For A2, an increase in FaultP decreases the guarantee ratio.
5.2.5 Performance of Flexible Overloading
The performance of flexible backup overloading has been studied for various parameters. Here, we
present only some sample results. For these experiments, m is taken as 8, and the different algorithms
studied are: (i) no overloading (Algorithm A2), (ii) half overloading (gsize = (say A4), and (iii) full
overloading which is the same as algorithm A3. The tradeoff between performance and
fault-tolerance is studied through this experiment. At any point of time, Algorithm A2 can tolerate
more than one fault, algorithm A4 can tolerate two faults with a restriction that there is at most one
fault within a group, and algorithm A3 can tolerate at most one fault.
The task load and laxity are varied in Fig.14 and 15, respectively. From these figures, the guarantee
ratio offered by full overloading is better than the other two, and half overloading is better than no over-
loading. The gain in guarantee ratio obtained by trading (reducing) the number faults in full overloading
is around 2% to 3% in both the experiments. For lower task loads, the gain is less than 1% and is more
at higher task loads. This reveals that backup overloading is less effective in improving the guarantee
ratio compared to the other techniques such as distance concept, backup deallocation, and reclaiming
from early completing tasks. Thus, the flexible overloading provides a tradeoff between performance and
the degree of fault-tolerance.
Guarantee
ratio
Task arrival rate
A3
Fig.14 Effect of task load70747882
Guarantee
ratio
Task laxity
A3
Fig.15 Effect of task laxity
5.3 Analytical Study
In this section, we show analytically using Markov chains that the distance is an important parameter
in fault-tolerant dynamic scheduling of real-time tasks. Using Markov chains, the possible states of the
system and the probabilities of transitions among them can be determined, which can then be used to
evaluate different dependability metrics for the system. The analysis presented here is similar to the one
given in [3, 17] except for the backup preallocation strategy. To make the analysis tractable, we make
the following assumptions:
1. All tasks have unit worst case computation time, i.e., c
2. Backup slots are preallocated in the schedule based on the distance parameter.
3. FIFO scheduling strategy is used.
4. Size of the feasibility check window (K) is 1.
5. Task deadlines are uniformly distributed in the interval [W min ,W max ] relative to their ready times,
which we call deadline window.
6. Task arrivals are uniformly distributed with mean A av .
7. Backup overloading and resource reclaiming are not considered.
5.3.1 Backup Preallocation Strategy
Since the tasks are of unit length, we reserve slots in the schedule for the backup copies based on the
distance parameter. Let m be the number of processors and d be the distance. Let s
and In our backup preallocation strategy, at any time t, the available number of
primary slots is s 1 if t is odd, s 2 if t is even. Similarly, the available number of backup slots is s 2 if t
is odd, s 1 if t is even. In other words, backups are reserved at time slot the primaries of time
slot t. Fig.16 shows the backup preallocation with 2. Note that the backup preallocation
for m processors with distance (m \Gamma d) is the same as for m processors with distance d. In our backup
preallocation strategy, d should not be equal to (m \Gamma 1) because if a primary is scheduled on slot t (even),
its backup slot is already reserved on the same processor at time slot which is a violation of space
exclusion. Also, d ? m does not have any meaning in the preallocation.
Processors
Time (t) ->
Backup slot
Fig.16 Distance based backup preallocation with
5.4 Analysis
If P ar (k) is the probability of k tasks arriving at a given time, then P ar
If Pwin (k) is the probability that an arriving task has a relative deadline w, then
The arriving tasks (primary copies) are appended to the task queue (Q) and they are scheduled in
FIFO order. Given that s 1 or s 2 tasks can be scheduled on a given time slot t depending on whether t
is odd or even, respectively, then the position of the tasks in the Q indicates their scheduled start times.
If at the beginning of time slot t, a task T i is the k-th task in Q, then T i is scheduled to execute at time
k is the time, from now, at which a task will execute whose position in the Q is k and
is defined as
In equation (3), arrives at time t, its schedulability
depends on the length of Q and on the relative deadline w i of the task. If T i is appended at position q
of Q and w i - g q , then the primary copy, Pr i , is guaranteed to execute before time
the task is not schedulable since it will miss its deadline. Moreover, if w
guaranteed to execute before t +w i . Note that in our backup preallocation strategy, the backup of a task
is scheduled in the immediate next slot of its primary. The dynamics of the system can be modelled using
Markov chain in which each state represents the number of tasks in Q and each transition represents
the change in the length of the Q in one unit of time. The probabilities of different transitions may be
calculated from the rate of task arrival. For simplicity, the average number of tasks executed at any time
t is which is m=2.
If S u represents the state in which Q contains u tasks and u - m=2, then the probability of a transition
from S u to S u\Gammam=2+k is P ar (k) since at any time t, k tasks can arrive and m=2 tasks get executed. If
only u tasks are executed, then there is a state transition from S u to S k with probability
ar (k).
When the k arriving tasks have finite deadlines, some of these tasks may be rejected. Let P q;k be
the probability that one of the k tasks is rejected when the queue size is q. The value of P q;k is the
probability that the relative deadline of the task is smaller than and the extra
one time unit is needed to schedule the backup. Then,
Pwin (w); (4)
Hence, when the queue size is q, the probability, P rej (r; k; q), that r out of the k tasks
are rejected is
r is the number of possible ways to select r out of k elements.
Our objective is to find the guarantee ratio (rejection ratio) for different values of distance. To do
that, we need to compute the number of tasks rejected in each state. This is done by splitting each
state S u in the one-dimensional Markov chain into 2A av av is the maximum
number of task arrivals, and possibly rejected, in unit time. In the two-dimensional Markov chain, the
state S u;r represents the queue size as u and r tasks were rejected when the transition was made into
S u;r . The two-dimensional Markov chain contains (m=2)W
columns (number of arrivals in unit time 1), and the transition probabilities become:
if
if
By computing the steady state probabilities of being in the rejection states, it is possible to compute
the expected value of the number of rejected tasks Rej per unit time. If P ss (u; v) is the steady state
probability of being in state S u;v , then
(vP ss (u; v)): (6)
Then, the rate of task rejection is given by Rej=A av . Note that, P ss (u; 0) is not included in equation (6)
since these are the states corresponding to no rejection.
5.4.1 Results
Figs.17 and show the rejection ratio by varying distance for different values of A av and W max , re-
spectively. The values of the other fixed parameters are also given in the figures. Since the preallocation
of backups for distance d and (m \Gamma d) is identical, their corresponding rejection ratios are also the same.
From the plots, it can be observed that the rejection ratio varies with varying distance. For lower values
of distance, the rejection ratio is more and the same is true for higher values of distance. The lowest
rejection ratio (best guarantee ratio) corresponds to some medium value of distance. From the Figs.17-
19, the optimal value of distance is m=2. Therefore, the distance parameter plays a crucial role on the
effectiveness of dynamic fault-tolerant scheduling algorithms.
Rejection
ratio
Distance
Fig.17 Effect of task load
Rejection
ratio
Distance
Fig.18 Effect of laxity
Rejection
ratio
Distance
Fig.19 Effect of distance
5.5 Comparison with an Existing Algorithm
In this section, we compare our distance myopic algorithm with a recently proposed algorithm by Ghosh,
Melhem, and Moss~e (which we call, GMM algorithm) in [3] for fault-tolerant scheduling of dynamic real-time
tasks. The GMM algorithm uses full backup overloading (gsize = m) and backup deallocation,
and permits at most one failure at any point of time. The GMM algorithm does not address resource
constraints among tasks and reclaims resources only due to backup deallocation. The limitations of this
algorithm have been discussed in Section 3.2.
In the GMM algorithm, the primary and backup copies of a task are scheduled in succession. In
other words, the distance is always 1. The algorithm is informally stated below:
GMM Algorithm():
begin
1. Order the tasks in non-decreasing order of deadline in the task queue.
2. Choose the first (primary) and second (backup) tasks for scheduling:
ffl Schedule the primary copy as early as possible by End Fitting() or Middle Fitting() or Middle
Adjusting().
ffl Schedule the backup copy as late as possible by Backup Overloading() or End Fitting() or
Middle Fitting() or Middle Adjusting().
3. If both primary and backup copies meet their deadline, accept them in the schedule.
4. else reject them.
(a) End Fitting(): Schedule the current task as the last task in the schedule of a processor.
(b) Middle Fitting(): Schedule the current task some where in the middle of the schedule of a
processor.
(c) (b) Middle Adjusting(): Schedule the current task some where in the middle of the schedule
of a processor by changing start and finish times of adjacent tasks.
(d) Backup Overloading(): Schedule the current task on a backup time interval if the primary
copies corresponding to these backup copies are scheduled on two different processors.
Each of steps (b)-(d), the search for fitting, adjusting, and overlapping, begins at the end of the
schedule and proceeds towards the start of the schedule of every processor. The depth of the search is
limited to an input parameter K. Since each of steps (b)-(d) takes time Km, the worst case time taken
to schedule a primary copy is 2Km, whereas it is 3Km for a backup copy.
The performance of distance myopic algorithms is compared with the GMM algorithm. For the sake of
comparison with the GMM algorithm, no resource constraints among tasks are considered. To make the
comparison fair, resource reclaiming only due to backup deallocation is considered, since GMM does not
reclaim resources from early completing tasks. The plots in Figs.20 and 21 correspond to four algorithms:
(i) distance myopic (DM), (ii) distance myopic with full backup overloading (DM
algorithm without backup overloading (GMM - overload), and (iv) GMM algorithm.
The scheduling cost of both the algorithms is made equal by appropriately setting K(= 4) and K(= 1)
parameters in distance myopic and GMM algorithms, respectively. For these experiments, the values
of R, UseP , FaultP , aw-ratio, and distance values are taken as 5, 0, 0.2, 1, and 5, respectively. We
present here only the sample results.
The task load is varied in Fig.20. In this figure, the different algorithms are ordered in decreasing
order of the guarantee ratio offered: DM overloading. In Fig.21,
the number of processors is varied by fixing the task load equal to the load of 8 processors. For lower
number of processors, even DM algorithm is better than GMM. From these simulation experiments, we
have shown that our proposed algorithm (DM + overloading) is better than the GMM algorithm even
for the (restricted) task model for which it was proposed.5070900.5 0.6 0.7
Guarantee
ratio
Task arrival rate
GMM
DM
Fig.20 Effect of task load305070903 4 5 6 7 8
Guarantee
ratio
Number of processors
GMM
DM
Fig.21 Effect of number of processors
6 Conclusions
In this paper, we have proposed an algorithm for scheduling dynamically arriving real-time tasks with resource
and primary-backup based fault-tolerant requirements in a multiprocessor system. Our algorithm
can tolerate more than one fault at a time, and employs techniques such as distance concept, flexible
backup overloading, and resource reclaiming to improve the guarantee ratio of the system.
Through simulation studies and also analytically, we have shown that the distance is a crucial parameter
which decides the performance of any fault-tolerant dynamic scheduling in real-time multiprocessor
systems. Our simulation studies on distance parameter show that increasing the size of feasibility check
window (and hence the look ahead nature) does not necessarily increase the guarantee ratio. The right
combination of K and distance offers the best guarantee ratio. We have also discussed as how to choose
this combination.
We have quantified the effectiveness of each of the proposed guarantee ratio improving techniques
through simulation studies for a wide range of task and system parameters. Our simulation studies show
that the distance concept and resource reclaiming, due to both backup deallocation and early completion
of tasks, are more effective in improving the guarantee ratio compared to backup overloading. The
flexible backup overloading introduces a tradeoff between the number of faults and the guarantee ratio.
From the studies of flexible backup overloading, the gain (in guarantee ratio) obtained by favouring
performance (i.e., reducing the number of faults) is not very significant. This indicates that the backup
overloading is less effective, compared to the other techniques.
We have also compared our algorithm with a recently proposed [3] fault-tolerant dynamic scheduling
algorithm. Although our algorithm takes into account resource constraints among tasks and tolerates
more than one fault at a time, for the sake of comparison, we restricted the studies to independent
tasks with at most one failure. The simulation results show that our algorithm, when it is used with
backup overloading, offers better guarantee ratio than that of the other algorithm for all task and system
parameters. Currently, we are investigating as how to integrate different fault-tolerant approaches
namely, triple modular redundancy, primary-backup approach, and imprecise computation into a single
scheduling framework.



--R

"Multiprocessor on-line scheduling of hard real-time tasks,"
"Computers and intractability, a guide to the theory of NP- completeness,"
"Fault-Tolerance through scheduling of aperiodic tasks in hard real-time multiprocessor systems,"
"Bounds on multiprocessing timing anomalies,"
"Approaches to implementation of reparable distributed recovery block scheme,"
"Distributed fault-tolerant real-time systems,"
"On scheduling tasks with quick recovery from failure,"
"Real-time Systems,"
"Architectural principles for safety-critical real-time applications,"
"A fault tolerant scheduling problem,"
"Imprecise computations,"
"Modular redundancy in a message passing system,"
"An efficient dynamic scheduling algorithm for multiprocessor real-time systems,"
"A new study for fault-tolerant real-time dynamic scheduling algorithms,"
"New algorithms for resource reclaiming from precedence constrained tasks in multiprocessor real-time systems,"
"Real-time System Scenarios,"
"Analysis of a fault-tolerant multiprocessor scheduling al- gorithm,"
"Adaptive software fault tolerance policies with dynamic real-time guarantees,"
"Multiprocessor support for real-time fault-tolerant scheduling,"
"An environment for developing fault-tolerant software,"
"Efficient scheduling algorithms for real-time multiprocessor systems,"
"Scheduling algorithms and operating systems support for real-time systems,"
"Graceful degradation in real-time control applications using (m,k)-firm guarantee,"
"Resource reclaiming in multiprocessor real-time systems,"
"Real-time computing: A new discipline of computer science and engineering,"
"Understanding fault-tolerance and reliability,"
"The Spring Kernel: A new paradigm for real-time operating systems,"
"TaskPair-Scheduling: An approach for dynamic real-time systems,"
"Low overhead multiprocessor allocation strategies exploiting system spare capacity for fault detection and location,"
"Fault-tolerant scheduling algorithm for distributed real-time systems,"
"Determining redundancy levels for fault tolerant real-time systems,"
"Multiprocessor scheduling of processes with release times, deadlines, precedence and exclusion constraints,"
"Scheduling tasks with resource requirements in hard real-time systems,"
--TR

--CTR
Wei Sun , Chen Yu , Xavier Defago , Yuanyuan Zhang , Yasushi Inoguchi, Real-time Task Scheduling Using Extended Overloading Technique for Multiprocessor Systems, Proceedings of the 11th IEEE International Symposium on Distributed Simulation and Real-Time Applications, p.95-102, October 22-26, 2007
R. Al-Omari , A. K. Somani , G. Manimaran, An adaptive scheme for fault-tolerant scheduling of soft real-time tasks in multiprocessor systems, Journal of Parallel and Distributed Computing, v.65 n.5, p.595-608, May 2005
R. Al-Omari , Arun K. Somani , G. Manimaran, Efficient overloading techniques for primary-backup scheduling in real-time systems, Journal of Parallel and Distributed Computing, v.64 n.5, p.629-648, May 2004
Xiao Qin , Hong Jiang, A novel fault-tolerant scheduling algorithm for precedence constrained tasks in real-time heterogeneous systems, Parallel Computing, v.32 n.5, p.331-356, June 2006
Wenjing Rao , Alex Orailoglu , Ramesh Karri, Towards Nanoelectronics Processor Architectures, Journal of Electronic Testing: Theory and Applications, v.23 n.2-3, p.235-254, June      2007
run-time anomaly;dynamic scheduling;fault tolerance;safety critical application;resource reclaiming;real-time system