Preemptive Scheduling of Tasks with Reliability Requirements in Distributed Hard Real-Time Systems

Real-time systems are being extensively used in applications that are mission-critical and life-critical, such as space exploration, aircraft avionics, and robotics. These mission critical systems are mainly parallel or distributed systems that are embedded into complex, even hazardous environments, under tight constraints on timeliness and dependability of operations. It is therefore extremely important that these hard real-time systems must be reliable, i.e., task deadlines be met even in the presence of certain faults or failures. In this paper, we address the problem of supporting timeliness and dependability in a real-time system at the level of task scheduling. We consider the problem of scheduling a set of tasks, each of which, for fault-tolerance purpose, has multiple versions, on a number of processors, such that the number of processors used is minimized. Two scheduling algorithms are proposed and evaluated using simulation. It is shown that the algorithms produce near-optima..