面向服务仿真系统的最大可靠性容错调度算法

Fault-tolerant Scheduling Algorithm for Maximizing Reliability of Service-Oriented Simulation System

基于PB模型对面向服务的分布式仿真系统的容错调度问题进行了研究。首先,根据该类系统的特点提出了两个命题并以此为基础给出了仿真任务的调度规则;其次,分析了仿真任务的可靠性代价并给出了任务最坏反应时间的计算公式;最后,在此基础上提出了相应的算法RC-RTFT和MW-RTFT。RC-RTFT综合利用了最小可靠性代价及最小最坏反应时间两种启发式规则进行主版本任务的调度,MW-RTFT则基于最小最坏反应时间这一启发式规则进行主版本任务的调度,副版本任务的调度都是基于最小最坏反应时间启发式规则进行。算法仿真结果表明RC-RTFT算法具有较好的负载平衡特性和稳定性,且较MW-RTFT具有更小的算法复杂度。

The real-time fault-tolerant scheduling problem of service-oriented distributed simulation system was studied based on PB model, in which the heterogeneity of system was considered. Firstly, two propositions were put forward according to the characters of simulation system and corresponding scheduling rules were given. Secondly, reliability cost of simulation task was analyzed and two formulas for counting the worst case response time of primary and backup version tasks were put forward. Finally, two different algorithms were advanced, RC-RTFT and MW-RTFT. Primary version tasks were scheduled by the integration rule of minimum reliability cost and minimum worst case response time heuristic rule in RC-RTFT, whereas in MW-RTFT which were scheduled by minimum worst case response time. And in both algorithms, backup version tasks were scheduled by minimum worst case response time heuristic rule. The simulation result of algorithms shows that the load balance and stability characteristic of RC-RTFT is acceptable, and as computation complexity considered, and RC-RTFT is better than MW-RTFT.