实时异构系统中的积极复制容错调度算法

在设计实时异构系统中的容错调度算法时,既要考虑到实时性的约束,又要最大化系统的可靠性.此外,异构系统中的并行应用调度问题已经被证明了是NP完全问题.现有的容错调度算法大多采用复制技术来提升系统的可靠性,但是任务的多次执行会导致应用执行时间变长,系统实时性下降.为此,提出了一个基于积极复制技术的容错调度算法,该算法连续的复制任务集中对当前系统实时性影响最小的任务,然后将任务集中的所有任务调度至最早完成的处理器,用以在满足实时性约束的同时,提升系统的可靠性.实验表明,相比于同样着眼于实时异构系统的DB-FTSA算法,该算法在实时性约束严格的情况下,可靠性有较大提升.

Active Replication Fault-tolerant Scheduling Algorithm in Real-time Heterogeneous Systems

When designing a fault-tolerant scheduling algorithm in a real-time heterogeneous system, it is necessary to consider the constraints of real-time and maximize the reliability of the system. Furthermore, parallel application scheduling problems in heterogeneous systems have been shown to be NP-complete. Most of the existing fault-tolerant scheduling algorithms use replication technology to improve the reliability of the system, but the multiple execution of tasks will lead to longer application execution time and reduced system real-time performance. Therefore, a fault-tolerant scheduling algorithm based on active replication technology is proposed. The algorithm continuously replicates the tasks that have the least impact on the real-time performance of the current system in the task set and then schedules all tasks in the task set to the earliest completed processor. While meeting the real-time constraints, the algorithm improves the reliability of the system. Experiments show that the reliability of the proposed algorithm has been improved under strict time constraints compared with that of the DB-FTSA algorithm which also focuses on real-time heterogeneous systems.