基于網絡模型的軟／硬件可靠性分析

摘要：提出了一種以軟件環境中硬件可靠性分析的可靠性計算方法，從而使系統的可靠性計算更精確。最后給出了提高系統可靠性的策略與方法。

關鍵詞：網絡模型； 硬件可靠性； 軟件可靠性

中圖分類號：TP311．5文獻標志碼：A

文章編號：1001－3695(2007)07－0028－04

0引言

在結構化編程思想的指導下，程序是由模塊組成的。各個模塊之間通過參數的傳遞進行交互，協作完成任務。在面向對象的編程思想和面向構件(Component)的編程思想日益盛行的今天，大型程序一般都是由很多嚴格定義接口的構件組成。只要知道各個構件的接口標準就能將這些構件組裝起來，使一個構件的輸入結構對應另一個構件的輸出結構(這是受硬件接口標準化的影響)。無論是模塊還是構件，它們之間都通過信息的流動達到交互與合作的目的。

圖1給出了兩個模塊之間交互的模型。這里沒有具體考慮它們之間是怎樣交互(傳遞參數)的。該部分工作是由硬件來完成的。其實所有可執行的程序或代碼經過編譯后是存儲在存儲器中的指令。對于馮諾伊曼體系結構的計算機，其指令與數據是存儲在同一個存儲區中的；而對于哈佛體系結構的計算機則有兩個存儲區(程序存儲區和數據存儲區)，程序與數據分開存儲。仔細分析，模塊或構件之間的數據交互是通過函數調用或程序調用來實現的。當一個模塊(函數)調用另一個模塊(函數)時，它把自己的所有參數壓入堆棧，然后把被調用的程序或模塊的參數放入寄存器中，這樣就實現了參數傳遞。

軟件的可靠性與硬件的可靠性是密不可分的。如果硬件的可靠性為零，各個軟件模塊根本無法溝通。目前的可靠性計算方式是分別計算硬件與軟件的可靠性，而沒有將軟件的可靠性與硬件的可靠性進行系統考慮。本文的創新之處在于將硬件的可靠性融入構件或模塊的可靠性計算中，然后得出系統的總體可靠性。最后結合連通圖的知識提出了增強系統可靠性的方法。

1網絡模型

把硬件和軟件結合起來考慮，采用這樣的模型：節點不單單是程序本身(語句或指令的集合)，而是包含它上面所執行的控制(Control)、操作(Operation)、存儲(Load－Store)和輸入/輸出(I/O)(因為不同的程序代碼集合它上面所執行的控制、操作、存儲和輸入/輸出是不一樣的，引起牽涉到的可靠性指標不一樣)。形成的節點模型是：節點(程序和數據、控制、執行、存儲、輸入/輸出)，如圖2所示。其中的數據牽涉到函數調用機制的實現。很多網絡攻擊正是利用緩沖區溢出來達到對計算機攻擊與控制的目的。因此，數據對于可靠性具有很大的影響。控制與程序中的指令條數有關，而執行則與程序中的指令種類有關。譬如對于偏于計算的程序，加、減、乘、除等運算應該占大多數；而偏于自動化控制的程序則會頻繁地調用邏輯指令。它們的可靠性顯然與不同的硬件部件有關。一個使用三條乘法指令和一條加法指令的程序與一個使用兩條乘法指令和兩條加法指令的程序的可靠性也會有所不同。

由此，對于包含軟件與硬件的系統可靠性分析可以建立在由上面的節點構成的一個網絡結構的可靠性計算上。實際上一個系統的可靠度就是由節點的可靠度和節點之間的連接關系完全決定的。

定義1一個計算機系統的可靠度（Computer System Reliability，CSR）可以定義成其中各個抽象節點的可靠度與連接關系G的函數，即CSR=f(N，G)。

2可靠性分析

2．1節點的可靠性分析

對于軟件的可靠性分析，有很多基于概率統計的模型可以被使用。它們在軟件的可靠性預測與可靠性分配方面發揮了很大作用。但是本文認為那是在沒有辦法或不能分析軟件可靠性本質情況下的一種選擇。舉個簡單的例子：我們很難了解一個人的內心世界，于是對于一個人的了解在很大程度上基于對這個人日常行為的統計，但是概率與統計的東西是建立在無窮（無窮遠、無窮大或無窮小）概念之上的，所以這樣很難精確地描述系統的本質。對于兩個實現相同功能的軟件，軟件A在開始運行的5 h內發生了五次錯誤或異常，在以后的5 h內發生了一次錯誤；軟件B在開始運行的5 h內發生了三次錯誤，在以后的5 h內發生了四次錯誤。不能根據一開始的5 h就斷定軟件B比A可靠；當然也不能根據前10 h的數據，斷定軟件A比B可靠。

可靠性分析不可能脫離概率的概念，因為可靠性本身屬于概率的范疇。例如有如下代碼：

顯然，標記為A的語句序列與標記為B的語句序列的動態可靠性是不同的，分別記為RA、RB。由分析可知，a==0的概率為p，a!=0的概率為q。那么整個分支語句的可靠度可以這樣計算：R=p×RA+q×RB。其中q=1-p。不過注意一點，這里分析的是一般的分支語句，與那種為了提高可靠性而加入的冗余語句是不同的。譬如這里有幾個可以同時實現FFT算法的模塊，可以根據其結果來判斷執行是否成功。如果不成功則執行下一個實現相同功能的模塊。可能的語句序列為

這叫做旁聯模型，其可靠度的計算可以參閱非工作儲備模型（旁聯模型的可靠性計算公式）。它不是籠統地通過執行這段代碼多次獲得統計上的概率，而是通過分析代碼的特性得到的分支概率p和q，然后通過計算得到更本質上的概率。

如果大部分情況下，a≠0，那么很難通過統計的方法發現這個程序或模塊的設計錯誤。這里a==0的概率與i=0的情況屬于軟件靜態可靠性分析的范疇（當然也是軟件動態可靠性分析的范疇）；其他語句的可靠性分析則不是靜態可靠性分析的范疇，而是動態可靠性分析的范疇。

(2)程序代碼的動態可靠性分析。一條語句經過編譯后可能是一條或幾條可執行的指令。當程序要執行時它被從硬盤或其他存儲設備通過I/O系統放在內存中的某個空間；然后控制器將它從內存中讀到寄存器中譯碼，送到運算器（ALU）中執行；而后，程序計數器中的地址被用來作為下一條指令的地址。每一步經過的硬件組成部分都需要考慮它的可靠性，如圖5所示。

這是從程序代碼的角度來考慮的。如果從一個模塊的角度來考慮，由于一個模塊中的語句經過編譯后的指令與其他程序比較起來可能會用到不同的部件。對于數值計算的程序，它對算術運算部件的要求就應該高一些。因為其中的指令要用到算術運算部件。如果該部件的可靠性不高，則該程序的可靠性也不會很高，而其他部件的可靠性則可能對于該模塊或程序的可靠性影響不大。數字信號處理中有很多乘法運算（如FFT算法），因此對于乘法部件的要求相對于加法來說要高一些。

對于一臺主要進行路由選擇的計算機而言，它的光驅對于系統的可靠性影響不大，甚至可以沒有光驅。但是對于一臺必須通過光盤驅動設備進行輸入/輸出的設備，如果沒有光驅，則它的可靠性近乎為零。因此如果考察一個系統的可靠性，就不能把軟件在別的系統上運行的可靠度照搬過來。軟件的可靠性是不確定的，它必須與它所執行的硬件環境結合起來。這里完全可以設計一種可靠性分析的程序(可以在編譯器中實現，因為編譯器是將軟件或程序轉換成依賴于硬件平臺的指令代碼或匯編程序)。首先它分析設計中的邏輯不可靠性（也許需要借助于人工分析的幫助，如分支跳轉的概率）；然后讀取編譯后代碼統計所需要的控制、操作、存儲以及輸入/輸出的情況；最后根據公式

2．2系統的可靠性計算

經過上面的分析，可以認為一個計算機系統是一個由多個計算元組成的系統。每個計算元不是單獨的程序、進程或線程，也不是物理部件的某個組成部分。它是軟體與硬體結合起來的一個可執行體。

文獻[3]給出了關于單輸入節點、單輸出節點并且節點之間連線的可靠度為1的網絡結構的可靠度計算方法。但是對于一個實際系統，它很可能是個多輸入/多輸出的系統，并且通過上面的分析知道節點之間連線的可靠度也不可能是1（即考慮的連接是Imperfect Link）[6]。

一個系統輸入/輸出節點越多，則它的性能可能越高，但是它的可靠性可能會降低。因為這些輸入/輸出之間可以看成是一種串聯關系。

由于函數的調用與參數的傳遞是單向的，構建的圖是有向圖。有向圖知識是計算可靠度的理論基礎。并且由于不會出現循環調用(如果出現循環調用則進行展開)，構造的有向圖中不會出現環。

3提高可靠性的策略

如果不考慮所建立的模型的方向性，即把原來的有向圖看成一個無向圖，則可以考慮其連通性問題。

在無向圖G中，如果從頂點v到頂點v′有路徑，則稱v和v′是連通的。如果對于圖中任意兩個頂點vi、vj∈V，vi和vj都是連通的，則稱G是連通圖。如果把無向連通圖G中某節點a以及與a相關聯的所有邊刪去，得到兩個或兩個以上的非空分圖，那么節點a就稱為G的關節點。以圖7為例，如果刪除節點2、3、5中的任何一個，則本來連通的圖不再連通。所以，節點2、3、5都是關節點。如果無向連通圖G根本不包含關節點，則稱G為雙連通圖。

如果關節點出現故障則整個系統無法繼續工作。本文的方式是盡量提高關節點的可靠度或通過增加（改變）節點間的連接方式來消除關節點。增加（或改變）節點間的連接方式反映在圖論中就是增加一些邊，以使整個網絡成為雙連通圖。由于改變節點間的聯結方式需要修改系統的軟件間的調用關系（建立冗余調用關系）。因此要求使要增加的冗余調用關系達到最小。

該算法把一個含有關節點的連通圖G變成一個雙連通圖。基本思想是每一個關節點將連通圖分成n個連通圖，那么這幾個連通圖之間必須有邊進行連接，只需n-1條就可以；也就是從每個連通圖中選擇一個節點進行連接。但是當分割多個關節點的時候，需要連通的節點之間可能有交，這樣就可以減少邊的條數。可以證明這樣取的邊是充分必要的，即是最少的。

這個圖可以不用輸出連通分量，但是必須找出所有的關節點。當割開關節點的時候可以通過將那個節點所在的行與列置成無窮大。采用深度優先或者寬度優先等可以得到分割后的連同分量。

（1）得到關節點。

（2）分割關節點。依次求包含。

下面給出具體的算法。(文獻[5]給出了完成這個任務的算法，但不能保證需要的邊是最少的)。

輸入：圖G的鄰接矩陣存儲

輸出：需要節點的節點對

begin:

調用ART函數得到關節點，存入關節點集合crux；//ART函數可以參閱文獻[5]

建立一個臨時的數組(m*n)用來存儲圖C=G;

count用來記錄刪除關節點后升成了幾個連通圖

first用來判斷是不是第一次刪除，初始值為零；

temp1用來記錄上次的count，temp2用于記錄歸并的集合數

m*n矩陣集合X，Y，Z清零，X用來存放上次的求交的結果，Y紀錄當次分割的結果，Z用來暫時存放X與Y取交的結果；

for(每個關節點)do

temp2=0;

temp++;//用于記錄是否是第一次

將G的值付給C(C=G);

將該關節點所在行與列全部置零；

在每次調用前先把Y清零；

//調用深度優先算法，輸出各個連通分量，存入集合中

count=bft(k)，并且將各個連同分支放入Y中;//其中的count用來判斷分成了幾個集合

//在這里取包含關系

if(temp==1){

for(i=1;i<=count;i++)

X[i]=Y{i};

temp1=count;

}

else

{

for(X中的每個集合i，Y中的每個集合j)

如果X[i]=Y[j]，則什么也不做

如果X[i]包含在Y[j]中

{temp2++;Z[temp2]=X[i];}

如果Y[j]包含在X[i]中

{temp2++;Z[temp2]=Y[j];}

空X;

X=Z;

清空Z;

temp1=temp2;

}

enddo

此時X中有temp1個集合，從每個集合中隨便取一個節點進行連接就是所求

end

參考文獻：

[1]郭永基.可靠性工程原理[M].北京:清華大學出版社，2002:67－74.

[2]何國偉，王偉.軟件可靠性[M].北京:國防工業出版社，2002:100－109.

[3]陸延孝，鄭鵬洲.可靠性設計與分析[M].北京:國防工業出版社，2002:1－200.

[4]Michael R LYU.軟件可靠性工程手冊[K].劉喜成，等譯.北京:電子工業出版社，1997.

[5]余祥宣，崔國化，鄒海明.計算機算法基礎[M].武漢:華中理工大學出版社，1998:10－50.

[6]CHENG Dengyi， CHANG Mingsang， SHENG Mingcheng， et al. Time－Constrained distributed program reliability analysis[J]. Journal of Information Science and Engineering， 1998，14(4):891－911.

[7]DICK HAMLET， DAVE MASON， DENISE WOIT. Theory of software reliability based on components: proc.of the 3rd Int’l， Workshop on Component－Based Software Engineering[C]. Toronto: IEEE Computer Society， 2001:361－370.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”