Real-time Task Assignment with Replication on Multiprocessor Platforms

Fault tolerance is a very important aspect in critical real-time task scheduling. On multiprocessor systems, executing tasks with replication provides an additional reliability to resist potential processor failures and computing faults. For assigning real-time tasks on such systems, there must be requirements that all tasks assigned on the system meet their timing constraints, and all replicas of the same task are assigned to distinct processors. Obviously, such a reliability requirement could overload the system. In these situations, how to assign the tasks on processors to achieve the highest benefit poses a challenge. In this paper, we consider the problem of maximizing the number of successfully assigned tasks on a homogeneous distributed multiprocessor system, while satisfying the real-time constraint and system reliability requirement. Exact, greedy approximation and polynomial time approximation scheme (PTAS) algorithms are developed for the problem. Theoretical analysis, necessary proofs and experimental results that support our claims are all given.