A SIMULATION STUDY OF FAULT-TOLERANT DYNAMIC SCHEDULING FOR MULTIPROCESSOR REAL-TIME SYSTEMS

Abstract

Real-time systems are being increasingly used in several applications, which are time critical in nature. Fault-tolerance is an important requirement of such systems, due to the catastrophic consequences of not tolerating faults. Many time critical applications require dynamic scheduling with predictable performance and these tasks in these applications have deadlines to be met. In this dissertation aim at studying the effects of an algorithm to dynamically schedule arriving real-time tasks with resource and fault-tolerant requirements on to multiprocessor systems. In this scheme we schedule multiple copies of dynamic, aperiodic, and nonpreemptive, tasks in the system, and use techniques called deallocation to achieve high guarantee-ratio (percentage of arriving tasks scheduled by the system). Two copies of each task called primary and backup copies that are mutually excluded in space, as well as in time in the schedule, are scheduled in this scheme to handle permanent processor failures and to obtain better performance, respectively. This scheme can tolerate more than one fault at a time, and employ 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) resource reclaiming, which reclaims both from deallocated backups and early completing tasks. Also, simulation studies were performed to compare the performance of this scheme with a best-known algorithm for the problem, and the importance of distance parameter in fault-tolerant dynamic scheduling in multiprocessor real-time systems is studied.