A Fault-Tolerant Scheduling Algorithm Based on Local Maximum Reliability Replication Strategy in Real-Time Heterogeneous Systems
Dengfeng Mao, Wei Hu, Yu Gan, Jing Liu, Haonan Gu · 2022 IEEE International Conference on Systems, Man, and Cybernetics (SMC) · 2022
High reliability and low latency are conflicting when tasks are scheduled. Scheduling of parallel applications with data dependencies in heterogeneous systems is an NP-complete problem. Using replication to improve system reliability can lead to increased application execution time. From the perspective of increasing the reliability of real-time heterogeneous system considering communication overhead and the timing requirements, this paper proposed a fault-tolerant scheduling algorithm based on local maximum reliability replication strategy (FTSA-BLMR). Our algorithm first sets the maximum number of replications for each task. Then it continuously replicates the task with the highest system reliability for the current task set to obtain a new task set. The tasks in the new task set will be scheduled and the scheduling results will be recorded. Finally, the scheduling result will be selected as the final scheduling sequence, which has maximum system reliability and meets the deadline. The experimental results indicate that our algorithm can improve the system reliability by 40% compared with DB-FTSA when the deadline constraint is strict.