| Real-time systems are those which must execute all tasks within their timing constraints. Due to the catastrophic consequences of missing deadlines of some real-time tasks, fault tolerance is an essential component of such systems. This thesis introduces techniques to enhance the fault tolerance capability of real-time systems by incorporating time redundancy.; Time redundancy is essential in ultrareliable real-time systems where correlated faults must be tolerated. It can also be used to detect and tolerate transient faults, which are a majority of the faults in computing systems. This thesis demonstrates how time redundancy can be used in conjunction with hardware and software redundancy to tolerate a variety of faults in real-time systems.; This thesis considers several different system and task models, and for each model, presents a schedulability test (a utilization bound or a set of conditions) which guarantees that all tasks in the system will satisfy their timing constraints even in the presence of faults. The thesis studies the tradeoff between the fault tolerance capability and resource utilization of the system (which decreases due to the added redundancy). New techniques are introduced to increase the system utilization. Efficient scheduling algorithms and bounds are presented to ensure high schedulability of tasks.; The fault tolerance approaches presented in this thesis are thoroughly evaluated. The time after which a system recovers from one fault and is ready to tolerate a second one is measured for static and dynamic systems. Various tradeoff studies are conducted to help the system designer make appropriate choices. Extensive simulation results explain the effects of various input parameters such as task characteristics, task arrival rate, and amount of redundancy on metrics such as the schedulability of tasks, system utilization and fault tolerance capability of the system. Implementation issues are also discussed for each model to help system designers build a fault-tolerant real-time system using time redundancy.; Overall, this thesis demonstrates that enhancing the fault tolerance capabilities of existing real-time systems is easily achieved without extensive changes to the hardware or system software. The schemes introduced in this thesis are flexible in the sense that they allow the amount of redundancy to be varied depending on the system requirements, the fault rate and the cost of incorporating redundancy. |
