（计算机应用技术专业论文）计算机容错系统的体系结构与安全性研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要1 哆印2 & l 针算机容错系统是由若干台计算机按照一定的容错原则通过资源冗余， 配置构成冗余结构的计算机系统，当系统出现一定的运行性故障时，能够依 赖系统内驻的容错能力保证系统连续正确地执行其程序并输出正确的结果。 信息时代的到来，计算机技术的广泛应用，在某些领域对计算机系统的可靠 性要求愈来愈高，因此开展计算机容错系统及容错技术的研究也显得越来越 重要。y 7 本文对计算机容错系统的理论基础、模型结构、组成方法以及评价过程 作了详细的论述。具体针对三模混合冗余、增强型双机比较及带热备份的双 机比较三种典型体系结构的计算机容错系统进行了研究，统一用马尔可夫模 型进行描述，通过理论分析和计算，获得各体系结构容错系统的可靠度与安 全度的数学模型；通过分析，合理定义了系统的任务工作期区间，并在此区 间上比较分析了各体系结构容错系统的可靠度与安全度情况，从而对各系统 的可靠性指标进行了评价；根据上述三种系统的数学模型，在考虑系统故障 覆盖率与维修率两个参数对系统可靠度与安全度影响的情况下，用m a t l a b 语言编制了计算机仿真程序。在系统的任务工作期区间内对系统进行仿真计 算，并获得系统的可靠度与安全度的变化规律。通过分析得出系统的故障覆 盖率与维修率在容错系统的评价过程中起到非常重要的作用。 本文最后对容错技术的深入研究所涉及的相关关键技术和研究思路提出 了一些设想和建议，并说明了容错技术的开放化及标准化是容错技术得以推 广应用的重要前提。 关键词容冀系统? 多鼍考多呈琶箩马i ! 多券模型 、一 v 西南交通大学硕士研究生学位论文 第页 a b s t r a c t 1 1 1 ec o m p u t e rf a u l t - t o l e r a n ts y s t e mi sar e d u n d a n ts y s t e mc o m p o s e d o f m u l t i c o m p u t e r sb y r e d u n d a n tr e s o u r c ea n ds t r u c t u r e a c c o r d i n g t ot h ed e f i n i t e f a n l t - t o l e r a n tp r i n c i p l e w h e nr a n - t i m e e r o rc o m e sf o r t h , t h ef a u l t - t o l e r a n ts y s t e m w i l lc o n t i n u ee x e c u t i n gt h ep r o c e d u r ea n dg i v i n go u tp r o p e r r e s u l t sd e p e n d i n go n t h ei n n e rr e s i d e n tc a p a b i l i t y w i t h t h ei n f o r m a t i o n a g e s c o m i n g a n dt h e w i d e s p r e a da p p l i c a t i o n s o fc o m p u t e rt e c h n o l o g y , t h er e l i a b i l i t yo fc o m p u t e r s y s t e m sw a sp a i dm o r ea t t e n t i o ni ns o m ef i e l d s s od e v e l o p i n gt h er e s e a r c ho f c o m p u t e r f a u l t - t o l e r a n ts y s t e ma n df a u l t - t o l e r u n tt e c h n o l o g yi sv e r yi m p o r t a n t t h i sp a p e r e x p l i c a t e st h et h e o r e t i c a lf o u n d a t i o n , m o d e ls t r u c t u r e ，c o m p o s i n g f o r ma n de v a i u a t i o ni 1 1d e t a i l w ei n v e s t i g a t e dt h ea r c h i t e c t u r e so ft h r e et y p i c a l c o m p u t e rf a u l t - t o l e r a n ts y s t e m ss u c ha st r i p l em o d u l a r a d m i x t u r er e d u n d a n c y s y s t e m ，b u i l d u p d u a l c o m p u t e rc o m p a r i n gs y s t e m a n dd u a l c o m p u t e r c o m p a r i n gs y s t e m w i t l ih o t s t a n d b y , a n dd e s c n p tt h e m w i t ht h em a r k o vm o d e l t h er e l i a b i l i t ya n ds a f e t ym o d e io ft h e s ef a u l t - t o l e r a n ts y s t e m sa r ea c q u i r e d t h r o u g ht h e o r e t i c a la n a l y z i n ga n dc a l c u l a t i n g w i t ha n a l y z i n g , w ed e f m e dt h e s y s t e m s t a s ki n t e r v a la v a i l a b l et i m es e c t i o ni nm a s o n , c o m p a r e dt h e i rr e l i a b n i t y a n d s a f e t ya n d e v a l u a t e dt h e i rr e l i a b i l i t i e s a c c o r d i n gt ot h e i rm a t h e m a t i c s m o d e l a n dt a k i n gt h ei n f l u e n c e so f t h ec o v e m g er a t i oa n dm a i n t e n a n c er a t i oi n t oa c c o u n t , w ec o m p i l e dt h es i m u l a t i n gp r o g r a m sw i t hm a t l a b l a n g u a g e d u r i n gt h et a s k i n t e r v a la v a i l a b l et i m es e c t i o n ，w es i m u l a t e da n dc a l c u l a t e dt h er e l i a b i l i t i e sa n d s a f e t i e so ft h es y s t e m s ，a n da c q u i r e dt h es y s t e m s v a r i e t yr o l e so f r e l i a b i l i t ya n d s e c u r i t y s i n c et h es y s t e mp a r a m e t e r sf a u l t yc o v e r a g er a t i oa n dm a i n t e n a n c e r a t i o i n f l u e n c et h es y s t e m sr e l i a b i l i t ya n ds e c u r i t y , w ea n a l y z et h e ma n df i n do u t t h e y p l a y a ni m p o r t a n tr o l ei nt h ee v a l u a t i o no f f a u l t - t o l e r a n ts y s t e m a tl a s t ，t h i sp a p e rg i v eo u ts o m et e n t a t i v ep l a n sa n d8 0 m e s u g g e s t i o n sa b o u t t h er e l a t e dt e c h n o l o g i e sa n dr e s e a r c ht h o u g h to fl u c u b r a t i n gt h ef a u l t - t o l e r a n t t e c h n o l o g ya n d i n d i c a t e st h a ti t so p e n i n ga n ds t a n d a r d i z a t i o ni st h ep r e c o n d i t i o n f o rt h i st e c h n o l o g y sp r e v a l e n c e k e y w o r d s ：f a u l t t o l e r a n t ；r e d u n d a n c y ；r e l i a b i l i t y ；s a f e t y ；m a r k o vm o d e l 西南交通大学硕士研究生学位论文第l 页 第l 章绪论 1 1 研究计算机容错系统的重要性 信息时代，信息科学技术的快速发展和广泛渗透已经成为现今社会的一 个重要的时代特征。人类社会的生产活动和生活质量，比以往任何时代都更 加得益和依赖于信息技术的成就和发展。据统计，在商业市场中，如果公司 丢失了1 0 的数据，其中6 5 的公司会因此而退出竞争市场。信息成为人们 前进的道路，而作为信息处理与传播的主要工具的计算机在信息社会中占据 了非常重要的地位。计算机已渗透到了社会生活的各个领域。从工程设计、 科学计算，到气象预报、地震预报和各种c a d 工作站；从城市的交通规划 管理、调度，到海运、空运的交通控制；从银行系统、各种过程控制系统， 到国防、航空航天等领域，计算机都占据了非常重要的地位。计算机系统的 安全性和可靠性是保证在各个领域成功应用计算机的关键问题。因为安全性 和可靠性对整个系统的正常运行、管理和发展都有着至关重要的影响。一台 缺乏可靠性与安全性的计算机系统投入运行将会给社会造成无法估量的损 失，甚至会带来巨大的灾难。例如，1 9 7 9 年，新西兰航空公司的一架客机因 为计算机控制的自动飞行系统发生故障，而撞到了阿尔卑斯山上，机上2 5 7 名乘客不幸遇难。还有，前年发生在我国衡阳的火车追尾事故，也是由于计 算机控制系统出现故障而引起的。这种种灾难都表明保证计算机系统的可靠 运行或使系统在出现故障时安全停机是推动计算机普及应用的关键。 在提高系统可靠性与安全性方面，避错与容错技术是常用的两种关键性 技术。避错即避免出错，即采用正确的设计和质量控制方法尽量避免将错误 引进系统。一般采用的技术措施有：从工艺上提高构成计算机的元器件的可 靠性；对元器件进行严格的筛选：认真地核实设计：仔细地装配；认真地测 试每个部件；对系统进行屏蔽以减少外部干扰等等。但众所周知，无论采用 何种技术，如何控制制造工艺都不可完全避免故障的发生。并且实践证明， 利用避错技术来提高系统的可靠性有一定的限度( 例如最多可使系统的平均 无故障时间增加一个数量级) ，超过这个限度将使系统的成本急剧上升。要想 进一步提高系统的可靠性则必须采用容错技术。容错技术是指系统在内部出 西南交通大学硕士研究生学位论文第2 页 现故障的情况下，仍能正常运行程序，并给出正确结果的技术在实际应用 中，用户使用计算机进行管理、交易、控制等操作。他们关心的是系统能否 给出正确结果，而并不关心其中采用何种技术，是否中途出现故障a 故容错 技术在提高系统的可信性方面具有更大的潜力。在当今计算机日益普及的年 代，研究计算机容错系统就显得尤为重要。 1 2 容错技术在国内外的研究概况 1 2 1 国外发展概况 在计算机容错技术领域，国外的研究工作开展较早。可以说在第一代计 算机( 1 9 4 6 年1 9 5 7 年) 期间，人们就已将容错技术应用到计算机中。由于 当时构成计算机的元件主要是电子管、继电器及延迟线存储器。这些元件的 失效率相当高，并且易受瞬时故障的影响，故系统的平均无故障时间极短， 为此需采用故障检测与恢复技术以提高系统的使用时间。例如， i b m 6 5 0 ，u n i v a c ，w h i r l w i n di 等计算机采用了奇偶校验以检查数据传送的 结果是否正确。还有，1 9 4 9 年设计的e d v a c 计算机采用了双份运算部件，每 次运行后两个部件的结果进行比较，用以检测故障。这个时期已出现了早期 的容错系统。1 9 5 2 年冯诺依曼( j o h n1 o nn e u m a n n ) 在加利福尼亚技术学 院作了关于容错技术研究的五个报告，他所提出的精辟的论断成了以后容错 技术研究的基础。1 9 5 6 年他发表了题为概率逻辑及用不可靠的元件设计可 靠的结构的论文，文中提出了多数表决的概念，并分析了这种结构对系统 产生错误结果的概率可能产生的影响。这预示着容错计算方面的理论工作的 开始。 到了7 0 年代，随着计算机的更新换代，容错技术进入蓬勃发展的时期。 该时期容错技术的应用和研究范围迅速从宇航领域扩大到交通管制、工厂自 动化、电话开关、战略防卫的控制和数据处理等领域。主要成果有电话开关 系统e s s 系列处理机、软件实现容错的s i f t 计算机、容错多处理机f t 静等 等。 到8 0 年代，随着超大规模集成电路v l s i 和计算机的迅速发展和广泛应 用，容错技术的研究也随着计算机的普及而深入到整个工业界，许多公司生 产的容错系统已商品化并进入市场。 西南交通大学硕士研究生学位论文第3 页 在国际上人们非常关注容错技术的发展，1 9 7 1 年，i e e e 计算机学会成立 了容错计算技术委员会并且每年召开一次国际容错计算学术会议( f t c s ) a 在 该组织发展了3 0 年之际，2 0 0 0 年i e e e 国际容错计算会议与国际信息处理联 合会( i f i p ) 的1 0 4 工作组主持的关键应用可信计算工作会议合并，从此改 名为i e e e 可信系统与网络国际会议( i c d s n ) 。i c d s n 2 0 0 0 于纽约召开，它 标志着本领域的研究，无论从内容、方法和组织方面都有重大调整，也充分 说明了国际上对容错计算技术与可信计算技术的重视程度。 1 2 2 国内发展概况 我国研究容错系统起步较晚。从学术角度来讲，在8 0 年代我国派遣了一 批学者出国，他们在美国和日本从事容错方面的研究，回国后纷纷成为这一 领域的学术带头人。二十多年来，他们的优异工作得到了该领域的广泛关注， 现在我国在容错研究领域的某些方面已经居于国际前沿。1 9 8 7 年1 月我国计 算机学会也成立了自己的容错计算专业委员会，召开了多次全国性的容错计 算学术会议。这充分说明了我国对容错计算技术的重视程度。 在应用方面，我国容错系统的应用领域非常广泛，i b m 、s t r a t u s 、天腾、 d e c 等公司的容错产品大量传入我国，在银行、证券、航天及核技术领域得 到了普遍的应用。 在产品研发上，虽然我国目前还没有形成通用的计算机容错产品，但各 行各业在各自的领域中自行开发研制了一些高可用系统，如用于铁路运输中 的铁路微机联锁系统。更令人高兴的是，我国的曙光机和我们自行开发研制 的交换机系统中提供了容错性能。并且在软件测试方面也引起了人们的重视， 铁道、航空和航天等部门纷纷成立了自己的软件测试中心，由此可见人们已 经充分意识到了容错的重要性。 1 3 本论文的研究工作 本课题“计算机容错系统的体系结构与安全性研究”是四川省应用基础 研究项目。具体研究工作如下： 研究三种典型的计算机容错系统即兰模混合冗余、增强型双机比较与带 热备份的双机比较的体系结构，统一用马尔可夫模型进行描述，通过理论计 西南交通大学硕士研究生学位论文 第4 页 算，获取各体系结构的可靠度与安全度的数学模型a 对上述三种典型结构的系统，定义合理的任务期区间，在此区间上比较 各体系结构的可靠度与安全度情况。分析系统方案的优劣指标。 射以上分析的三种系统，按其数学模型进行计算机仿真，在任务期区间 内，获得可靠性、安全性的变化规律，并分析系统的参数故障覆盖率与维修 率对系统可靠度与安全度的影响情况。 西南交通大学硕士研究生学位论文 第5 页 第2 章计算机容错系统的体系结构研究 随着计算机系统的广泛应用和复杂性的急剧提高，系统运行的可靠性问 题越来越引起人们的注意。容错技术是构建高可靠系统的最有力的手段之一。 在当今这个信息时代，随着大规模及超大规模集成电路的迅猛发展，容错技 术在提高系统的可靠性方面越来越受到人们的重视。容错是利用资源的冗余 来实现的，其确切定义是：如果一个系统在出现一定的运行性故障时，能够 依赖系统内驻的能力仍保持系统连续正确地执行其程序和输入输出功能。具 有这种特性的计算机系统则叫做计算机容错系统。 2 1 容错技术的分类及基本模型 2 1 1 容错技术的分类 为了达到容错的目的。容错系统必须克服故障的影响，一个容错系统可 能经历多达1 0 个阶段： 故障限制：限定故障的传播范围，防止故障对其它区域的污染。 故障检测：尽快发现故障，减少故障潜伏期。可分为脱机和联机检测。 故障屏蔽：掩盖故障对输出的影响。 重试：再作一遍或若干遍，消除对不引起物理破坏的瞬时故障的影响。 诊断：确定故障的位置。 重组：当检测出一个故障并判明是一个永久性故障时，这对重组系统的器 件以便替代失效的器件或把失效的器件与系统的其他部分隔离开来，可使冗 余系统的能力不降低。 恢复：检测和重组后，使系统操作回到故障检测前的处理点。 重启：当恢复不能消除故障影响时，采用“热”重启( 从故障检测点恢 复所有的操作) 或“冷”重启( 重新引导装入系统) 。 修复：对故障部件进行修理使之复原，修复也可脱机或联机进行。 重构：把修复了的部件加入系统，若修复是联机进行的，则重构不能中 断系统的运行。 西南交通大学硕士研究生学位论文第6 页 ( 1 ) 按照系统的这些失效响应阶段，可以把各种容错技术分成三种：故 障检测、静态冗余、动态冗余。 故障检测不提供对故障的容忍，而是当发生故障时给出一个警告。故障检 裰9 广泛应用于微型机和小型机之类的许多小系统中，其中一些已体现了简单 的联机检测机理。严格来说，故障检测不是容错，因为尽管检测了故障，但 不能容忍这些故障( 对瞬时故障的静态重试除外) 。 静态冗余能容忍故障，但不给出故障警告。 动态冗余用于纠错码存储器或具有固定配置( 即线路器件之间的逻辑连接 保持不变) 的多数表决冗余计算机之类的系统中。 ( 2 ) 根据容错系统所采用的冗余方式的不同，可将容错技术分为：硬件 冗余容错，信息冗余容错，时间冗余容错及软件冗余容错四种形式。 硬件冗余是通过对物理部件的重复来达到容错的目的。 信息冗余是通过在数据中附加冗余的信息来达到故障检测、故障掩蔽或 容错的目的。 时间冗余的基本思想是重复进行计算以检测故障。有指令复执及程序卷 回两种形式。 软件冗余的基本方法是将若干个根据同一需求说明编写的不同程序( 或 程序块) ，在不同空间同时运行或在同一空间依次运行，然后在每一个预定的 点通过表决或接受测试进行裁决。在判明其正确或一致后接受这个结果。否 则便加以拒绝，并给出报警信息。 ( 3 ) 根据计算机系统采用冗余技术的部位不同，又可将容错技术分为： 系统级容错、部件级容错和元器件级容错。 2 1 2 容错系统的基本模型简介 容错技术主要是依靠资源的冗余和资源的精心组织来完成，随着半导体 元件体积的缩小及成本的下降，以及超大规模集成电路的发展，在计算机容 错系统的设计中采用硬件冗余成为当前比较常用的方法。硬件冗余分为被动 硬件冗余、主动硬件冗余和混合硬件冗余。 被动硬件冗余又称为静态硬件冗余，它应用了故障掩蔽的概念，是指冗 余结构并不随故障情况变化的冗余形式。通常采用的结构是三模冗余( t r i p l e m o d u l a r r e d u n d a n c y , 简称t m r ) 西南交通大学硕士研究生学位论文第7 页 如图2 1 所示，三模冗余是将系统的输入同时输给三个相同的模块， 并将三个模块产生的结果送到表决器上。表决器的输出取决于它的三个输入 的多数。若其中一个模块有故障，则另两个正常模块的输出可将故障模块的 输出掩蔽，从而不会在表决器的输出中产生差错，这样就达到了容错的目的。 输入 图2 - 1 三模冗余结构 输出 三模冗余的主要问题是表决器的故障将使整个系统产生差错。为克服这 一问题可采用多重表决系统，即将三个模块的输出同时输出到三个相同的表 决器上，利用多数表决的原理对表决器进行次表决，但因此却增加了系统 复杂度。故有人提出了利用冗余共享存储器实现多机通讯，由多个模块利用 各自的处理机系统在冗余共享存储器环境中对冗余处理的结果进行表决，经 过多数表决错误被屏蔽，得到正确结果从而实现容错。这就解决了系统可靠 性对表决器的依赖问题。 为了迸一步提高系统的可靠性，可以采用n 模冗余( n m r ) 。n m r 与 t m r 的原理相同，只是采用n 个相同的模块。n 一般为奇数，以方便进行 多数表决。n m r 可以容忍( n - 1 ) ，2 个故障模块。 静态硬件冗余系统虽然能容忍部分模块的故障，但它要求大部分模块正 常工作。当工作模块数不大于故障模块数时，系统将无法正常工作，这就造 成系统资源的浪费。 主动硬件冗余又称为动态硬件冗余，它主要采用重组技术。是通过故障 检测、故障定位及故障恢复来达到容错的一种技术。主动硬件冗余的形式有： 双机比较、备用替换和成对备用。 如图2 2 所示是双机比较的最简单方案，它由两个相同模块并行执行相 同的计算，其结果由比较器进行比较。一致则产生输出，不一致则拒绝输出。 它提供故障检测能力，但不提供容错。 西南交通大学硕士研究生学位论文第8 页 在图2 2 的方案下若配以故障定位技术及切换技术则构成具有容错性能 的比较系统。例如在上述比较结果不一致时。可以启动自诊断程序，以确定 有故障的模块，并利用切换程序将其切除。将正常模块的输出作为最后输出， 系统则以单机系统继续运行。若配以自动恢复装置，则在故障模块修复后， 将其重新接入系统。 输入 不一致检测 图2 2 双机比较 备用替换是采用一个模块为主模块，用以产生输出，其余为备用模块。 采用各种故障检测技术及故障定位技术来确定发生故障的模块。若主模块发 生故障则进行重组，使一个正常工作的备用模块成为主模块。 备用替换中的备件可以分为热备与冷备。热备时备件与主模块同步工作， 冷备时，备件不加电，需要备件接替工作时才加电并初始化。 成对备用是将备用替换与双机比较集合起来的一种形式。 动态硬件冗余采用了系统重组技术，可以提高系统的利用率。 将主动冗余与被动冗余结合起来就构成混合硬件冗余，混合冗余的成本 较高，故一般用于需要极高可靠度的地方。混合冗余的形式有带备件的n 模 冗余、自清除冗余、筛选模块冗余和三模双机系统。 如图2 - 3 是带备件的n 模冗余形式，其基本核心是n 个模块构成的表决 结构，外加若干个备件以替换n m r 核心中的失效模块。利用不一致检测器 将表决器的输出与n 个模块的输出进行比较，以发现故障模块。若发现故障 模块，则由开关网络将该模块切除并用一个正常工作的备件代替。 自清除冗余的结构如图2 _ 4 所示。用开关比较器对表决器的输出与本模 块的输出进行比较。若不一致则将本模块切除。以( n 1 ) 模表决结构继续运 行。 筛选模块冗余的结构如图2 5 所示。系统同时将数据输入n 个模块，比 较器将各个模块的结果一对一地进行比较，每次比较一致时输出l ，不一致 时输出0 。检测器根据比较器的输出确定有故障的模块，并为每个模块产生 一个指示信号，用l 表示该模块有故障，用o 表示该模块正常。最后，收集 器根据每个模块的输出和检测器的指示产生系统输出。被指示为故障的模块 西南交通大学硕士研究生学位论文 第9 页 不允许影响系统的输出。 输入 输入 输入 图2 - 3 带备件的n 模冗余 萝剖 图2 4 自清除冗余 图2 5 筛选模块冗余 输出 输出 输出 西南交通大学硕士研究生学位论文 第1 0 页 三两两机系统是将双机比较与三模冗余结合起来的一种容错形式。 双机输出经比较器比较，若不一致则将该模块切除。该系统能容忍多至两个 模块的故障。 输入 图2 - 6 三模一双机系统 2 2 计算机容错系统的体系结构研究 输出 计算机容错系统是指在机器级采用容错技术以提高整个系统的可靠度及 安全度。当所选用的计算机的性能一定时，系统的体系结构便决定了整个系 统的总体性能。根据系统的拓扑结构不同，可以构造不同的计算机容错系统。 下面介绍几种比较实用的计算机容错系统的结构。 2 2 1 三模混合冗余系统 如图2 7 所示为三模混合冗余系统的系统结构。系统由3 个能完成相同 功能的计算机模块，一个进行多数表决及完成比较功能的多数表决比较恢复 器( m v r ) ，一个用于产生单一输出结果的磁通和，一个进行失效比较与模式 控制的失效安全比较器及模式控制系统( f s c _ _ l 婚c c ) 以及用于显示系统工 作模式及工作状态的监视器构成。 系统的工作原理是：利用监控软件对系统的硬件和软件工作状况进行监 西南交通大学硕士研究生学位论文第ll 页 视，确保3 个计算机模块以外的各个硬件模块正常工作并避免自身的失效。3 个计算机模块由一个冗余时钟同步，每次将输入信号同时输入3 个计算机进 行运算处理，并将运算结果送往多数表决比较恢复器( m v r ) ，同时送入失 效安全比较器及模式控制系统( f s c m c c ) 。f s c - - m c c 系统进行故障定 位及切换工作，以确定系统的工作状态。若3 个计算机模块均正常工作，则 系统以三模冗余模式工作；若有一个计算机模块失效，并由f s c - - m c c 检测 定位故障计算机模块并且成功切除，系统将降级为双机比较系统；若又有一 个计算机模块失效并被定位切除，则系统以单机模式运行。失效计算机模块 经修复后，又回到工作状态。 图2 - 7 三模混合冗余系统结构 2 2 2 增强型双机比较系统 出 如图2 - 8 所示为增强型双机比较系统的系统结构。系统由2 个能完成相 同功能的计算机模块与一个进行故障诊断的比较器组成。系统中带有进行故 障定位的自诊断程序以及当检测到故障时进行切换处理的切换开关k l ，l 【2 。 k 1 输入 不一致检测 图2 - 8 增强型双机比较系统 系统的工作原理是：2 个能完成相同功能的计算机模块并行执行相同的计 西南交通大学硕士研究生学位论文第1 2 页 算，计算结果送比较器进行比较以确定是否存在故障。当比较器给出的结果 一致时，系统将任一计算机的结果作为系统的最后输出结果。当比较器给出 的结果不一致时，系统启动自诊断程序进行故障定位，若系统无法定位故障， 则停机：若系统定位故障，则由切换开关将故障计算机模块切除。系统以非 故障机器的输出作为系统的最后输出结果。并且系统以单机系统继续运行。 故障机转去维修，维修好后继续投入使用。 2 2 3 带热备份的双机比较系统 如图2 - 9 所示为带热备份的双机比较系统的系统结构。系统在增强型双 机比较系统的基础上，增加了一个热备计算机。系统中同样带有进行故障定 位的自诊断程序。当检测定位了工作计算机模块故障时，在切除了故障模块 的同时，将处于正常工作的热备计算机模块接入系统。 系统的工作原理是：系统开始以带热备份的增强型双机比较模式运行。 当双机比较系统出现故障时，启动自诊断程序进行故障定位。定位故障后， 切换开关将故障机器从系统中切除并换上处于正常工作状态的热备计算机。 系统继续以增强型双机比较系统运行。故障机器转入维修，维修好后作为热 备计算机。 输入 图2 - 9 带热备份的双机比较系统 不一致检测 西南交通大学硕士研究生学位论文第1 3 页 第3 章分布式容错系统 分布式系统与网络系统虽然都使用网络，但是两者具有不同的结构和工 作方式。网络系统按客户服务器方式工作，系统的客户部分和服务器部分各 自设置在不同的结点上，它是一种各个组成单元分布在网络结点上的集中式 系统。而分布式系统通常是按对等方式工作的，客户和服务器可以分处、也 可以共处在系统的任意结点。分布式系统有以下两个基本特征：( 1 ) 分离性， 即系统内有大量独立的、自治的和可以相互通信的处理机结点；( 2 ) 透明性， 即对用户和编程者来说，整个系统就如同一个单一处理机系统。透明性是分 布式系统最重要的特征，它极大地简化了应用软件的设计。 传统的容错设计大多依靠硬件冗余设计，要采用各种专用芯片、特殊的 电路和专门的实现手段，并投入大量的研究基金和开发时间。这使得成熟的 容错设计总是落后于现代技术的发展步伐，并且若设计不当，其系统性能会 远低于非容错系统。这使用户在选择系统时不得不在系统性能与容错要求之 间做出妥协。 随着微电子学技术的不断发展，芯片集成度迅速提高，价格持续下降， 部件的出错概率大大降低，这使得电路级与芯片级的硬件冗余的必要性大为 减弱。由于分布式系统的每个自治的节点形成独立的故障隔离区，它可以很 方便地实现节点级的冗余备份。因此，可以采用分布式操作系统，将分布与 冗余组合起来获得系统的容错能力，组成分布式容错系统。这种基于软件的 系统易于扩充容错能力和处理能力，且不必改变其结构，仅通过对构成节点 的计算机的升级就可提高系统性能，从而可以充分利用现代成熟的通用计算 机的计算能力，跟上更新换代的步伐。 3 1 分布式容错系统的基本技术 分布式计算机系统是相互通信的自治计算机结点的集合，计算机结点相 互合作完成一个共同的目标。在分布式计算机系统中实现容错，主要是在分 布式计算机系统的两个基本问题上起作用，即在通信子网和操作系统上发挥 作用。 通信子网络为分布式计算机系统提供高速、可靠且基于消息通信的互连 西南交通大学硕士研究生学位论文第1 4 页 结构。在计算机网络中，用于多处理机系统的互连开关网络，由于距离短( 通 常在一个机柜里) ，成本太高而不适于分布式系统。远程网络的拓扑结构不规 则，传输速率低且控制复杂，也不能用于分布式系统。局域网c l a n ) 具有 各种规则的拓扑结构。较为简单的传输协议，传输速率高和物理距离适中等 优点，为分布式系统提供了有效的支持。但作为高可靠的分布式容错系统的 予网络，必须采取冗余的l a n 网络及相应的可靠通信协议，才能保证整个系 统的可靠性。容错通信网络包括网络节点和通信链路，一般对节点和链路均 采用双冗余结构，一用一备，或是热备份工作。在任务执行过程中，若工作 网发生故障时自动从工作网切换到备份网。 分布式容错操作系统从全局的角度，以分散的方式管理系统的各种资源， 实现分布式容错计算，并提供与用户的接口。在分布式操作系统中，进程迁 移起着熏要的作用，它可以提高系统的负载平衡和实现容错、减少通信负载 等。其作用概括起束土婴体现在以下两个方面：提高系统的负载平衡。在特 定的时问内，各主机负载具有不确定性，会出现负载不平衡。这时通过进程 迁移彳能使主机实时地计算任务、实时地动态调度，使系统内部真正的实现 动念负载平衡和动态负载分担。实现高效率容错是它的第二大作用，在分布 式系容错系统中，当一个上机发生故障时，需要将该主机正在运行的进程迁 移到该节点的其它主机。i 耵肖某节点出现故障时，需要将在该节点的主机中 运行的进程迁移到其它正常工作的节点主机中。否则，如果故障主机正在运 行的是某些关键进程则有可能导致系统任务的错误运行后果将不堪设想。 进程迁移后，只有收集足够的状态信息才能重新启动进程，使进程得到 如同迁移之前的环境，冈此状态的获取就显得至关重要，它主要包括以下几 点： ( 1 ) 内存窀问。大量的状态都和进程的内存空间有关，如代码、数据； ( 2 ) 打开文件，包括打丌文件的内部标议，文件访问的位置及文件缓冲块； ( 3 ) 进程消息，如果操作系统是基于消息的，其状态包括接受和发送的缓冲 信息； ( 4 ) 执行状态，包括在进行上下文切换时有关的核心存储和恢复信息。如寄 存器的值； ( 5 ) 其它内核信息，操作系统存储进程的其它信息。如当前的工作目录、进 程i d 等。 进程迁移算法在目前主要有贪婪拷贝算法( e a g e rc o p y ) 、惰性拷贝算法 ( 1 a z yc o p y ) 和预拷贝算法( p i e c o p y ) 。这三种算法都是在源主机没有故障 西南交通大学硕士研究生学位论文第1 5 页 的情况下，将源进程挂起，从而使进程迁移得以完成。如果源主机发生故障， 迁移将不能得到进程的状态信息，而使系统失效。为了提高系统的可靠性， 必须采取定的措施。皋于检查点的迁移算法可以解决这一问题它可使其 减小时问歼销，并且在源辛机故障的情况下，依据检查点信息在新的主机中 重构进程，使其继续运 r 。在该算法中，何时设置检查点和如何设置检查点 是两个关键问题，f 面就这两个问题进行讨论，讨论完后给出基于检查点的 迁移算法的步骤。 检查点的设置必须满足实时响应故可以采用以下策略：即在对某一进 程进行检查点设置时，对与陔进程通信的进程同时设置捡查点，从而保持两 者数据的致性。进程问的通信都以消息队列、共享内存、信号、通道等方 式进行。例如对于消息队列方式的通信来说，可通过在消息队列中增加一个 标志位当进程修改消息队列时，就将标志位置l ，这样就很容易找到与之 通信的进程，并为之建立检奄点，实现数据的。致性。 对于何时设置榆查点有以卜两种策略：一个是在被控系统的一个控制 周期结束后保存，这样i u 减少检查点的个数，使目标主机尽快启动提高计 算机性能。另一个是在系统写调用后保存，这样将减少系统调用对检查点设 置的影响。同时，在每个页表中增加个标志位来检查最后1 次设置检奄点 后被修改的页在新榆企点设置后，只需更改被修改的页即可。 基r 检查点的算法的分两利一情况。 对于分前i 式容错系统叶i ，源辛机萨常 = = 作，利用进程迁移实现系统的动 态负载平衡的情况步骤如f ： ( 1 ) 源主机运行的州时。把最近榆企点中最少量的、必需的信息从源 主机传送到目标主机： ( 2 )如果有新的检查点建市，则转向( 1 ) ：否则执行下一步： ( 3 ) 状态信息在h 标上机上重构进程，然后挂起源主机上运行的进程， 传输被修改的“脏”页到目标主机； ( 4 ) 重新启动存目标主机上的新进程和源主机上的源进程： ( 5 ) 通过比较关键数据的策略比较源主机进程和目标主机进程是否 敛。如果不敛，源上机则转向( 1 ) 。否则传输其它信息，从源主 机的运行i f i 删除队列链表进程。 对于分布式容错系统中源主机节点有故障，利用进程迁移实现系统的 容错性能，提高系统可靠性的情况。则直接从检查点提取状态信息。在目标 主机中重构进程，从检奄点处继续运行。 西南交通大学硕士研究生学位论文第1 6 页 3 2 分布式容错系统节点的结构 分布式容错系统是将传统的分布式系统与典型的冗余结构相结合而形成 的系统容错方案，该方案既具有高的可靠性又能在系统中某个节点发生故障 时，由系统中其它正常节点顺利接替故障结点中的任务。在分布式系统上实 现容错，其优点是成本低，并且可根据用户需要和系统状态自动重构和调度 以达到系统容错的目的。根据系统的节点所采用的容错方式不同，人们研究 了五种分布式容错系统，即分布式双冗余、分布式( 2 1 ) 概念冗余、分布式 三冗余、分布式( 3 1 ) 概念冗余和分布式二冗余系统。 3 2 1 分布式双冗余系统 双冗余系统中每个节点均由两个机器按双冗余机制构成，并且由这种节 点按分布式机制构成系统。 系统的工作原理是：当一个节点收到任务时，该节点的两台机器同时运 行，分别运行两个不同的版本并进行比较，根据需要设置故障检测点，当在 系统的检测点处比较的结果相同时，系统继续运行。若比较结果不同则启动 另两版本，又不同则将任务转交给相邻的正常工作的节点进行处理。原来节 点中的两台机器则分别运行自诊断程序以发现故障机器。将故障机器转入修 理，修理好后继续投入节点运行。 3 2 2 分布式( 2 1 ) 概念冗余系统 分布式( 2 1 ) 概念冗余系统是在分布式双冗余的基础上另外增加n 个备 用机，如果某个结点中有一机器发生故障，则在备用机中选择一个正常工作 的机器取代故障机器以保持该节点能继续正常运行。 系统的工作原理是：当某一个节点收到任务时，该节点的两个机器同时 运行，分别执行两个不同版本并进行比较，不同时启动另两版本，又不同时 则采用外推法，选偏差小的一个机器和一个能正常工作的备用机组成新的节 点继续工作；若不能找到一个能正常工作的备用机则交系统调用其它节点继 续运行；偏差大的机器转诊断，属永久性故障的机器则转修理，修复后的机 西南交通大学硕士研究生学位论文 第1 7 页 器和属瞬时性故障的机器均按一定的算法复原；所有不完好的节点不再参加 新的系统调用，节点一旦恢复即参加系统调用。 3 2 3 分布式三冗余系统 分布式三冗余系统是指每个节点由三台机器构成。当一节点收到任务时， 该节点的三台机器按三中取二的模式进行表决或者采用s h a d o w 机制容错运 行。 系统的工作原理：采用三中取二模式时，三个机器执行不同的版本，结 果进行比较，若三个结果相同则继续往下执行：若只有两个结果相同则此后 执行两个不同的版本并进行比较；不同时启动另两版本，又不同则采用外推 法，选偏差小的结果交系统其它节点调用；三个机器的比较结果均不同时亦 采用外推法，选偏差小的结果交系统其它节点调用；所有被视为不能正常运 行的机器都转入诊断，属永久故障则转入修理；修复后的机器和属瞬时故障 的机器均恢复节点；所有不完好的节点均不再参加系统调用，节点一旦复原 即参加调用。 采用s h a d o w 机制时，一节点的两个机器执行两个不同的版本并进行比较， 第三个机器作为热备用机器；当比较结果不同时启动另两版本，又不同时则 采用外推法，选偏差小的结果与第三个热备份机器按两版本机制继续执行； 对偏差大或有错误的机器则转入诊断，属永久故障则转入修理，修复后的机 器和属瞬时故障的机器均恢复节点：所有不完好的节点均不再参加系统调用， 节点一旦复原即参加调用。 3 2 4 分布式( 3 1 ) 概念冗余系统 分布式( 3 1 ) 概念冗余系统是在分布式三冗余系统的基础上，外加n 个 备用机，如果某一节点有一个机器不能正常工作，则取一正常工作的备用机 替代故障机器以保持节点继续正常运行。每个节点的三台机器按三中取二的 模式进行表决或者采用s h a d o w 机制容错运行。 系统的工作原理是：采用三中取二模式时，节点的三个机器同时工作并 进行比较，若三个机器的比较结果相同则继续往下执行；仅两个机器的比较 结果相同则取一备用机和结果相同的两个机器组成新的节点继续工作；若不 西南交通大学硕士研究生学位论文第1 8 页 能找到一个能正常工作的的备用机则执行两个不同的版本并进行比较。不同 时启动另两版本，又不同时采用外推法，选偏差最小的结果交系统调用其它 节点继续执行；若三个机器的比较结果均不同时则采用外推法，选偏差最小 的一个机器和一正常工作的备用机按( 2 1 ) 概念继续执行；所有被视为不能 正常工作的机器转诊断，膳永久故障的机器转修理，修复后的机器和属瞬时 性错误的机器均按一定的锋法复原：所有不完好的节点不再参加新的系统调 用，节点一旦复原即参加系统调蒯。 采用s h a d o w 技术时，一节点的两个机器执行两个不同的版本并进行比较， 第三个机器作为热备份：当i 埘个工作机器的比较结果不同时启动另两个版本， 又不同时则采用外推法。选偏差小的一个机器与第三个热备份机器按两版本 机制继续执行：如无热器份机器兀j 用则从备用机器中选一机器取代；对热备 份机器的检测全系统统一由备用机完成：如果某一节点机是在调用备用机的 情况下亦只有一个机器i f 常工作，则请求分布式系统调用其它节点接替：所 有不完好的节点不再参加新的系统调用；所有被规为不能正常= 作的机器转 诊断，属永久故障的机器转修理修复后的机器和属瞬时性错误的机器均按 一定的算法复原；节点一h 复原即参加调用。 3 2 5 分布式二冗余系统 分靠式_ 冗余系统是指由两机构成分布式计算机并以此为节点再构成分 析j 式系统。 系统工作原理是：任务在系统内实 1 ：动念调度，旦某- 任务被调到某 一节点后又在节点内实行动态调度。一节点的两机器自j 互有对方的任务队列。 不完好的节点不参加系统调用。不能萨常工作的机器转诊断，属永久故障的 机器转修理。修复后的机器和属瞬时性错误的机器均按一定的算法复原。节 点旦复原即参加系统渊用。 3 3 分布式容错系统的评价问题 分布式容错系统的评价分为网络性能的评价与节点性能评价两部分。 在网络性能的评价中主要是对系统的平均响应时间即网络的忙闲程度和可靠 性进行分析。而对节点的性能评价中，主要是对其可靠性、丢失任务数和机 西南交通大学硕士研究生学位论文第1 9 页 器的利用率即吞吐力，机器比进行分析。 网络的平均响应时间一般是根据网络所采用的冗余结构来分析。网络的 可靠性分析是