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

Authors: Jun Zhang; Edwin H-M. Sha; Qingfeng Zhuge; Juan Yi; Kaijie Wu

Addresses: College of Computer Science, Chongqing University, Chongqing, 400040, China ' College of Computer Science, Chongqing University, Chongqing, 400040, China ' College of Computer Science, Chongqing University, Chongqing, 400040, China; Key Laboratory of Dependable Service Computing in Cyber Physical Society, Ministry of Education, Chongqing, 400044, China ' College of Computer Science, Chongqing University, Chongqing, 400040, China; Key Laboratory of Dependable Service Computing in Cyber Physical Society, Ministry of Education, Chongqing, 400044, China ' College of Computer Science, Chongqing University, Chongqing, 400040, China; Key Laboratory of Dependable Service Computing in Cyber Physical Society, Ministry of Education, Chongqing, 400044, China

Abstract: 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.

Keywords: fault tolerance; optimisation; embedded systems; fault-tolerant scheduling; multiprocessor systems; replication; deallocation.

DOI: 10.1504/IJES.2014.063819

International Journal of Embedded Systems, 2014 Vol.6 No.2/3, pp.216 - 224

Received: 13 Sep 2013
Accepted: 11 Oct 2013

Published online: 31 Jul 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article