基于自檢測(cè)的自適應(yīng)一致表決算法

俞功兵，王俊峰

（四川大學(xué) 計(jì)算機(jī)學(xué)院，四川 成都 610065）

隨著軟件技術(shù)的迅速發(fā)展和人們對(duì)軟件系統(tǒng)穩(wěn)定性、可靠性的更高要求，軟件冗余技術(shù)越來越受到人們的重視并被廣泛地應(yīng)用于各類軟件系統(tǒng)中，用以提高系統(tǒng)容錯(cuò)能力。其基本原理就是通過在計(jì)算機(jī)上運(yùn)行功能相同但采取不同設(shè)計(jì)方式實(shí)現(xiàn)的軟件模塊和相應(yīng)的表決算法來屏蔽軟件冗余模塊的錯(cuò)誤輸出，以此提高軟件系統(tǒng)的可靠性。常用的表決算法有大數(shù)表決算法[1]、一致性表決算法[2]、自適應(yīng)大數(shù)表決算法[3]等。

但是，上面提到的各種表決算法都有各自的缺點(diǎn)，大數(shù)表決算法在當(dāng)各軟件冗余模塊輸出不能達(dá)成一致時(shí)，不能表決輸出結(jié)果；一致性表決算法一定程度上客服了大數(shù)表決算法的缺陷，但在軟件冗余模塊輸出結(jié)果有相同的最大輸出一致時(shí)，只能隨機(jī)選擇一組結(jié)果作為最終輸出，此時(shí)表決系統(tǒng)很有可能輸出一個(gè)不正確的結(jié)果，另外，軟件冗余模塊雖然采用軟件的相異性策略進(jìn)行設(shè)計(jì)與開發(fā)，但由于軟件功能需求的相同，開發(fā)手段和工具的相近，軟件冗余模塊之間肯定存在著不能夠克服的相關(guān)性，很難保證冗余模塊軟件版本的獨(dú)立性，所以軟件模塊的失效空間可能存在重疊，這樣就可能出現(xiàn)冗余模塊的錯(cuò)誤輸出獲得表決通過，使軟件系統(tǒng)可靠性降低；自適應(yīng)大數(shù)表決算法是一致性表決算法的拓展，通過構(gòu)建每個(gè)軟件冗余模塊的歷史記錄信息，克服一致性表決算法在當(dāng)各軟件冗余模塊不能達(dá)成一致時(shí)不能輸出結(jié)果的問題，同時(shí)也在一定程度上考慮了錯(cuò)誤的原因及分布，能對(duì)系統(tǒng)重置或安全降級(jí)策略提供支持，但是通常情況下，一個(gè)表決周期的執(zhí)行時(shí)間遠(yuǎn)遠(yuǎn)超過瞬時(shí)錯(cuò)誤的持續(xù)時(shí)間，很難反映模塊運(yùn)行時(shí)的實(shí)時(shí)特征，因此該算法不能容忍軟件冗余模塊在表決周期內(nèi)發(fā)生瞬時(shí)錯(cuò)誤。

文中針對(duì)自適應(yīng)大數(shù)表決算法不能容忍軟件冗余模塊在表決周期內(nèi)發(fā)生瞬時(shí)錯(cuò)誤的情況，提出了一種新的表決算法-基于自檢測(cè)的自適應(yīng)一致表決算法。該算法是自適應(yīng)大數(shù)表決算法的拓展，在自適應(yīng)大數(shù)表決算法的基礎(chǔ)上進(jìn)一步考慮了錯(cuò)誤的原因及其分布特征，能比較準(zhǔn)確地反映各軟件冗余模塊在執(zhí)行過程中是否發(fā)生了瞬時(shí)錯(cuò)誤。

1 基于自檢測(cè)的自適應(yīng)一致表決算法

1.1 瞬時(shí)錯(cuò)誤檢測(cè)代碼

在原來的軟件冗余模塊代碼中分散地插入相應(yīng)的檢測(cè)代碼，實(shí)時(shí)地抽取任務(wù)運(yùn)行過程中的環(huán)境信息。這里定義{k1，k2…，kn}為任務(wù)代碼序列，{f1，f2，…，fm}為檢測(cè)代碼序列，把{f1，f2，…，fm}均勻分布地插入{k1，k2…，kn}中，等效成{k1，k2，f1，k3，k4，f2，…，fm，kn}。 當(dāng)然，插入方法不同，得到的序列也不同。 關(guān)鍵一步就是合理地設(shè)計(jì)檢測(cè)代碼序列{f1，f2，…，fm}。這里只需要檢測(cè)代碼序列能夠檢測(cè)出軟件冗余模塊在運(yùn)行時(shí)是否發(fā)生瞬時(shí)錯(cuò)誤，在保證功能的前提下檢測(cè)代碼越少，系統(tǒng)運(yùn)行開銷也會(huì)越少，對(duì)后續(xù)表決系統(tǒng)表決的影響也會(huì)越少。

本文借鑒使用基于自檢測(cè)的多數(shù)一致表決算法[4]中用作檢測(cè)RAM錯(cuò)誤、算術(shù)邏輯單元ALU錯(cuò)誤的檢測(cè)序列：

（*）表示＜DetectPair＞可以重復(fù)任意次數(shù)。

如果執(zhí)行軟件冗余模塊的過程中沒有發(fā)生瞬時(shí)錯(cuò)誤，則DetectResult為零；如果在一個(gè)表決周期發(fā)生瞬時(shí)錯(cuò)誤，則DetectResult不為零；這樣我們通過判斷DetectResult值是否為零，來確定是否阻塞某一個(gè)軟件冗余模塊。

文獻(xiàn)[5]中提到，在一個(gè)具有N個(gè)軟件冗余模塊的容錯(cuò)系統(tǒng)中，增加一個(gè)高性能的軟件冗余模塊，對(duì)于表決系統(tǒng)表決性能的提高有促進(jìn)；相反，如果我們把N個(gè)軟件冗余模塊中發(fā)生瞬時(shí)錯(cuò)誤的模塊屏蔽后，再進(jìn)行表決，那么表決系統(tǒng)輸出的可靠性也會(huì)有所增強(qiáng)；所以在相同的條件下，基于自檢測(cè)的自適應(yīng)一致表決算法表決性能肯定優(yōu)于基于自檢測(cè)的多數(shù)一致表決算法的表決性能。

1.2 一種新的基于歷史記錄信息的自適應(yīng)一致表決算法

這里最關(guān)鍵的就是要構(gòu)建軟件冗余模塊的歷史記錄信息。構(gòu)建歷史記錄信息最常用方法就是累計(jì)每個(gè)軟件冗余模塊通過表決的次數(shù)，軟件冗余模塊的輸出結(jié)果每通過一次表決，就記錄一次該冗余模塊的次數(shù)。那么，在某一個(gè)表決周期，具有最大記錄次數(shù)的軟件冗余模塊被認(rèn)為是最可靠地模塊，想反，記錄次數(shù)最低的模塊被認(rèn)為是可靠性最低的模塊。對(duì)于基于N版本程序的軟件容錯(cuò)系統(tǒng)，下面給出基于歷史記錄信息表決算法的一個(gè)形式化描述:

2）設(shè) A={a1，a2，…an}為第 Q個(gè)表決周期 n個(gè)模塊輸出，V1，V2， …Vp為 A 的一個(gè)劃分，V1U V2U…UVp=A，|V1|表示 V1中元素的個(gè)數(shù)，且任意兩個(gè)劃分之間沒有交集；對(duì)于任意ai∈Vi，均有 d（ai，ak）＜g，d（ai，ak）為 ai與 ak之間的距離，g 為表決器閾值，由用戶根據(jù)實(shí)際情況設(shè)定。

當(dāng)|V1|大于等于（n+1）/2時(shí)，以V1中的輸出結(jié)果作為參考，在Q表決周期之前，哪個(gè)輸出結(jié)果對(duì)應(yīng)的軟件冗余模塊的H值大，就取該輸出結(jié)果為最后輸出結(jié)果，同時(shí)將V1中的輸出結(jié)果對(duì)應(yīng)模塊的H值增1，以便后續(xù)周期表決作參考。例：A=｛9.5，9.6，9.9，10，10.1，10.8，11.1｝， 其對(duì)應(yīng)軟件冗余模塊通過表決的歷史記錄 H=｛90，92，95，98，96，91，88｝，假設(shè)在Q 表 決 周 期 快 結(jié) 束 的 時(shí) 候 ，A=｛V1，V2｝， 其 中 V1=｛9.5，9.6，9.9，10，10.1｝，V2=｛10.8，11.1｝，因?yàn)閨V1|=5，在表決周期Q之前，V1中輸出結(jié)果10對(duì)應(yīng)的軟件冗余模塊通過的表決次數(shù)最高為98，所以將輸出結(jié)果10作為表決器最后輸出，同時(shí)將軟件冗余模塊的歷史記錄修正為｛91，93，96，99，97，91，88｝。

當(dāng)|V1|小于（n+1）/2，但大于|V2|至|Vp|中的任何一個(gè)時(shí)，仍以V1中的輸出結(jié)果作為參考，在Q表決周期之前，哪個(gè)輸出結(jié)果對(duì)應(yīng)的軟件冗余模塊的H值大，就取該輸出結(jié)果為最后輸出結(jié)果，同時(shí)將V1中的輸出結(jié)果對(duì)應(yīng)模塊的H值增1。繼續(xù)以 A=｛9.5，9.6，9.9，10，10.1，10.8，11.1｝，H=｛90，92，95，98，96，91，88｝為例，假設(shè)在此表決周期快結(jié)束的時(shí)候，A=｛V1，V2，V3｝，其中 V1=｛9.9，10，10.1｝，V2=｛11.1，10.8｝，V3=｛9.5，9.6｝。 因?yàn)閂1中的輸出結(jié)果具有最大贊同數(shù)，在表決周期Q之前，V1中輸出結(jié)果10對(duì)應(yīng)的軟件冗余模塊通過的表決次數(shù)最高為98，所以將輸出結(jié)果10作為表決器最后輸出，同時(shí)將軟件冗余模塊的歷史記錄修正為｛90，92，96，99，97，91，88｝。

在Q表決周期快要結(jié)束時(shí)，如果具有相同的最大贊同數(shù)，且最大贊同數(shù)小于（n+1）/2。假設(shè)V1和V2具有相同的最大贊同數(shù)，那么以V1和V2中的輸出結(jié)果作為參考，在Q表決周期之前，哪個(gè)輸出結(jié)果對(duì)應(yīng)的軟件冗余模塊的H值大，就取該輸出結(jié)果為最后輸出結(jié)果，同時(shí)將屬于同一劃分中的輸出結(jié)果所對(duì)應(yīng)的軟件冗余模塊H值增1。這里假設(shè)A=｛9.0，9.1，9.3，9.9，10，10.1，11.1｝，H 等 于 ｛90，92，95，96，98，91，88｝ 為例， 假設(shè)在此表決周期快結(jié)束的時(shí)候，A=｛V1，V2，V3｝， 其中 V1=｛9.0，9.1，9.3｝，V2=｛9.9，10，10.1，｝，V3=｛11.1｝。因?yàn)閂1和V2具有相同的最大贊同數(shù)，在表決周期Q之前，V2中輸出結(jié)果10對(duì)應(yīng)的軟件冗余模塊通過的表決次數(shù)最高為98，所以將輸出結(jié)果10作為表決器最后輸出，同時(shí)將軟件冗余模塊的歷史記錄修正為｛90，92，95，97，99，92，88｝。

當(dāng)出現(xiàn)其他情況時(shí)，表決失效，停止，轉(zhuǎn)入失效安全狀態(tài)。

1.3 基于自檢測(cè)的自適應(yīng)一致表決系統(tǒng)結(jié)構(gòu)

基于能實(shí)現(xiàn)以上功能，本文提出了一種新的拓展表決系統(tǒng)結(jié)構(gòu)框架圖，如圖1所示。

圖1中特殊情況歷史表的作用在于當(dāng)某些大多數(shù)軟件冗余模塊的輸出是錯(cuò)誤的情況下生成了表決結(jié)果，那么同樣的系統(tǒng)發(fā)生類似的情況仍然會(huì)表決出錯(cuò)誤的結(jié)果。對(duì)這種情況進(jìn)行記錄，構(gòu)成特殊情況歷史表，并對(duì)特殊情況進(jìn)行分別計(jì)數(shù)，保留出錯(cuò)次數(shù)極高的情況，可以在重復(fù)出現(xiàn)同樣情況時(shí)作參考。

圖1 基于自檢測(cè)的自適應(yīng)一致表決系統(tǒng)結(jié)構(gòu)Fig.1 Structure of adaptive consensus voting system based on Self-test system

歷史記錄表作用在于記錄過去的表決情況，包括所有軟件冗余模塊的輸出結(jié)果，軟件冗余模塊運(yùn)行時(shí)發(fā)生瞬時(shí)錯(cuò)誤的次數(shù)，系統(tǒng)表決的結(jié)果，各個(gè)軟件冗余模塊輸出結(jié)果通過表決的次數(shù)等，為表決系統(tǒng)最終表決提供參考。

2 仿真實(shí)驗(yàn)結(jié)果及其對(duì)比分析

由文獻(xiàn)[4]的實(shí)驗(yàn)結(jié)論，得出在當(dāng)軟件冗余模塊可靠性從低到高變化的時(shí)候，基于自檢測(cè)的多數(shù)一致表決算法性能比自適應(yīng)大數(shù)表決算法性能最高提高3%，所以為了直觀說明基于自檢測(cè)的自適應(yīng)一致表決算法表決性能的優(yōu)劣，我們采用仿真方式[6]，構(gòu)造一個(gè)代碼解釋器來仿真目標(biāo)計(jì)算機(jī)，與基于自檢測(cè)的多數(shù)一致表決算法性能作比較。仿真實(shí)驗(yàn)如下:

1）將任務(wù)代碼序列{k1，k2…，kn}的一次動(dòng)態(tài)執(zhí)行等效成一個(gè)順序執(zhí)行序列{X1，X2，…，Xz}，按某種方式插入檢測(cè)代碼序列{f1，f2，…，fm}后得到的序列為{Y1，Y2，…，Yz+m}。

2）構(gòu)造的代碼解釋器能執(zhí)行像a=b op f的指令，其中a、b為變量，op為如加、減、乘、除一樣的操作符，f為整型或浮點(diǎn)常數(shù)。 模擬產(chǎn)生任務(wù)代碼序列{X1，X2，…，Xz}，Xi為代碼 ai=b+fi，fi為隨機(jī)產(chǎn)生的浮點(diǎn)數(shù)，計(jì)數(shù)器N初始值賦零，設(shè)任務(wù)代碼長(zhǎng)度L。

3）將檢測(cè)序列對(duì)DetectPair均勻插入任務(wù)代碼中，設(shè)檢測(cè)序列長(zhǎng)度l。

4）瞬時(shí)錯(cuò)誤注入。根據(jù)前面提到的等效，所以{Y1，Y2，…，Yz+m}可以被看為順序執(zhí)行結(jié)構(gòu)，在執(zhí)行時(shí)間軸上的某點(diǎn)發(fā)生錯(cuò)誤，可以等效看作代碼長(zhǎng)度空間上的某點(diǎn)發(fā)生了錯(cuò)誤。

根據(jù)實(shí)驗(yàn)需要，這里假設(shè)單個(gè)軟件冗余模塊的可靠性R=0.8，錯(cuò)誤持續(xù)時(shí)間調(diào)節(jié)因子§=10，表決器閾值g=0.5，Pi=0.9，任務(wù)代碼長(zhǎng)度L=5 000，檢測(cè)代碼長(zhǎng)度l=200，經(jīng)過錯(cuò)誤污染的軟件冗余模塊數(shù) x 分別取值 0，1，2，3，4，5，6，7，8，軟件冗余模塊總數(shù)N遠(yuǎn)大于x，每種情況運(yùn)行一萬次后得到以下數(shù)據(jù)。

表1中y表示基于自檢測(cè)的自適應(yīng)一致表決算法相對(duì)基于自檢測(cè)的一致表決算法表決性能提高百分比數(shù)。

表1 錯(cuò)誤污染軟件冗余模塊數(shù)對(duì)表決性能的影響Tab.1 Error pollution redundant module of the influence on the performance of the voting

由上表可以看出，當(dāng)軟件冗余模塊數(shù)N遠(yuǎn)大于發(fā)生瞬時(shí)錯(cuò)誤的模塊數(shù)x時(shí)，隨著發(fā)生瞬時(shí)錯(cuò)誤模塊數(shù)x的逐漸增多，y也逐漸增大。所以，基于自檢測(cè)的自適應(yīng)一致表決算法尤其適合于發(fā)生瞬時(shí)錯(cuò)誤相對(duì)較多的場(chǎng)合。

3 結(jié)束語

本文提出了一種基于自檢測(cè)的自適應(yīng)一致表決算法，它克服了自適應(yīng)大數(shù)表決算法不能容忍軟件冗余模塊在表決周期內(nèi)發(fā)生瞬時(shí)錯(cuò)誤的情況，也克服了基于自檢測(cè)的一致性表決算法在各軟件冗余模塊輸出不能達(dá)成最大一致時(shí)無法表決的情況；仿真實(shí)驗(yàn)證明了該算法相對(duì)基于自檢測(cè)的一致性表決算法具有一定的優(yōu)越性，該算法尤其適合于發(fā)生瞬時(shí)錯(cuò)誤相對(duì)較多的場(chǎng)合。

[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ì)洪.基于自檢測(cè)的多數(shù)一致表決算法[J].清華大學(xué)學(xué)報(bào)：自然科學(xué)版，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.