李洪超

(上海理工大学光电信息与计算机工程学院,上海200090)

计算机的应用十分广泛,航空航天、军事、银行监管系统、交通运输系统以及其他重要的工业领域对计算机的可靠性要求非常高。计算机系统出现故障不仅会导致国家财产的严重损失,还会危及人身安全。因此,在这些领域中计算机的可靠性越来越受到人们的重视,国家非常重视可靠性的研究工作,投入了大量的资源。

1 基本容错技术

一般而言,提高计算机的可靠性有两种比较有效的方法。一种是避错,就是避免出现故障,这就需要严格筛选计算机元器件,完善设计,提高制造工艺,以及加强质量管理等。但即使是这样一个计算机系统,由于其所在的工作环境有各种环境应力,如湿度、温度、电磁干扰、强震动等,因此总避免不了出现故障。这就要求在计算机出现故障的情况下容忍故障的存在,即第二种方法——容错技术。容错技术最早由约翰◦冯◦诺依曼(John Von Neumann)提出,所谓容错是指在出现一个或者几个硬件或软件方面的故障或错误的情况下,计算机系统能够检测出故障的存在并采取措施容忍故障,不影响正常工作,或者在能够完成规定的任务的情况下降级运行[1]。

故障是指由于部件的物理失效、环境应力的作用、操作错误或不正确的设计,引起系统的硬件或软件的错误状态[2]。下面介绍几种相关技术的基本概念。

故障检错技术:对于计算机系统的容错首先要用到故障检错技术,即在计算机系统发生故障的情况下能够检测出故障的存在。

故障诊断技术:检测出系统存在故障后要进行故障的定位,找出故障所在的位置。

故障恢复技术:在检测出故障和定位故障的所在位置之后,就要运用故障恢复技术把系统从故障的状态恢复到无故障的状态继续运行。

容错最基本的的方法是冗余技术,所谓冗余就是超过系统实现正常功能的额外资源。冗余包括硬件冗余、软件冗余、时间冗余和信息冗余[3]。

1.1 硬件容错技术

硬件冗余又包括静态硬件冗余(也叫被动硬件冗余)、动态硬件冗余(也叫主动硬件冗余)和混合冗余(静态冗余和动态冗余的结合)。静态硬件冗余常见的形式有三模冗余(TMR),其基本原理是:系统输入通过3个功能相同的模块,产生的3个结果送到多数表决器进行表决,即三中取二的原则,如果模块中有一个出错,而另外两个模块正常,则表决器的输出正确,从而可以屏蔽一个故障,TMR的缺点是,如果3个模块的输出各不相同,则无法进行多数表决;若有两个模块出现一致的故障,则表决的结果会出现错误。TM R结构如图1所示。

三模冗余可推广到N模冗余(NM R),其基本原理与TMR的原理相同,其中N≥3,且N为奇数,以便进行多数表决。动态冗余是指当检测到工作的模块出现错误时,就切换到一个备用的模块,当换上的备用模块又发生故障时,再切换到另一个备用模块,依次类推,直到备用的模块用完。

图1 TMR结构图

1.2 时间容错技术

时间容错的基本思想是:重复执行指令或者一段程序来消除故障的影响,以达到容错的效果,它是用消耗时间来换取容错的目的。根据执行的是一条指令还是一段程序,分成两种方法:

一种是指令复执。当检测出故障的时候,重复执行故障指令,若故障是瞬时的,则在指令复执期间可能不会出现,程序就可以继续向前运行。指令复执必须保留上一指令结束的“现场”,包括累加器、PC及其他状态寄存器的状态。

另一种是程序卷回。它不是重复执行一条指令,而是重复执行一小段程序。在整段程序中可以设置多个恢复点,程序有错误的情况下可以从一个个恢复点处开始重复执行程序。首先检验一小段程序的计算结果,若结果出现错误则卷回再重复执行那个部分,若一次卷回不能解决,可以多次卷回,直到故障消除。

1.3 信息容错技术

信息容错技术是通过在数据中附加冗余的信息位来达到故障检测和容错的目的。通常情况下,附加的信息位越多,其检错纠错的能力就越强,但是这同时也增加了复杂度和难度。信息冗余最常见的有检错码和纠错码。检错码只能检查出错误的存在,不能改正错误,而纠错码能检查出错误并能纠正错误。常用的检错纠错码有奇偶校验码、海明码、循环码等。

1.4 软件容错技术

由于硬件系统的故障主要来自生产和使用阶段,因此容错可以通过相同部件的重复,即相同资源的累积设置来实现;而软件故障主要来自说明、设计和实现阶段,因此程序的简单重复不能实现容错,它只能防止硬件损坏或者环境干扰等引起的物理性故障,而不能防止软件本身缺陷造成的故障。实现软件容错的基本方法,是将若干个根据同一需求说明编写的不同程序(即多版本程序),在不同空间同时运行,然后在每一个设置点通过表决或接收测试进行表决。

最基本的软件容错技术是Algirdas Avizienis提出的基于静态冗余的N版本编程方法和B.Randell提出的基于动态冗余的恢复块技术[4]。

1.4.1 软件的相异性设计

对于软件容错,考虑的重点是软件设计的相异性和版本的独立性。软件的相异性设计是为了防止由于软件发生共性故障而采用的一种设计方法。软件设计时的共性越小,出现相同故障的概率也就越小,容错性能就越强[5]。

相异性设计要求,对于同一需求说明的软件功能,不同的研发设计人员及不同的研发设计小组对于这同一功能的软件设计禁止谈论和沟通,在不同的环境空间中独立进行设计;另外,还要求软件设计的多样性,如采取不同的设计方法、开发工具、编程语言、编译器、算法等。在航空航天、核电站控制以及铁路交通的控制等对软件的可靠性要求很高的场合,软件的相异性设计可以有效提高软件的容错能力和软件的可靠性,对提高整个系统的可靠性有很重要的作用。

1.4.2 软件容错的基本结构

软件容错的基本结构有两种[1,3-4]:

一种是NVP(N-Version Programming)结构(多版本编程设计),这种结构方法是Algirdas Avizienis于1977年在参考文献[6]中提出的,它是一种静态冗余方法,其基本的设计思想是用N个具有同一功能而采用不同编程方法的程序执行一项运算,其结果通过多数表决器输出。NVP系统中的多版本是指根据同一需求说明由不同的设计人员或由不同的设计方法、开发工具、编程语言等开发的具有同一功能的软件版本,即所谓的版本设计的相异性。这种容错结构方法有效避免了由于软件共性故障所造成的系统出错,提高了软件的可靠性。NNP结构如图2所示。

另一种是RB(Recovery Block,恢复快结构),它是Randell于1975年在参考文献[7]中提出的一种的软件容错技术,它是一种动态冗余方法。在RB结构中,有主程序块和一些备用程序块构,这里的主程序块和备用程序块采用不同编程方法但具有相同的功能。每个主程序块都可以用一个根据同一需求说明设计的备用程序块替换。首先运行主程序块,然后进行接收测试,如果测试通过则将结果输出给后续程序,否则调用第一个备用块,依次类推,在N个备用程序块替换完后仍没有通过测试,则要进行故障处理。RB结构如图3所示。

图2 NVP结构

图3 RB结构

其他的软件容错结构都是基于这两个基本结构而来的,例如NVPP[8](多版本阶段程序设计),它要求程序的版本运行分多个阶段进行,而且每个阶段运行的程序都包括适当的版本数量。运行一个阶段后,要通过表决程序来对这一阶段运行的程序进行表决,如果得到正确的结果就结束运行,否则继续下一个阶段版本的运行,直到得出正确的结果。

NVP和RB这两种基本结构在软件容错中用得最广泛,占据很重要的地位。这里要注意的是,验证表决程序的可靠性以及表决结果的正确性是个难点,因为如果表决程序本身就是错误的,那表决的结果就不可信了,所以要用正确性证明技术来保证表决程序的正确。

2 结 论

本文详细介绍了计算机容错的各种方法,包括硬件容错、时间容错、信息容错以及软件容错等,这些容错方法在其他工业场合有广泛的应用,现在很多工业系统都是采用基于三模冗余的容错技术来提高系统的可靠性。对于其他要求可靠性高的场合,计算机容错技术的方法有着良好的应用前景。

[1]袁由光,陈以农.容错与避错技术及其应用[M].北京:科学出版社,1992.

[2]国防科学工业技术委员会.GJB 3180-98军用计算机容错要求与测评[S],1998.

[3]胡谋.计算机容错技术[M].北京:中国铁道出版社,1995.

[4]Kanoun K,Kaaniche M,Beounes C,et al.Reliability Grow th of Fault-tolerant Software[J].IEEE Transactions on Reliability,1993,42(2):205-218.

[5]韩炜,杨孝宗,等.相异性容错设计的概念及其实现[J].哈尔滨工业大学学报,2001,33(5).

[6]Randell B.System Structure for Software Fault Tolerance[J].IEEE Transactions on Software Engineering,1975(SE-1):220-232.

[7]Avizienis A,Chen L.On The Implementation of N-Version Programming for Softw are Fault-Tolerance During Program Execution:proceedings of the 1977 International Conference on Computer Software and Application[C],1977:149-155.

[8]徐仁佐.软件可靠性工程[M].北京:清华大学出版社,2007.