HIGH PERFORMANCE FAULT-TOLERANT REAL-TIME SCHEDULING ALGORITHMS

Abstract

Real-time computing is an enabling technology for many current and future application areas and is becoming increasingly pervasive. The next generation real-time systems must be designed to be dynamic, predictable, flexible, reliable, and to be able to deal with nondeterministic fault-prone environments under rigid timing constraints. This demand for faulttolerant real-time system that maximizes the performance in terms of number of tasks accepted and collected value, while using least redundancy. This research focuses on reduction in size of recovery blocks and full exploitation of resources reclaimed to achieve better performance in fault-tolerant real-time systems. A scheme of checkpointing is used to reduce the size of recovery block, whereas a deferred scheme is used for full exploitation of reclaimed resources. The checkpointing scheme saves the status of system at some intermediate points (checkpoints) and a rollback to the latest saved state is done at the occurrence of a failure. Therefore, it reduces the rollback portion though at the cost of additional of overhead for checkpoints. In this work various aspects of checkpointing to reduce the rollback portion in a real-time system with tasks of different arrival patterns and for different type of faults have been investigated. Further, deferment of scheduling decisions has been used for full exploitation of reclaimed resources and its effect on fragmentation of hypercube multiprocessor configuration has been investigated. An efficient online scheduling scheme is introduced to take care of transient faults on uniprocessor system. The algorithm uses optimum number of checkpoints for each tasks to reduce the size of recovery of atask to its least value. Theorems have been given to determine optimum number of checkpoints and to determine whether checkpointing is beneficial over noncheckpointing. The online scheduling algorithm is enhanced for the applications where tasks have mixed arrival patterns (fixed and random). Here, combined offline and online approach is used. The offline feasibility analysis is used for fixed arrival pattern tasks with consideration of worst-case requirements. Online resource management approach is used to schedule dynamically arriving (aperiodic) tasks in the presence of fixed arrival pattern tasks. The above algorithms discussed for uniprocessor system use time redundancy, and are applicable for transient faults only. To take care of permanent faults, hardware redundancy in addition to time redundancy is needed. A multiprocessor system provides hardware redundancy by scheduling primary and backup copies of a task on different processors. Proposed scheduling algorithm employs the guarantee improving techniques, such as checkpointing to reduce roll back portion, and parallel execution of a portion of primary copy of a task on two different processors. This provide on line resource reclamation. The system model considered is extended to include applications where different tasks can have different values, i.e., value-based scheduling of dynamically arriving tasks, in the presence of transient, intermittent, and permanent failures. Anew priority assignment scheme is introduced that considers task's value, worst-case execution time, and deadline to decide the priority of tasks. Moving through Uniprocessor system/multiprocessor system with independent processors to multiprocessor system having connected processors, such as hypercube and mesh connected systems, scope of scheduling get changed. A modified deferred fault-tolerant scheduling algorithm has been presented to take care of transient, intermittent, and permanent type failures for hypercube connected multiprocessor systems. The scheduling algorithms presented in this thesis have been thoroughly evaluated with the use of theoretical results, examples, and extensive simulation. The Simulation results in explain the effects of various input parameters, such as effective system load, tasks laxity factor, checkpoint overhead, time required to make alternative arrangements in case infeasible task is rejected, etc. We expect the results presented in this thesis will aid the system designer in the development of predictable, flexible and reliable real-time systems. iv