任务容错调度长度最优化的建模及仿真  

Optimization of Task Scheduling Length with Fault-tolerance

作　　者：周教生 ZHOU Jiao-sheng(School of Media Engineering,Lanzhou University of Arts and science,Lanzhou 730010,China)

机构地区：[1]兰州文理学院传媒工程学院,甘肃兰州730010

出　　处：《兰州文理学院学报（自然科学版）》2018年第2期71-78,共8页Journal of Lanzhou University of Arts and Science(Natural Sciences)

摘　　要：随着可持续性计算急切需求的增加,实时系统中的实时应用的容错调度变得尤为重要.这是因为在广泛采用多处理器体系结构的实时系统中,任何一个处理器故障都可能导致灾难性的后果.当一个任务由于处理器故障执行出错时,其备份的重新执行是必不可少的手段;并且就目前来说,任务备份的重新执行方式主要有主动和被动两种方式.本文所要解决的问题是,当多处理器系统中的一个处理器发生故障而失效时,如何为每个任务合理地选择任务备份的执行方式进行容错调度,从而使得所有的任务都能被成功执行且达到调度长度最小的目标.为了解决该问题,本文建立了单处理器故障下任务容错调度的系统模型、整数线性规划(Integer Linear Programming,ILP)以及启发式算法求解模型,提出的启发式算法能够在满足所有约束的条件下给出近似最优的调度方案.同时,本文建立的系统模型对调度方案进行了仿真,并分析了仿真结果.With the emerging demands on sustainable computation,scheduling of real-time applications with fault-tolerance becomes more important in real-time systems.This is because a multi-processor architecture is adopted by most of real-time systems,in which the failure of any processor might cause disastrous consequences.The re-execution of backups of a task is necessary when this task encounters a failed execution due to the transient fault occurring on its responsible processor;and up to now,there are mainly two kinds of re-execution of backups:the active re-execution and passive re-execution.What this paper tries to address is that how to find a feasible schedule with fault-tolerance so that the schedule length can be minimized by properly choosing active or passive backup copies with at most one processor failure in multiprocessor systems.To solve this problem,this paper establishes a system model of task scheduling with fault-tolerance in case of at most one processor incurring transient faults at one time and the model of integer linear programming solution.The ILP solution can guarantee an optimal solution while satisfying all constraints including the optimization objective.The proposed heuristic gives near-optimal solution compared with that of ILP.Lastly,this paper simulates the system model and gives detailed analysis to the simulation results.

关 键 词：容错 调度 多处理器 最优 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]