基于自檢測的自適應一致表決算法

俞功兵，王俊峰

（四川大學 計算機學院，四川 成都 610065）

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

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

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

1 基于自檢測的自適應一致表決算法

1.1 瞬時錯誤檢測代碼

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

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

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

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

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

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

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

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

當|V1|大于等于（n+1）/2時，以V1中的輸出結果作為參考，在Q表決周期之前，哪個輸出結果對應的軟件冗余模塊的H值大，就取該輸出結果為最后輸出結果，同時將V1中的輸出結果對應模塊的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｝，假設在Q 表 決 周 期 快 結 束 的 時 候 ，A=｛V1，V2｝， 其 中 V1=｛9.5，9.6，9.9，10，10.1｝，V2=｛10.8，11.1｝，因為|V1|=5，在表決周期Q之前，V1中輸出結果10對應的軟件冗余模塊通過的表決次數(shù)最高為98，所以將輸出結果10作為表決器最后輸出，同時將軟件冗余模塊的歷史記錄修正為｛91，93，96，99，97，91，88｝。

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

在Q表決周期快要結束時，如果具有相同的最大贊同數(shù)，且最大贊同數(shù)小于（n+1）/2。假設V1和V2具有相同的最大贊同數(shù)，那么以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具有相同的最大贊同數(shù)，在表決周期Q之前，V2中輸出結果10對應的軟件冗余模塊通過的表決次數(shù)最高為98，所以將輸出結果10作為表決器最后輸出，同時將軟件冗余模塊的歷史記錄修正為｛90，92，95，97，99，92，88｝。

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

1.3 基于自檢測的自適應一致表決系統(tǒng)結構

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

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

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

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

2 仿真實驗結果及其對比分析

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

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

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

3）將檢測序列對DetectPair均勻插入任務代碼中，設檢測序列長度l。

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

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

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

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

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

3 結束語

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

[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]周海濤，朱紀洪.基于自檢測的多數(shù)一致表決算法[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.