一種基于時間容錯的同步機制分析

楊芳萍+趙海東

摘 要：表決邏輯結構在多通道余度系統的研究和應用中起著核心作用，針對該問題，設計了一個具有動態同步表決控制的邏輯結構，該邏輯結構用來控制表決時間并監測表決數據。理論分析和實驗表明，該表決算法在最大限度保證表決正確性的前提下，其表決控制邏輯結構還可以大幅度地提高多通道系統的可靠性。

關鍵詞：多通道；余度系統；表決；控制算法；可靠性分析

中圖法分類號：TP393 文獻標識碼：A 文章編號：2095-1302（2014）03-0076-03

0 引 言

多通道交叉余度模型雖然通過硬件冗余技術提高了系統的可靠性，但協調工作的基礎性前提是各個單元之間的同步。同步是整個余度管理系統的核心，它保證了各冗余單元間保持步調一致地工作，是表決、故障屏蔽、故障隔離和重構的基礎。當前關于同步的研究在分布計算、傳感器網絡以及媒體控制等領域各自展開。其中任務同步機制內容包括：共享內存、數據簡單的共享、信號量、基本的互斥和同步、消息隊列和管道，同一CPU內多任務間消息傳遞；Sockets和遠程調用，任務間透明的網絡通信等。

1 通道模型

一個實際的余度系統包含多個交叉傳輸數據的連接。其構成如圖1所示。

圖1 多交叉通道模型圖

圖1中，S為輸入任務序列，M為對應通道上的處理模塊，l為經過多通道表決后的處理輸出。多通道交叉余度模型在串聯通道的基礎上，將處理單元按階段進行并聯，然后再由并聯系統構成串聯結構，最終構成了負載的并/串結構。在每個并聯輸出時，設立表決面，進一步在處理上隔離了因為通道單元的故障而導致的錯誤向串聯系統的下一級傳遞。

在并聯的每個階段，設φ（zi）和zi=（zi，1，zi，2，…，zi，m）分別表示系統和其m個階段單元的狀態，它們是二值變量，當，φ（zi）=1時表示該階段單元正常工作，有正確的輸出，φ（zi）=0時表示階段單元故障。在該階段，多個單元之間構成k/n系統，存在φ（zi）=max{zi，1，zi，2，…，zi，m}，如有zi，1，zi，2，…，zi，m≥k，則φ（zi）=1，否則，φ（zi）=0。而在串聯的n個階段之間，構成串聯系統，則有1/n屬性，其狀態φ（z）=min{φ（z1），φ（z2），…，φ（zn）}。

2 表決結構

具有動態同步的表決控制邏輯結構如圖2所示。

圖2 動態同步表決控制邏輯

動態同步表決控制邏輯中，數據檢測從

開始，周期性地從每個處理單元的數據寄存器Ri，j中讀取數據，與特征碼比較，來判定數據是否準備好。在判定中，表決控制邏輯不讀取對應模塊中因永久故障而被隔離的單元，對所有正常工作的單元進行讀取。當數據全部就緒時，就進行表決，為下一模塊輸入表決數據。表決時間表維護一個本邏輯應當進行表決的最后時間期限，當時間期限到而數據檢測仍未全部就緒，則按照當前采集到的數據進行表決。而對未就緒的單元可能發生的故障或產生的失步，由檢測系統進行判定處理。表決邏輯執行表決策略，為下一級模塊輸入數據。

3 表決控制算法

當檢測過程被啟動后，檢測邏輯可采用輪詢端口或中斷等方式（按照硬件的設計和實現而定），獲取每個非永久故障單元數據就緒信息。當所有數據就緒，則進入表決，并將結果輸出到下一個模塊的輸入端口。有兩個因素導致表決的發生：一是數據就緒；二是表決時間到。如果表決時間到達最后期限，而對應模塊中仍有單元數據未就緒，則使用就緒數據進行表決。其未就緒單元進行檢測判定，按照故障判定規則處理。表決的最后期限按照后面可能的冗余時間為。

設模塊所包含的m個單元的端口依次為port1，port2，…，portm，建立一個長度為m的數組fixed[m]，記錄對應單元是否為永久故障，當對應位為0表示良好，為1表示持久故障；數組Data_ready[m] 存放讀取數據，并作為表決的參數；Data_readed[m]為已經讀取的標志，用num_ready對就緒數據個數進行計數；num_right表示當前完好的單元個數。當前時間用currently_clock表示，Di是按照靜態分配規劃的表決時間，deadline為最后表決時間期限，Sign_empty 為空標志特征碼。

Test_and_vote； //測試、表決算法過程

{ num_right=0

num_ready=0；

deadline=；

For i=1 to m do {

num_right= num_right+ fixed[i]；

num_right=m- num_right；

Data_readed[i]=0 } //當前良好的單元數

For i=1 to m do {

If （fixed[i]=0 and Data_readed[i]=0） then Data_ready[i]：=input（porti）；

If Data_ready[i]≠Sign_empty then { //數據就緒

num_ready= num_ready+1；

Data_readed[i]=1 //設置已讀取標志

}

If num_ready= num_right then {

For j=1 to m do {

output（portj）：= Sign_empty； //設置特征碼

Data_readed[i]=0 //恢復讀取標志為未讀取

break； //數據全部就緒

}

if currently_clock≥deadline then { //最后表決期限到

For j=1 to m do {output（portj）：= Sign_empty；

Data_readed[i]=0 //恢復讀取標志為未讀取

break；

}

}

Call voting（Data_ready） //啟動表決

}

4 可靠性分析

當m個表決邏輯在時刻t的可靠度依次為Ri， d （t），i=1，2，…，m時，并聯表決結構的可靠度為

結合表決可靠度Rb（t），級聯表決系統的可靠度R（t）為：

當級聯表決邏輯置入m×n多通道交叉余度系統中，系統變成m×2n的多通道交叉，在不考慮數據鏈路CCDL可靠性和負載分配的前提下，系統由2n個獨立的子系統串聯而成，第i個子系統又由mi個獨立分布的邏輯單元并聯而成[11]。設Rij（t）表示第i個子系統的第j個單元在時刻t的可靠函數，i=1，2，…，2n，j=1，2，…，m，Ri（t）表示第i個子系統在時刻t的可靠函數，則有：

進而：

假設i個子系統的每個單元壽命服從Poisson分布P（λi），λi>0，則有：

m×2n多通道交叉余度系統的可靠度表達式為：

其中，t為正整數，λ為任意的實數。

當不采用級聯表決邏輯時，系統構成為m×n多通道交叉和n個表決邏輯的串聯結構，其可靠度為：

顯然，系統在一定期限內運行（≤MTTF）可靠度有明顯提高。

5 實驗驗證

基于PowerPC的開發平臺下構建了實驗環境，其分為硬件平臺、開發環境系統和軟件平臺3部分：

（1）系統硬件平臺，主要包含微處理器PowerPC8247、SDRAM、BootFlash、Flash、網絡模塊、串口、電源模塊；

（2）開發環境系統，包含GCC交叉編譯系統，連接和Glibc庫；

（3）系統軟件平臺，主要包括VxWorks和文件系統的構建。驅動程序包含CPU的初始化，串口和相關文件系統所需要的驅動。

在上述開發環境下構建了三通道狀態，設置表決面3個，表決邏輯和處理邏輯具有一致的余度。設余度系統中所有的處理和表決單元邏輯具有相同的可靠度，故障率為1/R=17.7088×10-6/h（某型號飛機對余度器件的要求），仿真中采用一個符合平均分布的故障散播函數實現故障注入，系統故障覆蓋率為0.98，余度系統要求的指令周期為20 ms，其中表決周期為2 ms，每個階段任務周期為6 ms，任務時實際執行時間為4 ms，插入的故障周期為1 ms。表決輸出采用符合一致性要求的輸入數據的算術平均值，永久故障的臨界值計數為6，仿真時間為500 h。實驗結果如表1所列。

表1 不同時間同步算法故障狀態比較（/500 h）

時間同步算法 三通道故障狀態 系統失效狀態

靜態同步算法 0.784 5E-12 0.696 3E-12

時間冗余向后遷移 0.554 1E-13 0.376 2E-13

Test_and_vote 0.981 2E-14 0.789 0E-14

從上述實驗可以看出，隨著冗余時間的利用，在靜態同步算法的基礎上，時間冗余向后遷移和Test_and_vote算法分別在故障狀態和系統失效兩個參數上都有明顯提高，即故障率降低、可靠性提高，變化幅度在10倍以上。由于靜態同步算法在時間上沒有任何容錯處理，在一個指令周期中，單個故障已經降低了系統可靠性，當出現兩個以上連續故障時，會直接導致系統的失步。而后兩種算法理論上課提供6個連續的瞬時故障，時間冗余向后遷移實際可利用故障周期為3個左右，Test_and_vote算法則進一步將可利用故障周期提高到5個左右。大大促進了系統對時間周期的可利用率，進而提高了系統的可靠性。

6 結 語

文章針對多通道余度模型中同步的可靠性問題，提出了一種基于表決邏輯控制結構的算法，該邏輯結構用來控制表決時間并監測表決數據。理論分析和實驗表明，在表決算法最大限度保證表決正確性的前提下，表決控制邏輯結構大幅提高了多通道系統的可靠性，對瞬時干擾的抵抗能力得到了提高。

參 考 文 獻

[1]張小林.小型飛行器機載計算機的余度設計技術[J].西北工業大學學報，2001，19（2）：274-278.

[2]高冰. 基于自適應模糊控制的飛機自動著陸系統[J] . 電氣傳動， 2011（8）：26-29.

[3] KANG H G， SUNG T. An analysis of safety-critical digital systems for risk-informed design [J]. Reliability Engineering and System Safety， 2002， 78（3）： 307-314.

[4] BOURAS C， GKAMAS A， KARALIOTAS A， et al. Architecture and performance evaluation for redundant multicast transmission supporting adaptive QoS [J]. Multimedia Tools and Applications， 2005， 25（1）： 85-110.

[5] KELLNER A， KOLINOWITZ. A novel approach to fault tolerant computing in space systems [C]// Proceedings of 2001 IEEE Aerospace Conference. Big Sky， MT， The USA： IEEE， 2001： 127-1131.

A synchronization mechanism analysis based on time fault tolerant

YANG Fang-ping1， ZHAO Hai-dong2

（1. College of Information Engineering， Longdong University， Qingyang 745000， China；

2. School of Continuing Education， Longdong University， Qingyang 745000， China）

Abstract： Voting logical structure plays the core role over the research and application of system in the multi channel， in order to solve this problem， a dynamic synchronous voting logic control structure is designed， which is used to control and monitor the voting time voting data. Theoretical analysis and experimental results show that voting control logic structure of the voting algorithm can greatly improve the reliability of multi – channel， while the correctness of the system is guarantee in high limited.

Keywords： multi channel； redundant system； voting； control algorithm； reliability analysis

For j=1 to m do {output（portj）：= Sign_empty；

Data_readed[i]=0 //恢復讀取標志為未讀取

break；

}

}

Call voting（Data_ready） //啟動表決

}

4 可靠性分析

當m個表決邏輯在時刻t的可靠度依次為Ri， d （t），i=1，2，…，m時，并聯表決結構的可靠度為

結合表決可靠度Rb（t），級聯表決系統的可靠度R（t）為：

當級聯表決邏輯置入m×n多通道交叉余度系統中，系統變成m×2n的多通道交叉，在不考慮數據鏈路CCDL可靠性和負載分配的前提下，系統由2n個獨立的子系統串聯而成，第i個子系統又由mi個獨立分布的邏輯單元并聯而成[11]。設Rij（t）表示第i個子系統的第j個單元在時刻t的可靠函數，i=1，2，…，2n，j=1，2，…，m，Ri（t）表示第i個子系統在時刻t的可靠函數，則有：

進而：

假設i個子系統的每個單元壽命服從Poisson分布P（λi），λi>0，則有：

m×2n多通道交叉余度系統的可靠度表達式為：

其中，t為正整數，λ為任意的實數。

當不采用級聯表決邏輯時，系統構成為m×n多通道交叉和n個表決邏輯的串聯結構，其可靠度為：

顯然，系統在一定期限內運行（≤MTTF）可靠度有明顯提高。

5 實驗驗證

基于PowerPC的開發平臺下構建了實驗環境，其分為硬件平臺、開發環境系統和軟件平臺3部分：

（1）系統硬件平臺，主要包含微處理器PowerPC8247、SDRAM、BootFlash、Flash、網絡模塊、串口、電源模塊；

（2）開發環境系統，包含GCC交叉編譯系統，連接和Glibc庫；

（3）系統軟件平臺，主要包括VxWorks和文件系統的構建。驅動程序包含CPU的初始化，串口和相關文件系統所需要的驅動。

在上述開發環境下構建了三通道狀態，設置表決面3個，表決邏輯和處理邏輯具有一致的余度。設余度系統中所有的處理和表決單元邏輯具有相同的可靠度，故障率為1/R=17.7088×10-6/h（某型號飛機對余度器件的要求），仿真中采用一個符合平均分布的故障散播函數實現故障注入，系統故障覆蓋率為0.98，余度系統要求的指令周期為20 ms，其中表決周期為2 ms，每個階段任務周期為6 ms，任務時實際執行時間為4 ms，插入的故障周期為1 ms。表決輸出采用符合一致性要求的輸入數據的算術平均值，永久故障的臨界值計數為6，仿真時間為500 h。實驗結果如表1所列。

表1 不同時間同步算法故障狀態比較（/500 h）

時間同步算法 三通道故障狀態 系統失效狀態

靜態同步算法 0.784 5E-12 0.696 3E-12

時間冗余向后遷移 0.554 1E-13 0.376 2E-13

Test_and_vote 0.981 2E-14 0.789 0E-14

從上述實驗可以看出，隨著冗余時間的利用，在靜態同步算法的基礎上，時間冗余向后遷移和Test_and_vote算法分別在故障狀態和系統失效兩個參數上都有明顯提高，即故障率降低、可靠性提高，變化幅度在10倍以上。由于靜態同步算法在時間上沒有任何容錯處理，在一個指令周期中，單個故障已經降低了系統可靠性，當出現兩個以上連續故障時，會直接導致系統的失步。而后兩種算法理論上課提供6個連續的瞬時故障，時間冗余向后遷移實際可利用故障周期為3個左右，Test_and_vote算法則進一步將可利用故障周期提高到5個左右。大大促進了系統對時間周期的可利用率，進而提高了系統的可靠性。

6 結 語

文章針對多通道余度模型中同步的可靠性問題，提出了一種基于表決邏輯控制結構的算法，該邏輯結構用來控制表決時間并監測表決數據。理論分析和實驗表明，在表決算法最大限度保證表決正確性的前提下，表決控制邏輯結構大幅提高了多通道系統的可靠性，對瞬時干擾的抵抗能力得到了提高。

參 考 文 獻

[1]張小林.小型飛行器機載計算機的余度設計技術[J].西北工業大學學報，2001，19（2）：274-278.

[2]高冰. 基于自適應模糊控制的飛機自動著陸系統[J] . 電氣傳動， 2011（8）：26-29.

[3] KANG H G， SUNG T. An analysis of safety-critical digital systems for risk-informed design [J]. Reliability Engineering and System Safety， 2002， 78（3）： 307-314.

[4] BOURAS C， GKAMAS A， KARALIOTAS A， et al. Architecture and performance evaluation for redundant multicast transmission supporting adaptive QoS [J]. Multimedia Tools and Applications， 2005， 25（1）： 85-110.

[5] KELLNER A， KOLINOWITZ. A novel approach to fault tolerant computing in space systems [C]// Proceedings of 2001 IEEE Aerospace Conference. Big Sky， MT， The USA： IEEE， 2001： 127-1131.

A synchronization mechanism analysis based on time fault tolerant

YANG Fang-ping1， ZHAO Hai-dong2

（1. College of Information Engineering， Longdong University， Qingyang 745000， China；

2. School of Continuing Education， Longdong University， Qingyang 745000， China）

Abstract： Voting logical structure plays the core role over the research and application of system in the multi channel， in order to solve this problem， a dynamic synchronous voting logic control structure is designed， which is used to control and monitor the voting time voting data. Theoretical analysis and experimental results show that voting control logic structure of the voting algorithm can greatly improve the reliability of multi – channel， while the correctness of the system is guarantee in high limited.

Keywords： multi channel； redundant system； voting； control algorithm； reliability analysis

For j=1 to m do {output（portj）：= Sign_empty；

Data_readed[i]=0 //恢復讀取標志為未讀取

break；

}

}

Call voting（Data_ready） //啟動表決

}

4 可靠性分析

當m個表決邏輯在時刻t的可靠度依次為Ri， d （t），i=1，2，…，m時，并聯表決結構的可靠度為

結合表決可靠度Rb（t），級聯表決系統的可靠度R（t）為：

當級聯表決邏輯置入m×n多通道交叉余度系統中，系統變成m×2n的多通道交叉，在不考慮數據鏈路CCDL可靠性和負載分配的前提下，系統由2n個獨立的子系統串聯而成，第i個子系統又由mi個獨立分布的邏輯單元并聯而成[11]。設Rij（t）表示第i個子系統的第j個單元在時刻t的可靠函數，i=1，2，…，2n，j=1，2，…，m，Ri（t）表示第i個子系統在時刻t的可靠函數，則有：

進而：

假設i個子系統的每個單元壽命服從Poisson分布P（λi），λi>0，則有：

m×2n多通道交叉余度系統的可靠度表達式為：

其中，t為正整數，λ為任意的實數。

當不采用級聯表決邏輯時，系統構成為m×n多通道交叉和n個表決邏輯的串聯結構，其可靠度為：

顯然，系統在一定期限內運行（≤MTTF）可靠度有明顯提高。

5 實驗驗證

基于PowerPC的開發平臺下構建了實驗環境，其分為硬件平臺、開發環境系統和軟件平臺3部分：

（1）系統硬件平臺，主要包含微處理器PowerPC8247、SDRAM、BootFlash、Flash、網絡模塊、串口、電源模塊；

（2）開發環境系統，包含GCC交叉編譯系統，連接和Glibc庫；

（3）系統軟件平臺，主要包括VxWorks和文件系統的構建。驅動程序包含CPU的初始化，串口和相關文件系統所需要的驅動。

在上述開發環境下構建了三通道狀態，設置表決面3個，表決邏輯和處理邏輯具有一致的余度。設余度系統中所有的處理和表決單元邏輯具有相同的可靠度，故障率為1/R=17.7088×10-6/h（某型號飛機對余度器件的要求），仿真中采用一個符合平均分布的故障散播函數實現故障注入，系統故障覆蓋率為0.98，余度系統要求的指令周期為20 ms，其中表決周期為2 ms，每個階段任務周期為6 ms，任務時實際執行時間為4 ms，插入的故障周期為1 ms。表決輸出采用符合一致性要求的輸入數據的算術平均值，永久故障的臨界值計數為6，仿真時間為500 h。實驗結果如表1所列。

表1 不同時間同步算法故障狀態比較（/500 h）

時間同步算法 三通道故障狀態 系統失效狀態

靜態同步算法 0.784 5E-12 0.696 3E-12

時間冗余向后遷移 0.554 1E-13 0.376 2E-13

Test_and_vote 0.981 2E-14 0.789 0E-14

從上述實驗可以看出，隨著冗余時間的利用，在靜態同步算法的基礎上，時間冗余向后遷移和Test_and_vote算法分別在故障狀態和系統失效兩個參數上都有明顯提高，即故障率降低、可靠性提高，變化幅度在10倍以上。由于靜態同步算法在時間上沒有任何容錯處理，在一個指令周期中，單個故障已經降低了系統可靠性，當出現兩個以上連續故障時，會直接導致系統的失步。而后兩種算法理論上課提供6個連續的瞬時故障，時間冗余向后遷移實際可利用故障周期為3個左右，Test_and_vote算法則進一步將可利用故障周期提高到5個左右。大大促進了系統對時間周期的可利用率，進而提高了系統的可靠性。

6 結 語

文章針對多通道余度模型中同步的可靠性問題，提出了一種基于表決邏輯控制結構的算法，該邏輯結構用來控制表決時間并監測表決數據。理論分析和實驗表明，在表決算法最大限度保證表決正確性的前提下，表決控制邏輯結構大幅提高了多通道系統的可靠性，對瞬時干擾的抵抗能力得到了提高。

參 考 文 獻

[1]張小林.小型飛行器機載計算機的余度設計技術[J].西北工業大學學報，2001，19（2）：274-278.

[2]高冰. 基于自適應模糊控制的飛機自動著陸系統[J] . 電氣傳動， 2011（8）：26-29.

[3] KANG H G， SUNG T. An analysis of safety-critical digital systems for risk-informed design [J]. Reliability Engineering and System Safety， 2002， 78（3）： 307-314.

[4] BOURAS C， GKAMAS A， KARALIOTAS A， et al. Architecture and performance evaluation for redundant multicast transmission supporting adaptive QoS [J]. Multimedia Tools and Applications， 2005， 25（1）： 85-110.

[5] KELLNER A， KOLINOWITZ. A novel approach to fault tolerant computing in space systems [C]// Proceedings of 2001 IEEE Aerospace Conference. Big Sky， MT， The USA： IEEE， 2001： 127-1131.

A synchronization mechanism analysis based on time fault tolerant

YANG Fang-ping1， ZHAO Hai-dong2

（1. College of Information Engineering， Longdong University， Qingyang 745000， China；

2. School of Continuing Education， Longdong University， Qingyang 745000， China）

Abstract： Voting logical structure plays the core role over the research and application of system in the multi channel， in order to solve this problem， a dynamic synchronous voting logic control structure is designed， which is used to control and monitor the voting time voting data. Theoretical analysis and experimental results show that voting control logic structure of the voting algorithm can greatly improve the reliability of multi – channel， while the correctness of the system is guarantee in high limited.

Keywords： multi channel； redundant system； voting； control algorithm； reliability analysis