計算機容錯期末復習

1、實現(xiàn)可信計算，歸結(jié)為兩種方法：避錯、容錯，前者效果有一定限制，難以滿足高可信性系統(tǒng)需求。后者依靠冗余換取可靠性，主要有硬件冗余、軟件冗余、信息冗余、時間冗余這些方法要合理利用才能達到高可靠性?？煽慷龋涸O(shè)在時刻t0系統(tǒng)正常運行，則系統(tǒng)在整個時間區(qū)間 t0 , t 內(nèi)正常運行的條件概率，稱為系統(tǒng)在時刻 t 的，記為R(t)。不可靠度（失效概率）：Q(t) = 1-R(t)系統(tǒng)在時刻t的可用度：指系統(tǒng)在該時刻正確執(zhí)行其功能的概率，記為A(t)，是瞬時可用度。系統(tǒng)處于穩(wěn)定狀態(tài)時，其可用度不再隨時間變化，稱為系統(tǒng)的穩(wěn)態(tài)可用度，記為Ass。系統(tǒng)的可信性可以用下列參數(shù)指標進行表征：可靠度可用度、安全度、可維

2、度、保能度、可測度。Ass =T0T0 +TfT0：正常運行時間，系統(tǒng)完成功能的時間。：正常運行時間，系統(tǒng)完成功能的時間。Tf：故障時間，故障修理時間之和。：故障時間，故障修理時間之和。設(shè)在時刻t0系統(tǒng)正常運行，則系統(tǒng)在時刻t的安全度S(t) 指系統(tǒng)在t0, t內(nèi)正常運行的條件概率加上系統(tǒng)在時刻t處于失效安全狀態(tài)的條件概率。S(t) = R(t) +FS(t)1、為什么說可靠度高的系統(tǒng)其安全度必然高，但安全度高的系統(tǒng)其可靠度不一定高。答：安全度是兩個概率之和，其中第一個條件概率就是可靠度。因此，一個可靠度高的系統(tǒng)，其安全度也必然高，反之，一個安全度高的系統(tǒng)其可靠度未必高。2、可靠度高的系統(tǒng)是否

3、可用度一定高？（Y）可用度高的系統(tǒng)是否可靠度一定高（N），為什么？答：可用度的概念：系統(tǒng)在時刻t的可用度是指系統(tǒng)在該時刻正確執(zhí)行其功能的概率，記為a（t）。注意到可用度只考慮時刻t系統(tǒng)正確執(zhí)行功能的概率，并不關(guān)心時刻t以前系統(tǒng)是否發(fā)生過時效。而可靠度則要考慮在整個時間區(qū)間【t0，t】內(nèi)系統(tǒng)正常運行的概率。3、系統(tǒng)的可維度是如何影響系統(tǒng)的可用度的？A（t）=t0/t0+tf，可維度影響tf故障：是指系統(tǒng)的硬件中發(fā)生的物理缺陷、設(shè)計制造的不完善或軟件中隱含的錯誤。差錯：系統(tǒng)中由于故障而造成的信息或狀態(tài)的不正確。（信息方面）故障是差錯的原因，差錯是故障的結(jié)果。失效是系統(tǒng)未能正確提供預先指定的服務(wù)。（

4、功能方面）差錯是失效的原因，失效是差錯的結(jié)果。門級邏輯網(wǎng)絡(luò)中每個門的每根輸入輸出線均可能發(fā)生兩種故障，即該線固定為1（記為s-a-1）或該線固定為0（記為s-a-0）;總的故障數(shù)可達3n1。F.X1XSXnZF.X1XSXnZ&若物理故障對電路或系統(tǒng)產(chǎn)生的影響是使其輸出信息中最多只有1位產(chǎn)生差錯，則此種差錯稱為單位差錯模型。若物理故障對電路或系統(tǒng)產(chǎn)生的影響是使其輸出信息中只產(chǎn)生0錯成1的差錯，或只產(chǎn)生1錯成0的差錯，而不會同時產(chǎn)生0錯成1及1錯成0的差錯，則此種差錯稱為單向差錯模型。故障故障原因原因故障故障差錯差錯安全安全失效失效危險危險失效失效避錯避錯技術(shù)技術(shù)故障故障掩蔽掩蔽技術(shù)技術(shù)

5、系統(tǒng)系統(tǒng)重組重組技術(shù)技術(shù)失效失效安全安全技術(shù)技術(shù)冗余技術(shù)冗余技術(shù)硬件冗余硬件冗余軟件冗余軟件冗余信息冗余信息冗余時間冗余時間冗余防衛(wèi)故障的原理故障表：將電路無故障時的真值表與有故障時的真值表列在一個表中，該表稱為該電路的。測試方法：將二者結(jié)果按位異或，結(jié)果為1的位對應的輸入矢量，為該故障的測試。根據(jù)門電路根據(jù)門電路的有無真值的有無真值表可以看出，表可以看出，兩者輸出不兩者輸出不相等的就是相等的就是故障，對應故障，對應的輸入稱為的輸入稱為一個測試一個測試對電路中所有可能的輸入X，都有F(X) F(X) ，則稱故障和是等價故障。反映在故障表上即為兩列全部相等。上表F為無故障輸出，雖然F(X)最后一

6、列與之全等，但并非等價故障，而是因為電路有冗余，是不可測故障。對1個AND門， 任1輸入端s-a-0故障 輸出端s-a-0故障。對1個NAND門，任1輸入端s-a-0故障 輸出端s-a-1故障。對1個OR門， 任1輸入端s-a-1故障 輸出端s-a-1故障。對1個NOR門， 任1輸入端s-a-1故障 輸出端s-a-0故障。對1個反向器，輸入端s-a-1故障 輸出端s-a-0故障。 輸入端s-a-0故障 輸出端的s-a-1故障。電路最小完全測試集指：能測試該電路中所有故障且測試數(shù)最小的測試集。兩個故障有兩個測試集，測試集大（包含另一個）的那個故障強于另一個故障，在求最小完全測試時可以被刪掉。兩個

7、測試分別可以測試兩個故障集，故障集大的（包含另一個）那個測試強于另一個測試，弱的測試可刪掉。用故障表法求電路的最小完全測試集，步驟：列出電路的故障表，對等價故障類只留1個故障響應。列出電路的故障檢測表。根據(jù)故障強弱和測試強弱，在故障檢測表中求最小覆蓋。在故障表中每列對應于一個故障的響應，而在故障檢測表中，每列對應于一個故障，每行對應于一個測試。即故障檢測表i行j列=1，說明第i個測試可以檢測第j個錯誤。故障檢測表可由故障表中故障列和正常列異或得到。故障精簡定理,定理1：在無扇出的組合電路中，檢測電路中所有原始輸入線的單邏輯固定型故障的任一測試集，將檢測電路中的所有單邏輯固定型故障。定理2：在有

8、扇出的組合電路中，檢測所有原始輸入和各扇出支路上單邏輯固定型故障的測試集，必將檢測電路中的所有單個邏輯固定型故障。 例例35 用通路敏化法求下圖電路用通路敏化法求下圖電路a s-a-1故障的一故障的一個測試個測試解：故障激活：解：故障激活：a = 0 ;選擇通道選擇通道 aG5F1正向驅(qū)趕正向驅(qū)趕: G2 = 1;反向跟蹤反向跟蹤: a = 0 A=1, B=1, C=1;G2=1 D=0, A=0, 發(fā)生沖突發(fā)生沖突重選通道重選通道aG6F2正向驅(qū)趕正向驅(qū)趕: G4 =1;反向跟蹤：反向跟蹤：a=0 A=1, B=1, C=1;G4=1 G3 = 0, E=0;G3=0 C=1, 相容；相容

9、；故得測試：故得測試：T = (1110)11&DABCE13aG2G1G3G5G6G4F1F2【定義定義1】線線s的的組合組合0可控度可控度，記為，記為cc0(s)，為了使線，為了使線s取值為取值為0，電路中必須電路中必須置值置值的最小組合線數(shù)；的最小組合線數(shù)；【定義定義2】線線s的的組合組合1可控度可控度，記為記為cc1(s)，為了使線，為了使線s取值為取值為1，電路中必須，電路中必須置值置值的最小組合線的最小組合線數(shù)；數(shù)；【定義定義3】線線s的組合可觀測度，記為的組合可觀測度，記為co(s)，為了使線，為了使線s的邏的邏輯值傳遞到電路的一個原始輸出所必須置值的最小組合線數(shù)；輯值傳

10、遞到電路的一個原始輸出所必須置值的最小組合線數(shù)；可測度計算：對于電路的任一原始輸入線可測度計算：對于電路的任一原始輸入線I，有：，有：cc0(I) = 1 cc1(I) = 1 對于電路的任一原始輸出線對于電路的任一原始輸出線U，有：，有：co(U) = 0對與門，有：對與門，有：cc0(output) = MINcc0(input)+1cc1(output) = cc1(input)+1co(input)= co(output)+cc1(input)+1對或門，有：對或門，有： cc0(output) = cc0(input)+1cc1(output) = MINcc1(input)+1co

11、(input) = co(output)+ cc0(input)+1對非門，有：對非門，有： cc0(output) = cc1(input)+1cc1(output) = cc0(input) +1co(input) = co(output)+ 11234cc0(1) = cc0(2) = cc0(3) = cc0(4) cc1(1) = cc1(2) = cc1(3) = cc1(4) co(1) = min（co(2) , co(3) , co(4)）11&1112354109876111213141516171819n1 2 3 4 5 6 7 8 9 10 11 12 13

12、14 15 16 17 18 19cc0(n)1 1 1 1 1 1 1 1 1 1 1 1 2 3 3 2 7 3 2cc1(n)1 1 1 1 1 1 1 1 1 1 1 1 3 2 2 5 3 2 10co (n)2 2 9 9 9 13 13 13 2 9 13 13 7 11 11 5 7 0 0硬件硬件冗余冗余采用技術(shù)采用技術(shù)應用特點應用特點成成本本被動被動冗余冗余故障掩蔽故障掩蔽關(guān)鍵計算（安全關(guān)鍵計算（安全關(guān)鍵）；關(guān)鍵）；較較高高主動主動冗余冗余故障檢測、故障檢測、定位和恢復定位和恢復（重組）（重組）長生命期應用或長生命期應用或高可用度應用高可用度應用最最低低混合混合冗余冗余故障

13、掩蔽和故障掩蔽和重組重組關(guān)鍵計算；要得關(guān)鍵計算；要得到最高的可靠度到最高的可靠度時，用時，用最最高高硬件冗余三種基本形式：被動冗余、主動冗余、混合冗余。被動硬件冗余又稱為靜態(tài)硬件冗余，指冗余結(jié)構(gòu)不隨故障情況變化的冗余形式。被動冗余的基本結(jié)構(gòu)是N模冗余。設(shè)計中需要解決的關(guān)鍵問題有：初始化和時鐘同步及校正器設(shè)計：為了保證校正器的高可靠性，應盡可能使表決器簡單可靠。NMR的主要問題實際上就是校正器的設(shè)計問題。用多數(shù)表決邏輯來實現(xiàn)校正器是最直接和最常用見的一種方法。多數(shù)表決容易用組合邏輯來實現(xiàn)。模塊1模塊2模塊N輸入差錯輸出輸出校正器只要只要故障模塊數(shù)目故障模塊數(shù)目 ( N1) /2，則故障將，則故障

14、將被掩蔽。被掩蔽。模塊1模塊2模塊3表決器輸入1輸入2輸入3輸出三模冗余TMR 三取二，主要問題：表決器的故障將造成系統(tǒng)差錯。即對表決器可靠性要求較高，可采用三重表決表決器輸入1輸入2輸入3多級三重表決模塊1模塊2模塊3表決器表決器表決器模塊1模塊2模塊3表決器表決器輸出1輸出2輸出3表決器輸入1輸入2輸入3模塊1模塊2模塊3表決器表決器模塊1模塊2模塊3輸出1輸出2輸出3模塊1模塊2模塊3總線內(nèi)部總線命令關(guān)鍵部分采集/驅(qū)動任務(wù)處理電機處理器1處理器2處理器3反饋1輸入1反饋2輸入2反饋3輸入3反饋信號1 2 3圖 磁通和技術(shù)用1個TMR系統(tǒng)控制1個小電機轉(zhuǎn)子電流。無故障時，各個初級線圈各提供

15、1/3輸出電流，若1個模塊故障無輸出，則使電機轉(zhuǎn)子電流減小1/3，該變化通過反饋會使無故障的2個模塊提供較大的電流以補償故障的影響。若故障模塊輸出過大電流，也可通過反饋使無故障模塊減小電流輸出以補償故障影響。硬件表決和軟件表決的優(yōu)缺點：硬件表決速度快，所需附加硬件多，技術(shù)要求高。軟件表決與硬件表決正好相反，比較靈活。 軟件實現(xiàn)表決：傳感器信號經(jīng)采樣后存放在雙口RAM中，由前處理機取出表決，并將表決結(jié)果置于后雙口RAM，由后處理器計算處理，產(chǎn)生輸出。采樣器采用軟件表決的TMR系統(tǒng)雙口RAM處理機雙口RAM處理機采樣器雙口RAM處理機雙口RAM處理機采樣器雙口RAM處理機雙口RAM處理機主動硬件冗

16、余又稱動態(tài)硬件冗余，是通過故障檢測、故障定位及系統(tǒng)恢復來達到容錯的一種技術(shù)。它不防止故障產(chǎn)生差錯，但防止差錯產(chǎn)生失效。一般適用于：允許發(fā)生暫時的錯誤結(jié)果，只要系統(tǒng)能在規(guī)定時間內(nèi)進行重組并恢復正常運行輸入模塊1模塊1比較器一致/不一致輸出圖49 雙機比較系統(tǒng)雙機比較：只提供故障檢測能力，不提供容錯能力。但配以故障定位技術(shù)，可以做到容錯。備用替換，一個模塊為主用模塊產(chǎn)生系統(tǒng)輸出，其它模塊備用。備件可分為熱備和冷備。對熱備，中斷正常運行的時間短；對冷備，中斷時間相對長，功耗低輸入模塊1差錯檢測輸出備用替換系統(tǒng)N至1開關(guān)模塊n差錯檢測AB切換電路心跳線雙機熱備：A、B內(nèi)部有自檢測功能。主機檢測到故障后

17、自動切換到備機運行；A、B通過心跳線保持同步；輸入模塊1模塊1比較器一致/不一致輸出N至1開關(guān)輸出模塊1模塊1比較器一致/不一致輸出將備用替換和雙機比較結(jié)合起來就成為成組備用系統(tǒng)，典型應用是下圖的二乘二取二將主動冗余與被動冗余結(jié)合起來就是混合冗余?；旌嫌布哂喑杀据^高，一般用于需要極高可靠度的，常見的有：帶備件的N模冗余，自清除冗余，篩選模塊冗余，三模雙機系統(tǒng)。模塊1模塊2模塊N系統(tǒng)輸入系統(tǒng)輸出圖 帶備件的N模冗余開關(guān)備件1備件N不一致檢測器表決器 不一致檢測器將表決器輸出與N個模塊的輸出進行比較，若發(fā)現(xiàn)模塊故障，由開關(guān)網(wǎng)絡(luò)將故障模塊從NMR核心中清除，并以一個備件代之。當NMR中模塊發(fā)生故障

18、時，通過備件替換可恢復表決機構(gòu)。模塊1模塊2模塊N系統(tǒng)輸入系統(tǒng)輸出圖 自清除冗余表決器 開關(guān) 開關(guān) 開關(guān)各模塊將表決器結(jié)果與自身輸出通過開關(guān)比較，若不一致則該模塊被清除，系統(tǒng)按照（N-1）NR結(jié)構(gòu)運行，依此類推。維修方便，可在不中斷系統(tǒng)正常運行情況下維修。自清除冗余中的開關(guān)采用異或門、JK觸發(fā)器和與門構(gòu)成。模塊J KQ Q系統(tǒng)輸入系統(tǒng)輸出閹表決器 不一致檢測 自清除控制 初始化=1&來自另一模塊Z =1，若WiXi T0，若WiXi TTX1X2XnW1W2WnZ圖 用作表決器的閹值門自清除系統(tǒng)中的開關(guān)結(jié)構(gòu)示意模塊1模塊2模塊N系統(tǒng)輸入系統(tǒng)輸出 篩選模塊冗余收集器比較器檢測器 比較器將N個模塊一對一進行比較（一致時輸出1，不一致時輸出0，共C2N個輸出）；檢測器根據(jù)比較器輸出確定故障模塊（對每個模塊產(chǎn)生1個指示信號：信號為0表示模塊正常，1時故障）；收集器根據(jù)每個模塊的輸出及檢測器的指示產(chǎn)生系統(tǒng)輸出。被指示為故障的模塊不允許影響系統(tǒng)的輸出。篩選模塊冗余一個碼的碼距與它的檢錯及糾錯能力密切相關(guān)：要檢測碼中任意e位及e位以下差錯，碼距d必