基于自检测的自适应一致表决算法

俞功兵，王俊峰

（四川大学 计算机学院，四川 成都 610065）

随着软件技术的迅速发展和人们对软件系统稳定性、可靠性的更高要求，软件冗余技术越来越受到人们的重视并被广泛地应用于各类软件系统中，用以提高系统容错能力。其基本原理就是通过在计算机上运行功能相同但采取不同设计方式实现的软件模块和相应的表决算法来屏蔽软件冗余模块的错误输出，以此提高软件系统的可靠性。常用的表决算法有大数表决算法[1]、一致性表决算法[2]、自适应大数表决算法[3]等。

但是，上面提到的各种表决算法都有各自的缺点，大数表决算法在当各软件冗余模块输出不能达成一致时，不能表决输出结果；一致性表决算法一定程度上客服了大数表决算法的缺陷，但在软件冗余模块输出结果有相同的最大输出一致时，只能随机选择一组结果作为最终输出，此时表决系统很有可能输出一个不正确的结果，另外，软件冗余模块虽然采用软件的相异性策略进行设计与开发，但由于软件功能需求的相同，开发手段和工具的相近，软件冗余模块之间肯定存在着不能够克服的相关性，很难保证冗余模块软件版本的独立性，所以软件模块的失效空间可能存在重叠，这样就可能出现冗余模块的错误输出获得表决通过，使软件系统可靠性降低；自适应大数表决算法是一致性表决算法的拓展，通过构建每个软件冗余模块的历史记录信息，克服一致性表决算法在当各软件冗余模块不能达成一致时不能输出结果的问题，同时也在一定程度上考虑了错误的原因及分布，能对系统重置或安全降级策略提供支持，但是通常情况下，一个表决周期的执行时间远远超过瞬时错误的持续时间，很难反映模块运行时的实时特征，因此该算法不能容忍软件冗余模块在表决周期内发生瞬时错误。

文中针对自适应大数表决算法不能容忍软件冗余模块在表决周期内发生瞬时错误的情况，提出了一种新的表决算法-基于自检测的自适应一致表决算法。该算法是自适应大数表决算法的拓展，在自适应大数表决算法的基础上进一步考虑了错误的原因及其分布特征，能比较准确地反映各软件冗余模块在执行过程中是否发生了瞬时错误。

1 基于自检测的自适应一致表决算法

1.1 瞬时错误检测代码

在原来的软件冗余模块代码中分散地插入相应的检测代码，实时地抽取任务运行过程中的环境信息。这里定义{k1，k2…，kn}为任务代码序列，{f1，f2，…，fm}为检测代码序列，把{f1，f2，…，fm}均匀分布地插入{k1，k2…，kn}中，等效成{k1，k2，f1，k3，k4，f2，…，fm，kn}。 当然，插入方法不同，得到的序列也不同。 关键一步就是合理地设计检测代码序列{f1，f2，…，fm}。这里只需要检测代码序列能够检测出软件冗余模块在运行时是否发生瞬时错误，在保证功能的前提下检测代码越少，系统运行开销也会越少，对后续表决系统表决的影响也会越少。

本文借鉴使用基于自检测的多数一致表决算法[4]中用作检测RAM错误、算术逻辑单元ALU错误的检测序列：

（*）表示＜DetectPair＞可以重复任意次数。

如果执行软件冗余模块的过程中没有发生瞬时错误，则DetectResult为零；如果在一个表决周期发生瞬时错误，则DetectResult不为零；这样我们通过判断DetectResult值是否为零，来确定是否阻塞某一个软件冗余模块。

文献[5]中提到，在一个具有N个软件冗余模块的容错系统中，增加一个高性能的软件冗余模块，对于表决系统表决性能的提高有促进；相反，如果我们把N个软件冗余模块中发生瞬时错误的模块屏蔽后，再进行表决，那么表决系统输出的可靠性也会有所增强；所以在相同的条件下，基于自检测的自适应一致表决算法表决性能肯定优于基于自检测的多数一致表决算法的表决性能。

1.2 一种新的基于历史记录信息的自适应一致表决算法

这里最关键的就是要构建软件冗余模块的历史记录信息。构建历史记录信息最常用方法就是累计每个软件冗余模块通过表决的次数，软件冗余模块的输出结果每通过一次表决，就记录一次该冗余模块的次数。那么，在某一个表决周期，具有最大记录次数的软件冗余模块被认为是最可靠地模块，想反，记录次数最低的模块被认为是可靠性最低的模块。对于基于N版本程序的软件容错系统，下面给出基于历史记录信息表决算法的一个形式化描述:

2）设 A={a1，a2，…an}为第 Q个表决周期 n个模块输出，V1，V2， …Vp为 A 的一个划分，V1U V2U…UVp=A，|V1|表示 V1中元素的个数，且任意两个划分之间没有交集；对于任意ai∈Vi，均有 d（ai，ak）＜g，d（ai，ak）为 ai与 ak之间的距离，g 为表决器阈值，由用户根据实际情况设定。

当|V1|大于等于（n+1）/2时，以V1中的输出结果作为参考，在Q表决周期之前，哪个输出结果对应的软件冗余模块的H值大，就取该输出结果为最后输出结果，同时将V1中的输出结果对应模块的H值增1，以便后续周期表决作参考。例：A=｛9.5，9.6，9.9，10，10.1，10.8，11.1｝， 其对应软件冗余模块通过表决的历史记录 H=｛90，92，95，98，96，91，88｝，假设在Q 表 决 周 期 快 结 束 的 时 候 ，A=｛V1，V2｝， 其 中 V1=｛9.5，9.6，9.9，10，10.1｝，V2=｛10.8，11.1｝，因为|V1|=5，在表决周期Q之前，V1中输出结果10对应的软件冗余模块通过的表决次数最高为98，所以将输出结果10作为表决器最后输出，同时将软件冗余模块的历史记录修正为｛91，93，96，99，97，91，88｝。

当|V1|小于（n+1）/2，但大于|V2|至|Vp|中的任何一个时，仍以V1中的输出结果作为参考，在Q表决周期之前，哪个输出结果对应的软件冗余模块的H值大，就取该输出结果为最后输出结果，同时将V1中的输出结果对应模块的H值增1。继续以 A=｛9.5，9.6，9.9，10，10.1，10.8，11.1｝，H=｛90，92，95，98，96，91，88｝为例，假设在此表决周期快结束的时候，A=｛V1，V2，V3｝，其中 V1=｛9.9，10，10.1｝，V2=｛11.1，10.8｝，V3=｛9.5，9.6｝。 因为V1中的输出结果具有最大赞同数，在表决周期Q之前，V1中输出结果10对应的软件冗余模块通过的表决次数最高为98，所以将输出结果10作为表决器最后输出，同时将软件冗余模块的历史记录修正为｛90，92，96，99，97，91，88｝。

在Q表决周期快要结束时，如果具有相同的最大赞同数，且最大赞同数小于（n+1）/2。假设V1和V2具有相同的最大赞同数，那么以V1和V2中的输出结果作为参考，在Q表决周期之前，哪个输出结果对应的软件冗余模块的H值大，就取该输出结果为最后输出结果，同时将属于同一划分中的输出结果所对应的软件冗余模块H值增1。这里假设A=｛9.0，9.1，9.3，9.9，10，10.1，11.1｝，H 等 于 ｛90，92，95，96，98，91，88｝ 为例， 假设在此表决周期快结束的时候，A=｛V1，V2，V3｝， 其中 V1=｛9.0，9.1，9.3｝，V2=｛9.9，10，10.1，｝，V3=｛11.1｝。因为V1和V2具有相同的最大赞同数，在表决周期Q之前，V2中输出结果10对应的软件冗余模块通过的表决次数最高为98，所以将输出结果10作为表决器最后输出，同时将软件冗余模块的历史记录修正为｛90，92，95，97，99，92，88｝。

当出现其他情况时，表决失效，停止，转入失效安全状态。

1.3 基于自检测的自适应一致表决系统结构

基于能实现以上功能，本文提出了一种新的拓展表决系统结构框架图，如图1所示。

图1中特殊情况历史表的作用在于当某些大多数软件冗余模块的输出是错误的情况下生成了表决结果，那么同样的系统发生类似的情况仍然会表决出错误的结果。对这种情况进行记录，构成特殊情况历史表，并对特殊情况进行分别计数，保留出错次数极高的情况，可以在重复出现同样情况时作参考。

图1 基于自检测的自适应一致表决系统结构Fig.1 Structure of adaptive consensus voting system based on Self-test system

历史记录表作用在于记录过去的表决情况，包括所有软件冗余模块的输出结果，软件冗余模块运行时发生瞬时错误的次数，系统表决的结果，各个软件冗余模块输出结果通过表决的次数等，为表决系统最终表决提供参考。

2 仿真实验结果及其对比分析

由文献[4]的实验结论，得出在当软件冗余模块可靠性从低到高变化的时候，基于自检测的多数一致表决算法性能比自适应大数表决算法性能最高提高3%，所以为了直观说明基于自检测的自适应一致表决算法表决性能的优劣，我们采用仿真方式[6]，构造一个代码解释器来仿真目标计算机，与基于自检测的多数一致表决算法性能作比较。仿真实验如下:

1）将任务代码序列{k1，k2…，kn}的一次动态执行等效成一个顺序执行序列{X1，X2，…，Xz}，按某种方式插入检测代码序列{f1，f2，…，fm}后得到的序列为{Y1，Y2，…，Yz+m}。

2）构造的代码解释器能执行像a=b op f的指令，其中a、b为变量，op为如加、减、乘、除一样的操作符，f为整型或浮点常数。 模拟产生任务代码序列{X1，X2，…，Xz}，Xi为代码 ai=b+fi，fi为随机产生的浮点数，计数器N初始值赋零，设任务代码长度L。

3）将检测序列对DetectPair均匀插入任务代码中，设检测序列长度l。

4）瞬时错误注入。根据前面提到的等效，所以{Y1，Y2，…，Yz+m}可以被看为顺序执行结构，在执行时间轴上的某点发生错误，可以等效看作代码长度空间上的某点发生了错误。

根据实验需要，这里假设单个软件冗余模块的可靠性R=0.8，错误持续时间调节因子§=10，表决器阈值g=0.5，Pi=0.9，任务代码长度L=5 000，检测代码长度l=200，经过错误污染的软件冗余模块数 x 分别取值 0，1，2，3，4，5，6，7，8，软件冗余模块总数N远大于x，每种情况运行一万次后得到以下数据。

表1中y表示基于自检测的自适应一致表决算法相对基于自检测的一致表决算法表决性能提高百分比数。

表1 错误污染软件冗余模块数对表决性能的影响Tab.1 Error pollution redundant module of the influence on the performance of the voting

由上表可以看出，当软件冗余模块数N远大于发生瞬时错误的模块数x时，随着发生瞬时错误模块数x的逐渐增多，y也逐渐增大。所以，基于自检测的自适应一致表决算法尤其适合于发生瞬时错误相对较多的场合。

3 结束语

本文提出了一种基于自检测的自适应一致表决算法，它克服了自适应大数表决算法不能容忍软件冗余模块在表决周期内发生瞬时错误的情况，也克服了基于自检测的一致性表决算法在各软件冗余模块输出不能达成最大一致时无法表决的情况；仿真实验证明了该算法相对基于自检测的一致性表决算法具有一定的优越性，该算法尤其适合于发生瞬时错误相对较多的场合。

[1]Lorczak P R，Caglayan A K，Eckhardt D E.A theoretical investigation of generalised voters[C]//IEEE 19th Int.Ann.Symp.on fault-TolerantComputing Systems.Chicago，June 1989:444-451.

[2]McAllister D F，Sun C-E，Vouk M A.Reliability of voting in fault-tolerant software systems small output-spaces[J].IEEE Log，1990，39（5）:524-534.

[3]Latif-Shabgahi C，Bennett S.Adaptive majority voter:A novel voting algorithm for real-time fault-tolerant control systems[C]//Proceedings of 25th EUROMICRO Conference.Milan，Italy，Sept1ember，1999（2）:113-120

[4]周海涛，朱纪洪.基于自检测的多数一致表决算法[J].清华大学学报：自然科学版，2005，45（4）：488-491.

ZHOU Hai-tao，ZHU Ji-hong.Majority voting algorithm based on self-test[J].Journal of Tsinghua University：Science And Technology，2005，45（4）:488-491.

[5]Yacoub S，LIN Xiao-Fan，Simske S，et al.Automating the analysis of voting systems[C]//Proceedings of the 14th IEEE International Symposium on Software Reliability Engineering，2003.

[6]GilD，Martinez R，Busquets J V.Fault injection into VHDL models:Experimental Validation of a fault tolerant microcomputer system[C]//Proceedings of 3rd European Dependable ComputingConferenceBerlin Heidelberg:Spinger-Verlag，1999：191-208.