Efficient fault-tolerant scheduling on multiprocessor systems via replication and deallocation

Multiprocessor architectures have been extensively studied in the past decades. With the increasing demands on system reliability, fault-tolerant scheduling is even more important when multiprocessor system is used to run real-time applications since failure of any processor might produce disastrous results. To address this problem, we propose two fault-tolerant scheduling methods on multiprocessor systems via both active and passive backup copies. The first one uses the integer linear programming method to obtain the optimal results. The second one is a heuristic algorithm which can achieve close to optimal results within polynomial running time. In the experiments, this paper evaluates the proposed methods in terms of scheduling length for a set of DAG benchmarks. The experimental results show the effectiveness of our technique.