一种基于时间容错的同步机制分析

杨芳萍+赵海东

摘 要：表决逻辑结构在多通道余度系统的研究和应用中起着核心作用，针对该问题，设计了一个具有动态同步表决控制的逻辑结构，该逻辑结构用来控制表决时间并监测表决数据。理论分析和实验表明，该表决算法在最大限度保证表决正确性的前提下，其表决控制逻辑结构还可以大幅度地提高多通道系统的可靠性。

关键词：多通道；余度系统；表决；控制算法；可靠性分析

中图法分类号：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