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

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

作　　者：毛灯锋 胡威[1,2] 刘静 甘雨 MAO Deng-Feng;HU Wei;LIU Jing;GAN Yu(School of Computer Science and Technology,Wuhan University of Science and Technology,Wuhan 430065,China;Hubei Province Key Laboratory of Intelligent Information Processing and Real-time Industrial System,Wuhan 430065,China)

机构地区：[1]武汉科技大学计算机科学与技术学院,武汉430065 [2]智能信息处理与实时工业系统湖北省重点实验室,武汉430065

出　　处：《计算机系统应用》2023年第1期109-118,共10页Computer Systems & Applications

基　　金：国家自然科学基金面上项目(62176191)。

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

关 键 词：异构系统 容错调度 积极复制 可靠性 实时性 

分 类 号：TP332[自动化与计算机技术—计算机系统结构]