肖愛斌，胡明明，任憲朝，李 森，楊 樑

(1.北京控制工程研究所，北京100190;2.北京空間科技信息研究所，北京100190;3.中國空間技術(shù)研究院，北京100094)

0 引 言

工業(yè)界往往采用最小的硬件冗余來提高可靠性，只能容忍少數(shù)的幾種故障模式;國防應(yīng)用研究領(lǐng)域，尤其是載人航天器一般采用足夠的硬件冗余來提高系統(tǒng)可靠性，具備容忍所有故障模式的能力.

星載控制計算機是衛(wèi)星的關(guān)鍵部件，其可靠性直接關(guān)系到衛(wèi)星能否正常運行和完成預(yù)定任務(wù).為了保證計算機能在惡劣太空輻射環(huán)境中長期可靠工作，需要對其進行專門的加固和冗余容錯設(shè)計.對于載人航天器，由于涉及到乘員的安全性，控制計算機在完善單機設(shè)計外，通過精巧的冗余設(shè)計來增強整個計算機系統(tǒng)的容忍故障的能力尤為必要.學(xué)術(shù)界和防御研究機構(gòu)建議，對于載人航天器這樣有關(guān)鍵安全性需求的設(shè)備或系統(tǒng)可以使用足夠硬件冗余來滿足容忍任意故障模式的需求.容忍任意故障模式稱作拜占庭恢復(fù)(Byzantine resilience)[1].由于拜占庭恢復(fù)系統(tǒng)通過硬件冗余來屏蔽隱藏的未知故障引起的模塊或單機失效，因此具有極高的可靠性，使得星載計算機在關(guān)鍵安全、可靠性方面的指標(biāo)能得到有效保障.

本文采用馬爾可夫鏈分析拜占庭容錯模型的可靠性，為四模冗余拜占庭容錯計算機設(shè)計提供參考.

1 拜占庭容錯計算機模型

在容錯計算機里多機間通信是實現(xiàn)容錯的瓶頸，為盡可能減少開銷，需要采用硬件實現(xiàn)多機間的通信.采用額外硬件——網(wǎng)絡(luò)單元(NE，network element)來連接冗余多機.NE實現(xiàn)冗余多機間同步、數(shù)據(jù)通信和數(shù)據(jù)表決等容錯相關(guān)功能，而處理器負(fù)責(zé)執(zhí)行應(yīng)用程序、調(diào)度和重構(gòu)等復(fù)雜任務(wù).使用這種體系結(jié)構(gòu)就是為了解決上述3個問題:①通過獨立的硬件實現(xiàn)并維持多機間的數(shù)據(jù)一致性，避免主處理器進行頻繁的數(shù)據(jù)通信和數(shù)據(jù)表決等任務(wù)，減輕主處理器的容錯開銷;②提供多機實現(xiàn)的靈活性，使得支持異構(gòu)處理器、操作系統(tǒng)和應(yīng)用軟件的多機成為可能;③層次化的容錯策略可以使應(yīng)用軟件盡可能少的與容錯策略實現(xiàn)的細(xì)節(jié)耦合[2].

根據(jù)拜占庭恢復(fù)的理論需求，采用的拜占庭恢復(fù)容錯計算機的結(jié)構(gòu)方案[2]為:4個故障包容區(qū)域(FCR，fault containment region)，每個包含一個處理單元(PE)和一個NE，其中PE是執(zhí)行應(yīng)用程序、調(diào)度和重構(gòu)任務(wù)的單板計算機，NE是實現(xiàn)同步、數(shù)據(jù)傳遞和數(shù)據(jù)表決等容錯相關(guān)功能的硬件，4個NE通過完全連接提供1-拜占庭故障恢復(fù)，如圖1所示.

圖1 拜占庭容錯系統(tǒng)模型Fig.1 Byzantine fault tolerantmodel

此系統(tǒng)中每個處理器都連接自己的傳感器組，通過兩輪輸入一致交換使得系統(tǒng)中所有處理器都獲得此傳感器組的值(解決輸入一致問題);每個處理器都連接執(zhí)行機構(gòu)，通過仲裁算法確定某個無故障處理器當(dāng)班控制輸出(解決輸出沖突).

2 可靠性分析

本節(jié)采用馬爾可夫鏈分析拜占庭容錯模型的可靠性.系統(tǒng)失效概率記為Psysloss，可靠性定義為1-Psysloss.系統(tǒng)失效概率又可分為停機失效概率Pshutdown和不安全失效概率Punsafe，其中停機失效定義為系統(tǒng)檢測到故障的主動停機狀態(tài)，而不安全失效定義為系統(tǒng)發(fā)生故障未被檢測的不安全狀態(tài).對于空間應(yīng)用的星載計算機來說，Psysloss是Pshutdown與Punsafe的總和，由于傳統(tǒng)的容錯方法通過冗余備份能夠很好地解決系統(tǒng)停機失效的問題，因此本節(jié)的可靠性分析著重于拜占庭容錯對改善系統(tǒng)不安全失效的概率上.PE和NE的失效概率分別記為λPE和λNE，根據(jù)文獻[3]λPE的典型數(shù)值取10-4h-1;由于NE比PE簡單，因此NE的失效概率要低，根據(jù)文獻[4]λNE的值取1.4×10-5h-1.PE和NE的故障恢復(fù)率(故障恢復(fù)時間的倒數(shù))分別記為uPE和uNE，為簡便起見，uPE和uNE的值都取103h-1[5].參數(shù)fc指故障能夠被系統(tǒng)檢測到的概率，稱之為故障檢測率.對于單機系統(tǒng)，可以采用自測試、超時、重試和滾回等操作來恢復(fù)故障，其故障檢測率fc通常在0.8到0.95之間，這里取0.8來分析.本文的方案滿足1-拜占庭恢復(fù)條件[2]，因此，對于單個故障可以達到100%的檢測率，即fc=1.ft指當(dāng)發(fā)生故障時，瞬時故障所占的比率，這里取0.5.

2.1 單機系統(tǒng)可靠性分析

傳統(tǒng)單機系統(tǒng)的馬爾可夫模型如圖2所示，共包括以下4種狀態(tài):狀態(tài)1，零故障狀態(tài);狀態(tài)2，檢測故障的重試或滾回狀態(tài);狀態(tài)3，發(fā)生永久故障的停機失效狀態(tài);狀態(tài)4，未檢測故障的不安全失效狀態(tài).當(dāng)系統(tǒng)檢測到故障時進入狀態(tài)2，如果發(fā)生的是瞬時故障，系統(tǒng)通過重試或滾回操作可以恢復(fù)故障返回狀態(tài)1;如果發(fā)生的是永久故障，系統(tǒng)將進入狀態(tài)3.當(dāng)系統(tǒng)發(fā)生故障而沒有被檢測到時，系統(tǒng)進入狀態(tài)4.圖3是單機系統(tǒng)在fc=0.8時停機失效Pshutdown和不安全失效Punsafe的概率.

圖2 單機系統(tǒng)馬爾可夫鏈Fig.2 Markov chain for simplex system

單機系統(tǒng)在工作10h后Psysloss為其中為這不滿足文獻[1]中的10h運行的需求.

2.2 本文模型可靠性分析

由于本文拜占庭容錯模型的馬爾可夫鏈取決于所采用的容錯方案，下面根據(jù)不同的容錯方案分析第1節(jié)拜占庭容錯系統(tǒng)模型的可靠性.

方案1.系統(tǒng)一直工作在拜占庭恢復(fù)模式，當(dāng)出現(xiàn)第一個NE永久故障(不滿足拜占庭恢復(fù)條件)時系統(tǒng)安全停機.由于本文的系統(tǒng)模型是拜占庭恢復(fù)結(jié)構(gòu)，當(dāng)出現(xiàn)任意單個故障，系統(tǒng)都能夠容忍，也就是說fc等于1.方案1的馬爾可夫鏈如圖4所示，其中包括兩組工作狀態(tài):停機失效以及不安全失效狀態(tài).第一組工作狀態(tài)包括狀態(tài)1、2、3和5.狀態(tài)1是初始零故障狀態(tài)，當(dāng)PE故障時，系統(tǒng)轉(zhuǎn)換到狀態(tài)2(PE故障恢復(fù)狀態(tài))，相應(yīng)的，任意單個NE故障時，將使系統(tǒng)從狀態(tài)1轉(zhuǎn)換到狀態(tài)3(NE故障恢復(fù)狀態(tài)).如果上面發(fā)生的是瞬時故障，系統(tǒng)將返回狀態(tài)1;如果在狀態(tài)2或3發(fā)生第二個故障，系統(tǒng)將轉(zhuǎn)換到狀態(tài)10(不安全系統(tǒng)失效狀態(tài))，但當(dāng)發(fā)生的這兩個故障是一個FCR內(nèi)的PE和NE時系統(tǒng)轉(zhuǎn)移到狀態(tài)5.狀態(tài)5同時存在PE和NE故障，此時將首先恢復(fù)NE故障.在狀態(tài)3和狀態(tài)5時，如果發(fā)生的是NE永久故障，將導(dǎo)致系統(tǒng)轉(zhuǎn)換到狀態(tài)11(停機失效狀態(tài))，因為NE故障意味著相應(yīng)的FCR故障，此時無故障FCR不滿足最少拜占庭恢復(fù)的基數(shù)需求.在狀態(tài)5，重構(gòu)一個瞬時NE故障將返回狀態(tài)2.如果狀態(tài)2的PE是永久故障，系統(tǒng)將進入狀態(tài)4.

狀態(tài)4時系統(tǒng)進入第二組工作狀態(tài)(狀態(tài)4、6、7、8和9)，此時系統(tǒng)包含3個工作PE和4個工作NE，系統(tǒng)仍然滿足1-拜占庭恢復(fù)條件，因此仍然能夠容忍任意單個故障.其中3個處理器提供故障屏蔽能力，4個NE滿足1-拜占庭恢復(fù)的基數(shù)、互連和同步需求.因此，狀態(tài)4是降級拜占庭恢復(fù)結(jié)構(gòu)的初始狀態(tài).

在狀態(tài)4，PE故障將轉(zhuǎn)換到狀態(tài)6，如果發(fā)生的是瞬時故障，系統(tǒng)將返回狀態(tài)4;如果是永久故障，系統(tǒng)將進入停機失效狀態(tài).如果在狀態(tài)6時又發(fā)生一個部件故障將使得系統(tǒng)進入不安全失效狀態(tài).同樣，如果發(fā)生的是PE/NE故障對，使得系統(tǒng)進入狀態(tài)9.在狀態(tài)4，如果帶有工作PE的NE故障將進入狀態(tài)8，如果發(fā)生的是瞬時故障，系統(tǒng)返回狀態(tài)4，否則進入停機狀態(tài).在狀態(tài)8，如果又發(fā)生故障，系統(tǒng)進入不安全失效狀態(tài).同樣，PE/NE對失效時進入狀態(tài)9.在狀態(tài)4時，如果不含PE的NE故障，系統(tǒng)將進入狀態(tài)7，狀態(tài)7和狀態(tài)8不同的是它不能進入狀態(tài)9(PE/NE故障狀態(tài)).狀態(tài)9和狀態(tài)5一樣，系統(tǒng)首先恢復(fù)NE，如果成功恢復(fù)則進入狀態(tài)6，否則進入狀態(tài)11.此方案中，如圖5所示.

從圖5中可以看出，Punsafe比Pshutdown低5個數(shù)量級，因此Psysloss基本等于Pshutdown的值.在10h運行后，這比單模系統(tǒng)的Pshutdown還高，這是因為系統(tǒng)的4個FCR中有一個FCR故障的概率比單模系統(tǒng)FCR故障的概率要高.但如果系統(tǒng)仍有冗余備份資源，通過對故障機的替換繼續(xù)工作在拜占庭恢復(fù)模式，可以使系統(tǒng)停機失效的概率即Pshutdown的值接近于0，此時系統(tǒng)失效的概率基本等于不安全失效的概率即

圖4 方案1的馬爾可夫鏈Fig.4 Markov chains for redundancy scheme 1

圖5 方案1的 P shutdown和 P unsafe概率Fig.5 P shutdown and P unsafe for redundancy scheme 1

方案2.當(dāng)出現(xiàn)第一個NE永久故障時系統(tǒng)降級為單模系統(tǒng)繼續(xù)工作.在圖4的基礎(chǔ)上將狀態(tài)11替換為圖6的4個狀態(tài)，即可得到此方案的馬爾可夫鏈，其中如圖7所示.10h運行后，h-1，這比方案1要低好幾個數(shù)量級，但是比方案1要高一個數(shù)量級，這是因為方案2允許系統(tǒng)在非拜占庭恢復(fù)模式工作，這降低了Pshutdown，同時增加了Punsafe.

圖6 方案2增加的馬爾可夫鏈Fig.6 Additive Markov chains for redundancy scheme 2

方案3.當(dāng)出現(xiàn)第一個NE永久故障時系統(tǒng)降級為三模系統(tǒng)繼續(xù)工作，當(dāng)出現(xiàn)第二個NE永久故障時系統(tǒng)安全停機.在圖4的基礎(chǔ)上，將狀態(tài)11替換為圖8的8個狀態(tài)，即可得到此方案的馬爾可夫鏈.圖8中狀態(tài)11是3個FCR工作狀態(tài)，從圖4的狀態(tài)3、5、7中而來.這里的狀態(tài)13、14和圖4中的狀態(tài)2、3相似，所不同的是，三模系統(tǒng)是非拜占庭恢復(fù)結(jié)構(gòu)，當(dāng)系統(tǒng)發(fā)生拜占庭故障時系統(tǒng)不能檢測.因此在狀態(tài)11時，如果發(fā)生檢測到的NE故障，系統(tǒng)進入狀態(tài)13(NE故障恢復(fù)狀態(tài));否則，如果發(fā)生未檢測的拜占庭故障，系統(tǒng)將進入狀態(tài)18.同樣，如果發(fā)生檢測的PE故障，系統(tǒng)進入狀態(tài)14，否則，系統(tǒng)進入狀態(tài)18.圖8中狀態(tài)12是4個NE和兩個PE工作狀態(tài)，這是從圖4的狀態(tài)6進入的，也不滿足拜占庭恢復(fù)條件.

圖7 方案2的 P shutdown和 P unsafe概率Fig.7 P shutdown and P unsafe for redundancy scheme 2

圖8 方案3增加的馬爾可夫鏈Fig.8 Additive Markov chains for redundancy scheme 3

不同容錯方案在工作10h的可靠性分析總結(jié)如表1所示.

表1 可靠性分析總結(jié)Tab.1 Reliability analysis summary h-1

3 結(jié) 論

通過本文分析可以看出，工作在拜占庭恢復(fù)模式下系統(tǒng)具有最小的不安全失效概率.如果系統(tǒng)有額外備份資源可用，通過對故障機的替換，系統(tǒng)就不會發(fā)生停機失效，因此系統(tǒng)的失效概率等于不安全失效的概率，所以系統(tǒng)一直工作在拜占庭恢復(fù)模式可以獲得最高的可靠性.如果系統(tǒng)沒有額外的備份資源，通過降級工作在非拜占庭恢復(fù)模式下，這可以降低系統(tǒng)停機失效的概率，同時增加系統(tǒng)的不安全失效概率，當(dāng)兩者的和最小時系統(tǒng)獲得最高可靠性.因此，系統(tǒng)采用何種方案降級工作取決于系統(tǒng)Pshutdown和Punsafe之間的關(guān)系.

圖9 方案3的 P shutdown和 P unsafe概率Fig.9 P shutdown and P unsafe for redundancy scheme 3

[1]LALA JH，HARPER R E.Architectural principles for safety-critical real-time applications[C]//Proceedings of the IEEE.Cambridge:IEEE，1994:25-40.

[2]XIAO A B，YANG M F，LIU B.Design and validation of Byzantine fault tolerance for on-board computer[J].Aerospace Control and Application， 2008，34(4):17-22.

[3]WENSLEY J.SIFT:the design and analysis of a fault tolerant computer for aircraft control[C]//Proceedings of the IEEE.Cambridge:IEEE，1978:1240-1255.

[4]HARPER R.Critical issues in ultra-reliable parallel processing[D].Cambridge:Massachusetts Institute of Technology，1987.

[5]HOPKINS A L，SMITH T B，LALA J H.FTMP-A highly reliable fault-tolerant multiprocessor for aircraft[C]//Proceedings of the IEEE.Cambridge:IEEE，1978:1221-1239.