Bio-inspired approach to fault-tolerant scheduling of real-time tasks on multiprocessor - a study

Fault-tolerant scheduling of real-time (RT) tasks in multiprocessor based systems is essentially a NP-hard problem. Basically this is a permutation based combinatorial optimization problem which involves allocating a set of tasks to a set of processors so as to minimize the makespan and ensures tasks to meet their timing constraints. Conventional approach to meet fault-tolerance (FT) in scheduling RT tasks based on traditional heuristic approach yields poor performance, like inefficient processor utilization and higher task rejection. The primary-backup (PB) scheme is a popular approach used as a fault-tolerant technique to schedule RT tasks with guarantee to meet their deadlines despite presence of fault. In this paper, we propose a novel scheduling algorithm using particle swarm optimization (PSO) technique for providing FT in multiprocessor environment. Exhaustive simulation study reveals that the proposed primary-backup based fault-tolerant scheduling (PBFTS) scheme using PSO outperforms other traditional fault-tolerant scheduling schemes in terms of performance, system utilization and efficiency.