Y. Hashimoto and H.H. Ali (USA)
Genetic algorithms, fault-tolerant systems, real-time scheduling, task scheduling
The number of applications demanding real-time performance from their multiprocessor systems has been significantly increasing. At the same time, due to the possible catastrophic consequences from missing deadlines, fault-tolerance has become a critical issue in real-time systems. In order to solve real-time scheduling problems in multiprocessor systems, many researchers have proposed various heuristics and also adapted optimization methods such as simulated annealing, tabu search, and genetic algorithms. Nonetheless, almost none of these algorithms have been designed for fault-tolerant systems. In this paper, we present a genetic algorithm called the Genetic Real-time Fault-tolerant Scheduling (GRFS) algorithm and take a new approach to address real-time fault-tolerant scheduling. GRFS employs a fault-tolerant technique called backup overloading with two distinct modes, natural backup overloading and compulsive backup overloading. These two modes were devised in order to meet different system requirements. We also modified the existing branch-and-bound (B&B) algorithm to fit into our problem and compare these two algorithms. The simulation results show that GRFS outperforms the B&B algorithm in almost all cases. In addition, GRFS with natural backup overloading and compulsive backup overloading show different effects in terms of the schedule length and the processor utilization.
Important Links:
Go Back
