郁 湧,黃宇鑫,陳 浩

1(云南大學(xué) 軟件學(xué)院,昆明 650091)2(云南省軟件工程重點(diǎn)實(shí)驗(yàn)室,昆明 650091)

當(dāng)今,以高速通信、海量存儲(chǔ)和高性能計(jì)算為核心的信息基礎(chǔ)設(shè)施已經(jīng)廣泛深入地滲透到經(jīng)濟(jì)、政治、軍事和社會(huì)文化生活的各個(gè)層面,成為現(xiàn)代生產(chǎn)力發(fā)展和人類文明進(jìn)步不可或缺的強(qiáng)大工具.在眾多應(yīng)用背景的推動(dòng)下,軟件的復(fù)雜度和規(guī)模都在以前所未有的速度在不斷延伸,在金融、國(guó)防、政府和通信等關(guān)鍵領(lǐng)域的各種復(fù)雜應(yīng)用需求背景下,軟件是否可信已經(jīng)成為衡量軟件系統(tǒng)的重要指標(biāo).然而,作為計(jì)算機(jī)技術(shù)的核心和基礎(chǔ)之一的軟件系統(tǒng),其生產(chǎn)現(xiàn)狀和質(zhì)量一直不能令人滿意,尤其是應(yīng)用于航空航天、核電及國(guó)防等領(lǐng)域的安全關(guān)鍵軟件系統(tǒng),其失效常常會(huì)對(duì)人類和環(huán)境造成嚴(yán)重的乃至災(zāi)難性的后果.早在1991年,Laprie就從安全關(guān)鍵系統(tǒng)的研究出發(fā)提出了軟件可依賴性(Dependability)的概念[1].1997年美國(guó)國(guó)家科學(xué)技術(shù)委員會(huì)在《高可信系統(tǒng)的研究挑戰(zhàn)》中明確提出了高可信性(High Confidence)的概念[2].我國(guó)學(xué)者陳火旺、王戟等認(rèn)為高可信軟件在系統(tǒng)提供服務(wù)時(shí)應(yīng)能滿足一系列可靠安全性、實(shí)時(shí)性、可靠性、容錯(cuò)性、保密性等關(guān)鍵性質(zhì)[3].可信軟件作為軟件領(lǐng)域最具挑戰(zhàn)性和價(jià)值的研究課題之一,引起了國(guó)內(nèi)外學(xué)者的高度重視.

軟件容錯(cuò)是提高系統(tǒng)可信性的一種實(shí)現(xiàn)技術(shù)之一,其相關(guān)的研究方面主要分為兩大類:軟件冗余和時(shí)間冗余[4-6].軟件冗余是在系統(tǒng)設(shè)計(jì)時(shí),增補(bǔ)一些部件或模塊,使得即使其中一個(gè)部件發(fā)生故障,而整個(gè)系統(tǒng)照樣完成規(guī)定的任務(wù).從冗余的范圍來(lái)看,分為元件冗余、部件冗余、子系統(tǒng)冗余等.從部件聯(lián)接形式來(lái)分,可分為并聯(lián)、旁聯(lián)、表決系統(tǒng)等.多版本編程利用完成同一功能的不同實(shí)現(xiàn)之間的多樣性互補(bǔ)容錯(cuò),也是一種常見(jiàn)的軟件冗余容錯(cuò)方法.而時(shí)間冗余方面則是基于失敗重做(Retry-on-failure)的思想,如在系統(tǒng)進(jìn)行設(shè)計(jì)和實(shí)現(xiàn)時(shí)設(shè)置檢查點(diǎn)和回滾機(jī)制,當(dāng)發(fā)生故障就回滾到適當(dāng)?shù)臋z查點(diǎn)重新執(zhí)行[7].Reis等人在編譯器級(jí)別通過(guò)指令復(fù)制和合并對(duì)軟件進(jìn)行版本冗余從而可以在設(shè)置的同步點(diǎn)檢查指令的一致性,具有較好的容錯(cuò)效果和執(zhí)行效率,但其實(shí)現(xiàn)較為復(fù)雜[6].文獻(xiàn)[8]通過(guò)動(dòng)態(tài)監(jiān)控和回滾技術(shù),建立了合適的還原點(diǎn)來(lái)對(duì)系統(tǒng)進(jìn)行監(jiān)控,使系統(tǒng)能夠及時(shí)恢復(fù)到預(yù)先的還原點(diǎn).文獻(xiàn)[9]為提高軟件的可靠性和生存能力,分析了模塊化對(duì)可靠性的影響提出一種基于進(jìn)化計(jì)算的可進(jìn)化模塊冗余軟件混合容錯(cuò)模型.文獻(xiàn)[10]設(shè)計(jì)了一種基于網(wǎng)絡(luò)控制的可編程控制器冗余系統(tǒng),使得雙機(jī)軟件冗余系統(tǒng)更加穩(wěn)定.文獻(xiàn)[11]給出了一種基于三取二冗余結(jié)構(gòu)的安全計(jì)算機(jī)系統(tǒng).

在現(xiàn)代軟件工程技術(shù)中,系統(tǒng)構(gòu)件化已經(jīng)成為軟件技術(shù)總體發(fā)展趨勢(shì)之一[12],基于構(gòu)件的軟件開(kāi)發(fā)技術(shù)尤其得到了廣泛發(fā)展[13].為了能夠提高基于構(gòu)件的軟件系統(tǒng)的可信性,本文在分析系統(tǒng)結(jié)構(gòu)冗余和可信性關(guān)系的基礎(chǔ)上在基于構(gòu)件的軟件系統(tǒng)中提出一種構(gòu)件結(jié)構(gòu)冗余的方法并對(duì)其可靠性進(jìn)行性能分析.

1 軟件結(jié)構(gòu)冗余及其對(duì)可信性的影響

軟件系統(tǒng)的可信性質(zhì)是指該系統(tǒng)需要滿足的關(guān)鍵性質(zhì),包括可靠性(reliability)、可靠安全性(safety)、保密安全性(security)、生存性(survivability)、容錯(cuò)性(fault tolerance)等等,當(dāng)軟件一旦違背這些關(guān)鍵性質(zhì)會(huì)造成不可容忍的損失時(shí),稱這些性質(zhì)為系統(tǒng)的高可信性質(zhì)[3].構(gòu)建的軟件系統(tǒng)不夠可信的原因就是故障的存在,故障的存在說(shuō)明軟件系統(tǒng)內(nèi)部有缺陷的部件.軟件系統(tǒng)故障的種類很多,退化故障就是其中常見(jiàn)的一種.當(dāng)系統(tǒng)內(nèi)的一個(gè)部件發(fā)生失效,不再工作了,則認(rèn)為發(fā)生了退化故障.軟件系統(tǒng)中的退化故障可能是活動(dòng)的,也可能是休眠的;可能是瞬時(shí)性的,也可能是永久性的故障.為了降低軟件故障的發(fā)生率,如果能夠識(shí)別或者在進(jìn)行系統(tǒng)設(shè)計(jì)時(shí)確定系統(tǒng)中可能發(fā)生故障的關(guān)鍵部件,預(yù)先進(jìn)行調(diào)節(jié),并確保失效部件的影響不會(huì)帶來(lái)使系統(tǒng)發(fā)生失效的輸出,系統(tǒng)本身就不會(huì)失效.

軟件系統(tǒng)需要對(duì)退化故障進(jìn)行處理,系統(tǒng)的容錯(cuò)是處理退化故障的方法之一.容錯(cuò)性就是指軟件在故障出現(xiàn)時(shí)保證提供服務(wù)的能力,對(duì)退化故障進(jìn)行容錯(cuò)的一種處理方式就是依靠冗余.所謂軟件的冗余技術(shù)主要就是指在軟件設(shè)計(jì)和實(shí)現(xiàn)中,除了完成系統(tǒng)本身所需的功能外,為了能夠提高系統(tǒng)的性能及可靠性等而額外增加一些合理的部件和程序代碼的技術(shù).

基于構(gòu)件的可信軟件系統(tǒng)中,構(gòu)件是具有一定規(guī)模、相對(duì)獨(dú)立、可替換的單元,它具有較穩(wěn)定的組成模式,完成一項(xiàng)確定、可區(qū)分的功能,并遵從和提供一套接口以及這些接口的實(shí)現(xiàn).構(gòu)件是軟件系統(tǒng)的構(gòu)成要素,同時(shí)也是軟件的承載體,一個(gè)構(gòu)件應(yīng)該包括兩個(gè)部分:接口和實(shí)現(xiàn).其中接口部分定義了構(gòu)件所提供的功能并規(guī)范了功能的使用方法;而實(shí)現(xiàn)部分包括了構(gòu)件所能提供的一系列相關(guān)操作.在基于構(gòu)件的可信軟件結(jié)構(gòu)設(shè)計(jì)中,構(gòu)件冗余就是對(duì)可能會(huì)出現(xiàn)故障的關(guān)鍵構(gòu)件進(jìn)行多個(gè)備份;但是,冗余并不意味著簡(jiǎn)單的備份,冗余意味著一個(gè)構(gòu)件有多個(gè)功能相同的構(gòu)件是可用的,超過(guò)提供服務(wù)所需的部件數(shù)量,當(dāng)其中一些構(gòu)件發(fā)生失效時(shí),其他的冗余部件可以繼續(xù)提供服務(wù),從而保證軟件系統(tǒng)運(yùn)行的可信性.在系統(tǒng)中,如果兩個(gè)構(gòu)件A1和構(gòu)件A2所實(shí)現(xiàn)的功能和對(duì)應(yīng)接口完全一樣,則稱構(gòu)件A1和構(gòu)件A2是相互冗余的構(gòu)件,相互冗余的構(gòu)件的規(guī)約和消息傳遞機(jī)制必修一致.一個(gè)存在冗余構(gòu)件的系統(tǒng)在合理調(diào)用的情況下不僅不會(huì)影響系統(tǒng)的實(shí)現(xiàn),而且會(huì)提高系統(tǒng)的容錯(cuò)能力,滿足系統(tǒng)可信性的要求.相同冗余構(gòu)件的運(yùn)行要在確定的系統(tǒng)環(huán)境和相同輸入的情況下,才能得以正確運(yùn)行;否則,存在外界的影響會(huì)產(chǎn)生錯(cuò)誤的結(jié)果.當(dāng)一個(gè)構(gòu)件產(chǎn)生故障時(shí),繼續(xù)提供服務(wù)的構(gòu)件需要進(jìn)行數(shù)據(jù)和環(huán)境的檢測(cè)和重新配置來(lái)保證系統(tǒng)運(yùn)行的一致性.

為了保證基于構(gòu)件的可信軟件系統(tǒng)中的構(gòu)件冗余結(jié)構(gòu)的可靠性在運(yùn)行過(guò)程中能夠得到合理有效地驗(yàn)證,需要具有一個(gè)稱之為信任根的構(gòu)件,信任根構(gòu)件是系統(tǒng)的可信啟動(dòng)模塊,可以存放構(gòu)件的標(biāo)識(shí)和編號(hào)、構(gòu)件的信息摘要以及構(gòu)件冗余信息的存儲(chǔ)等重要數(shù)據(jù),同時(shí)也可以用來(lái)對(duì)冗余構(gòu)件的運(yùn)行情況就行實(shí)時(shí)檢測(cè),從而判斷各個(gè)構(gòu)件運(yùn)行是否正常.基于冗余機(jī)制的可信軟件框架如圖1所示.

圖1 基于冗余機(jī)制的可信軟件框架

2 單個(gè)構(gòu)件的雙模冗余結(jié)構(gòu)及性能分析

一個(gè)具有雙模冗余結(jié)構(gòu)的系統(tǒng)是指在系統(tǒng)中存在兩個(gè)完全冗余的構(gòu)件;在此系統(tǒng)中,兩個(gè)相同構(gòu)件并行運(yùn)行,并將結(jié)果進(jìn)行檢測(cè).兩個(gè)在相同輸入和相同環(huán)境的情況下運(yùn)行,所產(chǎn)生的運(yùn)行結(jié)果應(yīng)該是一樣的.一種普遍使用的簡(jiǎn)單雙模冗余結(jié)構(gòu)如圖2所示.

圖2 構(gòu)件的雙冗余結(jié)構(gòu)

在基于構(gòu)件的軟件系統(tǒng)中,對(duì)于系統(tǒng)中的關(guān)鍵或者核心構(gòu)件,為了保證運(yùn)行過(guò)程中所產(chǎn)生的故障能夠被及時(shí)發(fā)現(xiàn),提高系統(tǒng)容錯(cuò)階段的檢測(cè)能力,可以對(duì)其進(jìn)行雙模冗余結(jié)構(gòu)設(shè)計(jì).

在進(jìn)行雙模冗余結(jié)構(gòu)的設(shè)計(jì)時(shí),兩個(gè)完全冗余的構(gòu)件A1和構(gòu)件A2的輸入必須相同,即在進(jìn)行消息傳遞時(shí),需要把同一消息傳遞給冗余的構(gòu)件.雙模冗余結(jié)構(gòu)的錯(cuò)誤檢測(cè)是通過(guò)比較兩個(gè)冗余構(gòu)件的輸出結(jié)果來(lái)完成的.如果輸出不同,那么就是發(fā)生了錯(cuò)誤.但是,通過(guò)錯(cuò)誤檢測(cè)無(wú)法確定是哪個(gè)構(gòu)件發(fā)生了故障.如果輸出的結(jié)果完全相同,則說(shuō)明系統(tǒng)沒(méi)有發(fā)生故障,此時(shí)只需要把其中一個(gè)輸出傳遞給下一個(gè)構(gòu)件即可.

一個(gè)雙模冗余結(jié)構(gòu)會(huì)對(duì)系統(tǒng)的可信性產(chǎn)生影響,因?yàn)閱蝹€(gè)構(gòu)件的運(yùn)行結(jié)果無(wú)論是否正確都不可能完成故障和錯(cuò)誤檢測(cè),錯(cuò)誤狀態(tài)產(chǎn)生而未被檢測(cè)出來(lái),將會(huì)給系統(tǒng)帶來(lái)無(wú)限的負(fù)面影響,而雙模冗余結(jié)構(gòu)是一種最簡(jiǎn)單提供了錯(cuò)誤檢測(cè)的能力的方法.

雙模冗余結(jié)構(gòu)的可靠性分析:假設(shè)兩個(gè)完全冗余的構(gòu)件A1和構(gòu)件A2獨(dú)立運(yùn)行,兩個(gè)構(gòu)件產(chǎn)生故障的概率相同都為p,由于構(gòu)件A1和構(gòu)件A2建立的是個(gè)并聯(lián)系統(tǒng),則系統(tǒng)運(yùn)行中檢測(cè)出故障的概率為兩個(gè)完全冗余的構(gòu)件A1和構(gòu)件A2運(yùn)行中,一個(gè)產(chǎn)生故障而另一個(gè)沒(méi)有產(chǎn)生故障而整體被檢測(cè)成產(chǎn)生故障的概率為

從雙模冗余結(jié)構(gòu)的性能分析結(jié)果可以看出,該結(jié)構(gòu)與不用冗余結(jié)構(gòu)相比可能會(huì)增加系統(tǒng)整體被檢測(cè)出故障的概率,因?yàn)闊o(wú)法判斷哪個(gè)構(gòu)件產(chǎn)生故障,所以一個(gè)構(gòu)件故障而另一個(gè)沒(méi)有故障產(chǎn)生時(shí)的結(jié)果會(huì)判定為系統(tǒng)產(chǎn)生故障.

對(duì)于雙模冗余結(jié)構(gòu),如果在系統(tǒng)運(yùn)行過(guò)程中能夠收集系統(tǒng)產(chǎn)生故障的可能環(huán)境或情況,在對(duì)應(yīng)情況下才進(jìn)行兩個(gè)完全冗余的構(gòu)件的調(diào)用,否則只需要進(jìn)行其中一個(gè)構(gòu)件的調(diào)用,這樣就可以提高運(yùn)行效率.

3 組合構(gòu)件的雙模冗余結(jié)構(gòu)及性能分析

軟件系統(tǒng)中的構(gòu)件可能具有多種關(guān)系,比如并聯(lián)、串聯(lián)等,對(duì)于多個(gè)需要進(jìn)行冗余處理的關(guān)鍵構(gòu)件,為了能夠得到更好的效果,可以對(duì)其進(jìn)行冗余的組合.本論文主要對(duì)兩個(gè)構(gòu)件的并聯(lián)、串聯(lián)的組合關(guān)系進(jìn)行分析,對(duì)多個(gè)構(gòu)件的關(guān)系可以進(jìn)行相似處理.

3.1 兩個(gè)串聯(lián)構(gòu)件的雙模冗余方式及性能分析

對(duì)于兩個(gè)串聯(lián)構(gòu)件的冗余主要有兩種方式,如圖3和圖4所示,圖中相同冗余構(gòu)件用不同的下標(biāo)表示,如構(gòu)件A1構(gòu)件A2和構(gòu)件A3是三個(gè)相同的冗余構(gòu)件,構(gòu)件B1和構(gòu)件B2是兩個(gè)相同的冗余構(gòu)件,其他以此類推.

對(duì)于串聯(lián)構(gòu)件雙模冗余方式一,兩個(gè)構(gòu)件串聯(lián)運(yùn)行之后再檢測(cè)其運(yùn)行結(jié)果是否相同來(lái)確定是否有故障發(fā)生,把兩個(gè)構(gòu)件看成一個(gè)整體來(lái)檢測(cè),檢測(cè)數(shù)量會(huì)變少,但是就算檢測(cè)出存在故障,也不知道是哪個(gè)構(gòu)件造成的故障.

圖3 串聯(lián)構(gòu)件雙模冗余方式一

圖4 串聯(lián)構(gòu)件雙模冗余方式二

若構(gòu)件A1和構(gòu)件A2的故障概率為p1,構(gòu)件B1和構(gòu)件B2的故障概率為p2,且構(gòu)件A1和構(gòu)件A2、構(gòu)件B1和構(gòu)件B2的運(yùn)行都是獨(dú)立的,則構(gòu)件A1和構(gòu)件B1串聯(lián)時(shí)產(chǎn)生故障的概率為:

此時(shí),構(gòu)件A1、構(gòu)件A2、構(gòu)件B1和構(gòu)件B2中只要有一個(gè)構(gòu)件產(chǎn)生故障,檢測(cè)器就是認(rèn)為系統(tǒng)發(fā)生故障,其概率為:

對(duì)于串聯(lián)構(gòu)件雙模冗余方式二,兩個(gè)串聯(lián)的構(gòu)件分別運(yùn)行之后就檢測(cè)其運(yùn)行結(jié)果是否相同來(lái)確定是否有故障發(fā)生,把兩個(gè)構(gòu)件分開(kāi)來(lái)進(jìn)行檢測(cè),檢測(cè)數(shù)量會(huì)增加,可以根據(jù)檢測(cè)結(jié)果知道是構(gòu)件A1或A2還是構(gòu)件B1或B2造成了系統(tǒng)故障.

對(duì)應(yīng)方式2的串聯(lián)構(gòu)件雙模冗余,若構(gòu)件A1和構(gòu)件A2,構(gòu)件B1和構(gòu)件B2分別進(jìn)行檢測(cè),運(yùn)行中檢測(cè)出故障的概率分別為

對(duì)于兩個(gè)冗余檢測(cè)之間是串聯(lián)關(guān)系,此時(shí),構(gòu)件A1和構(gòu)件A2檢測(cè)出故障就不用運(yùn)行構(gòu)件B1和構(gòu)件B2,因此構(gòu)件B1和構(gòu)件B2也不需要檢測(cè).只有構(gòu)件A1和構(gòu)件A2運(yùn)行無(wú)故障時(shí)才需要運(yùn)行構(gòu)件B1和構(gòu)件B2并對(duì)其進(jìn)行檢測(cè).因此,運(yùn)行中檢測(cè)出產(chǎn)生故障的概率為:

從上可知道,串聯(lián)構(gòu)件采取哪種冗余方式與串聯(lián)的兩個(gè)構(gòu)件產(chǎn)生故障的概率有關(guān),可以根據(jù)情況進(jìn)行選擇.

3.2 兩個(gè)并串聯(lián)構(gòu)件的雙模冗余方式及性能分析

對(duì)于兩個(gè)并聯(lián)構(gòu)件的雙模冗余主要有兩種方式,如圖5和圖6所示.

對(duì)于并聯(lián)構(gòu)件雙模冗余方式一,兩個(gè)并聯(lián)關(guān)系的構(gòu)件A1和構(gòu)件B1以及并聯(lián)關(guān)系的構(gòu)件A2和構(gòu)件B2先并聯(lián)運(yùn)行,之后再把兩組并聯(lián)構(gòu)件運(yùn)行的結(jié)果進(jìn)行檢測(cè)來(lái)確定是否有故障發(fā)生,此時(shí)把兩個(gè)并聯(lián)關(guān)系的構(gòu)件看成一個(gè)整體來(lái)檢測(cè),檢測(cè)數(shù)量會(huì)變少,但是只要構(gòu)件A1、構(gòu)件A2、構(gòu)件B1和構(gòu)件B2中一個(gè)構(gòu)件發(fā)生故障,都會(huì)認(rèn)為系統(tǒng)出現(xiàn)故障.就算檢測(cè)出存在故障,也不知道是構(gòu)件A1或A2還是構(gòu)件B1或B2造成的故障.

圖5 并聯(lián)構(gòu)件雙模冗余方式一

圖6 并聯(lián)構(gòu)件雙模冗余方式二

若構(gòu)件A1和構(gòu)件A2的故障概率為p1,構(gòu)件B1和構(gòu)件B2的故障概率為p2,且構(gòu)件A1、構(gòu)件A2、構(gòu)件B1和構(gòu)件B2的運(yùn)行都是獨(dú)立的.雖然構(gòu)件A1和構(gòu)件B1是并聯(lián)關(guān)系,但是其中只要一個(gè)產(chǎn)生故障,均認(rèn)為系統(tǒng)產(chǎn)生故障,因此構(gòu)件A1和構(gòu)件B1并聯(lián)時(shí)產(chǎn)生故障的概率為:

此情況下,兩組并聯(lián)構(gòu)件運(yùn)行結(jié)果不一致,經(jīng)檢測(cè)器檢測(cè)認(rèn)為出現(xiàn)故障的概率為:

對(duì)于并聯(lián)構(gòu)件雙模冗余方式二,先對(duì)構(gòu)件A1和構(gòu)件A2以及構(gòu)件B1和構(gòu)件B2進(jìn)行冗余處理,構(gòu)件A1和構(gòu)件A2以及構(gòu)件B1和構(gòu)件B2的故障檢測(cè)互不影響,根據(jù)各次檢測(cè)的結(jié)果來(lái)確定是那組構(gòu)件產(chǎn)生故障.

若構(gòu)件A1和構(gòu)件A2的故障概率為p1,構(gòu)件B1和構(gòu)件B2的故障概率為p2,且構(gòu)件A1、構(gòu)件A2、構(gòu)件B1和構(gòu)件B2的運(yùn)行都是獨(dú)立的,則構(gòu)件A1和構(gòu)件A2并聯(lián)時(shí)產(chǎn)生故障的概率為:

此情況下,只要一個(gè)檢測(cè)器檢測(cè)出故障,均認(rèn)為出現(xiàn)故障,其概率為:

4 構(gòu)件的三取二冗余結(jié)構(gòu)及其擴(kuò)展

4.1 三取二冗余結(jié)構(gòu)

構(gòu)件的雙模冗余結(jié)構(gòu)只能檢測(cè)出系統(tǒng)是否出現(xiàn)故障卻不能判斷具體哪個(gè)構(gòu)件出現(xiàn)故障,而三取二冗余結(jié)構(gòu)是一種基于三取二表決原理的三模冗余架構(gòu),如圖7所示.

圖7 構(gòu)件的三取二冗余結(jié)構(gòu)

三取二冗余結(jié)構(gòu)不僅能夠檢測(cè)出系統(tǒng)的故障,而且能夠按照表決原理來(lái)確定哪個(gè)出現(xiàn)故障,其檢測(cè)和處理有2種方式.

方式一是先只運(yùn)行其中的兩個(gè)冗余構(gòu)件,如果運(yùn)行結(jié)果一致則直接運(yùn)行下一構(gòu)件;如果運(yùn)行結(jié)果不一致,說(shuō)明至少其中一個(gè)構(gòu)件產(chǎn)生故障,此時(shí)再運(yùn)行第三個(gè)冗余構(gòu)件,若三個(gè)冗余構(gòu)件運(yùn)行結(jié)果中有兩個(gè)結(jié)果是相同的,則把它當(dāng)成正確結(jié)果傳輸給下一個(gè)構(gòu)件,否則就認(rèn)為產(chǎn)生了故障.

方式二是在該結(jié)構(gòu)中,同時(shí)運(yùn)行三個(gè)冗余構(gòu)件,當(dāng)且僅當(dāng) 2個(gè)以上的構(gòu)件同時(shí)出現(xiàn)故障時(shí)( 發(fā)生概率較低)才會(huì)認(rèn)為出現(xiàn)故障,即三個(gè)冗余構(gòu)件運(yùn)行結(jié)果中,只要有2個(gè)及以上結(jié)果一致就把該結(jié)果當(dāng)成正確結(jié)果傳輸給下一個(gè)構(gòu)件.

三取二冗余結(jié)構(gòu)不僅可以有效保證冗余構(gòu)件的退化故障而導(dǎo)致的錯(cuò)誤能夠被檢測(cè)出來(lái),而且在故障產(chǎn)生的情況下判斷正確的運(yùn)行結(jié)果.這一特點(diǎn)與雙模冗余結(jié)構(gòu)中的錯(cuò)誤檢測(cè)形成鮮明對(duì)比,如果三個(gè)冗余構(gòu)件中只有一個(gè)產(chǎn)生故障,三取二冗余結(jié)構(gòu)都可以檢測(cè)出來(lái)并給出正確的運(yùn)行結(jié)果,因此,三取二冗余結(jié)構(gòu)可以對(duì)軟件的故障結(jié)構(gòu)進(jìn)行屏蔽.

在三取二冗余結(jié)構(gòu)中,假設(shè)三個(gè)完全冗余的構(gòu)件A1、構(gòu)件A2和構(gòu)件A3獨(dú)立運(yùn)行,它們產(chǎn)生故障的概率相同都為p,構(gòu)件A1、構(gòu)件A2和構(gòu)件A3建立的是并聯(lián)系統(tǒng),則系統(tǒng)運(yùn)行中檢測(cè)出故障的概率為此時(shí)出現(xiàn)故障被檢測(cè)出來(lái)的概率將會(huì)大幅增加.

三個(gè)完全冗余的構(gòu)件A1、構(gòu)件A2和構(gòu)件A3運(yùn)行中,三取二冗余結(jié)構(gòu)被認(rèn)為產(chǎn)生故障的概率為

4.2 三取二冗余結(jié)構(gòu)的擴(kuò)展

為了提高系統(tǒng)可靠性,也可采用四重化冗余結(jié)構(gòu)和二乘三取二冗余結(jié)構(gòu).四重化冗余結(jié)構(gòu)主要使用四個(gè)完全相同的構(gòu)件來(lái)搭建冗余結(jié)構(gòu),通過(guò)一定的邏輯關(guān)系來(lái)使可信性全面提高的一種技術(shù),其如圖8所示.

圖8 四重化冗余結(jié)構(gòu)

四個(gè)構(gòu)件被分為兩組,每組有兩個(gè)構(gòu)件和一個(gè)檢測(cè)器,整個(gè)四重化冗余結(jié)構(gòu)即由這兩個(gè)相同的系組成,每個(gè)系的運(yùn)行與檢測(cè)方式與雙模冗余結(jié)構(gòu)相同.在系統(tǒng)運(yùn)行過(guò)程中,只有一系有計(jì)算輸出而另一系為備用,當(dāng)工作的系失效之后,才進(jìn)行不同系之間的切換.

二乘三取二冗余結(jié)構(gòu)原理與四重化冗余結(jié)構(gòu)相似,冗余系統(tǒng)也由兩個(gè)系組成,只不過(guò)每個(gè)系就是一個(gè)三取二冗余結(jié)構(gòu).

四重化冗余結(jié)構(gòu)和二乘三取二冗余結(jié)構(gòu)能夠提高系統(tǒng)的可靠性和安全性,但是大量冗余結(jié)構(gòu)也會(huì)使得冗余機(jī)制實(shí)現(xiàn)起來(lái)比較復(fù)雜,增加了系統(tǒng)運(yùn)行的成本.

對(duì)于三取二冗余結(jié)構(gòu)也可以擴(kuò)展成為n-模冗余的結(jié)構(gòu),如圖9所示.該結(jié)構(gòu)運(yùn)行結(jié)果的檢測(cè)和正確運(yùn)行結(jié)果的判定方式與三取二冗余結(jié)構(gòu)相似,可以采取少數(shù)服從多數(shù)原則.

圖9 構(gòu)件 n 模冗余結(jié)構(gòu)

同時(shí),對(duì)于三取二冗余結(jié)構(gòu)和n模冗余結(jié)構(gòu)都可以考慮構(gòu)件之間的并串聯(lián)關(guān)系,但是具體分析方式與上面的原理相似,故在此就不在重復(fù)分析.

在具有冗余機(jī)制的可信軟件系統(tǒng)中,可以采用奇偶校驗(yàn)、錯(cuò)誤檢測(cè)、完整性檢測(cè)和HASH函數(shù)等方式來(lái)對(duì)冗余構(gòu)件運(yùn)行結(jié)果進(jìn)行檢測(cè),同時(shí)根據(jù)檢測(cè)的結(jié)果來(lái)確定構(gòu)件在運(yùn)行過(guò)程中是否存在失效問(wèn)題.當(dāng)系統(tǒng)中的一個(gè)構(gòu)件產(chǎn)生故障或者失效時(shí),可以利用恢復(fù)塊策略、檢查點(diǎn)技術(shù)等方法來(lái)對(duì)其進(jìn)行替換或者恢復(fù),從而保證系統(tǒng)的可信性.

5 檢驗(yàn)與分析

如果一個(gè)基于構(gòu)件的軟件系統(tǒng)中核心構(gòu)件有兩個(gè),分別為構(gòu)件A和構(gòu)件B,它們?cè)谶\(yùn)行過(guò)程中產(chǎn)生故障的概率分別為pA=0.3和pB=0.2,則當(dāng)對(duì)其進(jìn)行單個(gè)構(gòu)件的雙模冗余結(jié)構(gòu)、兩個(gè)串聯(lián)構(gòu)件的雙模冗余方式(方式一、方式二)以及三取二冗余結(jié)構(gòu)時(shí),其冗余系統(tǒng)對(duì)應(yīng)的概率如表1所示.

從表1中可以看出,在不同構(gòu)件發(fā)生故障的情況下,單個(gè)構(gòu)件的雙模冗余結(jié)構(gòu)和兩個(gè)串聯(lián)構(gòu)件的雙模冗余方式雖然不能確定系統(tǒng)中哪個(gè)構(gòu)件產(chǎn)生了故障,但是能夠提高故障概率檢測(cè)的效果,而三取二冗余結(jié)構(gòu)能夠很好地提高系統(tǒng)的可靠性,降低系統(tǒng)發(fā)生故障的概率.

表1 不同冗余模式下的概率對(duì)應(yīng)值

6 結(jié)論

可信軟件作為計(jì)算機(jī)軟件研究領(lǐng)域最具價(jià)值和最具挑戰(zhàn)性的核心課題之一,引起了國(guó)內(nèi)外政府組織、科學(xué)界和工業(yè)界的高度重視.我們構(gòu)建的軟件系統(tǒng)不夠可信的原因就是故障的存在,故障的存在說(shuō)明軟件系統(tǒng)內(nèi)部有缺陷的部件.為了降低軟件故障的發(fā)生率,同時(shí)能夠檢測(cè)出系統(tǒng)是否產(chǎn)生故障和確定哪些部件產(chǎn)生故障可以采用系統(tǒng)的容錯(cuò)的方法,而對(duì)系統(tǒng)故障進(jìn)行容錯(cuò)要依靠冗余.為此,本文在基于構(gòu)件的可信軟件結(jié)構(gòu)設(shè)計(jì)中加入冗余機(jī)制,也就是對(duì)可能出現(xiàn)故障的關(guān)鍵和核心構(gòu)件進(jìn)行冗余處理,使得當(dāng)冗余中的其中一些構(gòu)件發(fā)生失效時(shí),其他的冗余部件可以繼續(xù)提供服務(wù),從而保證軟件系統(tǒng)運(yùn)行的可信性.

1 Laprie JC.Dependability:Basic Concepts and Terminology.Vienna:Springe-Verlag,1991.

2 NSTC. Research challenges in high confidence systems.Proceedings of the Committee on Computing,Information,and Communications Workshop.1997.

3 陳火旺,王戟,董威.高可信軟件工程技術(shù).電子學(xué)報(bào),2003,31(A12):1933–1938.

4 Saha GK. Software based fault tolerance:A survey.Ubiquity,2006,7(25):1–15.

5 Reis GA,Chang J,Vachharajani N,et al. Softwarecontrolled fault tolerance.ACM Transactions on Architecture and Code Optimization,2005,2(4):366–396.[doi:10.1145/1113841]

6 Reis GA,Chang J,Vachharajani N,et al.SWIFT:Software implemented fault tolerance.Proceedings of the International Symposium on Code Generation and Optimization.Washington DC,USA.2005.243–254.

7 Xie ZP,Sun HY,Saluja K.A survey of software fault tolerance techniques.http://www.pld.ttu.ee/IAF0030/Paper_4.pdf.[2011-05-22].

8 Sathre J,Zambreno J.Automated software attack recovery using rollback and huddle.Design Automation for Embedded Systems,2008,12(3):243 –260.[doi:10.1007/s10617-008-9020-4]

9 何加浪,張琨,孟錦,等.可進(jìn)化模塊冗余軟件混合容錯(cuò)模型.南京理工大學(xué)學(xué)報(bào),2012,36(2):272–277,284.

10 張立眾.一種雙總線雙控制器軟件冗余系統(tǒng)的設(shè)計(jì).陜西理工學(xué)院學(xué)報(bào) (自然科學(xué)版),2014,30(3):41–46.

11 黃濤,陳祥獻(xiàn),黃海.基于三取二冗余結(jié)構(gòu)的安全計(jì)算機(jī)系統(tǒng).計(jì)算機(jī)工程,2011,37(18):254–257.[doi:10.3969/j.issn.1000-3428.2011.18.085]

12 楊芙清.軟件工程技術(shù)發(fā)展思索.軟件學(xué)報(bào),2005,16(1):1–7.

13 Atkinson C,Bunse C,Gross HG,et al.Component-based Software Development for Embedded Systems. Berlin Heidelberg:Springer-Verlag,2005.