基于杂交遗传算法的多处理器硬实时容错调度算法  

Genetic algorithm based multiprocessor hard real-time fault tolerant schedule

作　　者：李冠楠[1] 李家春[2] Li Guannan;Li Jiachun(School of Electronic & Information Engineering, Shunde Polytechnic, Foshan Guangdong 528300 , China;School of Computer Science&Technology, South China University of Technology, Guangzhou 510641 , China)

机构地区：[1]顺德职业技术学院电子与信息工程学院,广东佛山528300 [2]华南理工大学计算机科学与技术学院,广州510641

出　　处：《计算机应用研究》2016年第9期2606-2610,共5页Application Research of Computers

基　　金：国家自然科学基金资助项目(51175183);佛山市产学研专项资金项目及顺德职业技术学院资助项目(2012HC100303);广东省教育科研"十二五"规划研究项目(2012JK305)

摘　　要：传统的硬实时容错调度算法获得了较好的容错性能,但其任务拒绝率、处理器分配偏差比例以及最早完成时间等性能参数不佳,对此提出了一种基于杂交遗传算法的优化方案,并对传统的硬实时容错算法进行优化。采用了中心型调度模型,并采用了任务备份方案来实现容错能力。将任务拒绝率、处理器分配偏差比例以及最早完成时间三个优化参数作为遗传算法适应度目标函数的三个带权分量,对其进行优化,通过遗传算法的杂交与迭代计算获得了优化的结果。最终使用不同的任务数量与处理器数量的组合对本算法与传统算法进行对比实验,结果可看出本算法的三个优化参数明显优于传统算法,且总适应度值亦比传统算法有明显改进。Traditional hard real-time fault tolerant scheduling algorithm had good fault tolerant performance, but its task rejection ration, processor allocation deviation ratio and earliest finishing time ratio performance was not good, so this paper proposed a optimal algorithm based on genetic algorithm, and optimized the traditional hard real-time fault tolerant scheduling algorithm.It used the central scheduling model and the backup task approach to realize the fault tolerant. It set the three optimal parameters of task rejection ration, processor allocation deviation ratio and earliest finishing time ratio as the fit function of the genetic algorithm as well as the weight, and got the optimal results by crossover operation and iteration of genetic algorithm.Lastly, several set of different count of tasks and processors were set up for compare experimental. Three optimal parameters got from the proposed algorithm are better than the traditional scheduling algorithm, and the total fit value is better too.

关 键 词：遗传算法 硬实时系统 容错调度 多处理器 嵌入式系统 

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