（计算机应用技术专业论文）符合生存性的协同检查点技术研究与实现.pdf

摘要 摘要 大量实时系统作为安全关键实时系统的核心在运行着。在攻击、错误和失效 影响下，系统已经不能保持完整的正常工作能力，生存性研究的目的就是保存受 危害的信息，维护重要和关键服务。要对系统的生存性进行评估，必须首先定义 系统对同一要求提供不同形式的替换服务集，对关键服务和一般服务给予不同级 别的保护。其次对其提供的服务进行分析，量化服务的特征和可用性概率。 必须保证实时系统高度的可靠性和严格的时间确定性。实时调度算法与检查 点( c h e c k p o i n t ) 的结合是实现系统容错的重要支撑机制。利用检查点能缩短恢复过 程，提高可用性。通常检查点的实现，分为系统级和应用级，并各有其优点和缺 点。但大多数研究对系统的故障概率分布的假设不一定符合实际情况。 本文首先对生存性研究，实时容错调度算法，检查点技术研究的现状进行综 述。分析了系统级和用户级检查点的优点和缺点，介绍了结合两者优点的协同检 查点算法。然后对协同检查点进行了实时容错调度的研究，分析了检查点和任务 集的可调度性之间的约束条件，以符合生存性要求，帮助系统在不同性能情况下 选择适合的检查点策略。 最后在b l c r 基础上设计并实现了协同检查点系统。系统由系统级模块、用 户界面模块和系统性能监控预测模块构成，能根据当前性能和失效情况决定是否 执行协同检查点。在l i n u x 环境下进行了实验模拟。实验结果显示，协同检查点减 少了检查点的执行个数，但取得了和周期检查点类似的效果。因此减少了检查点 开销，提高了系统的实时容错能力。 关键词：生存性，实时系统，实时容错调度，协同检查点 a b s t r a c t a b s t r a c t m a n yr e a l t i m es y s t e m sa r er u n n i n ga st h ec o r eo fc r i t i c a ls a f e t ys y s t e m p u r p o s e o fs u r v i v a b i l i t yr e s e a r c hi st op r o t e c tt h ei m p o r t a n ti m f o r m a t i o na n de s s e n t i a ls e r v i c e s w h e ns y s t e mc a n to f f e rc o m p l e t es t a n d a r ds e r v i c e su n d e ra t t a c k s ，f a u l t so rf a i l u r e s t o e s t i m a t es y s t e ms u r v i v a b i l i t y , f i r s t , i tn e e d st od e f i n et h es p e c i f i c a t i o n so fa c c e p t a b l e s y s t e ms e r v i c e sw i t hm u l t i p l ea l t e r n a t ef o r m s ，t oo f f e rp m p e r l e v e lp r o t e c t i o nf o rc r i t i c a l a n dg e n e r a ls e r v i c e s s e c o n d ，t oa n a l y z et h es e r v i c e s ，q u a n t i f yt h es e r v i c ev a l u ea n d s e r v i c ep r o b a b i l i t y t h eh i 出d e p e n d a b i l i t ya n ds t r i c tt i m ec o n d i t i o no fr e a l - t i m es y s t e mm u s tb e g u a r a n t e e d f a u l tt o l e r a n c ei st y p i c a l l ya c h i e v e di nr e a l - t i m es y s t e m st h r o u g ha c o m b i n a t i o no fr e a l t i m es c h e d u l ea n dc h e c k p o i n tm e c h a n i s m c h e c k p o i n tc a nr e d u c e s t h et i m eo fr e c o v e r yp r o c e s st oi m p r o v es y s t e ma v a i l a b i l i t y t h et w om a i na p p r o a c h e s a r e s y s t e m l e v e la n du s e rl e v e l c h e c k p o i n tw h i c hb o t hh a v ea d v a n t a g e sa n d d i s a d v a n t a g e s b u tt h ef a i l u r ed i s t r i b u t i o n e sa s s u m e db ym o s to fr e s e a r c h e sa r en o tf i t f o rr e a l i s t i ce n v i r o n m e n t f i r s t ，t h i sd i s s e r t a t i o np r e s e n t st h ec u r r e n ts t a t es u r v e yo fs u r v i v a b i l i t yr e s e a r c h , f a u l t t o l e r a n tr e a l t i m es c h e d u l ea l g o r i t h ma n dc h e c k p o i n ti m p l e m e n t s t h e ni ta n a l y z e s a d v e n t a g e sa n dd i s a d v e n t a g e so fs y s t e ma n du s e rl e v e lc h e c k p o i n t , a n di n t r o d u c e st h e c o o p e r a t i v ec h e c k p o i n tw h i c hc o m b i n e st h ea d v e n t a g eo fc h e c k p o i n tb o t hl e v e l s e c o n d ， i tr e s e a r c h e st h er e a l t i m ef a u l t - t o l e r a n ts c h e d u l eb a s e do nc o o p e r a t i v ec h e c k p o i n t t o m e e ts u r v i v a b i l i t yd e m a n d s ，i ta n a l y z e st a s ks e tf e a s i b i l i t yc o n d i t i o nu n d e rc h e c k p o i n t f o rc h o o s i n gp r o p e rc h e c k p o i n ts t r a t e g yu n d e rd i f f e r e n ts y s t e mp e r f o r m a n c e t h i r d ，t h i sd i s s e r t a t i o nd e s i n g n e sa n di m p l e m e n t st h ec h e c k p o i n ts y s t e mb a s e do n b l c r t h es y s t e mi sc o m p o s e do fk e n e r lm o d u l e ，u s e rm o d u l e , a n dw a t c hp r e d i c t i o n m o d u l e i tc a l lc h o o s ec h e c k p o i n ts e t t i n gb a s e do ns y s t e mp e r f o m a n c ea n df a i l u r e i m f o m a t i o n a n dt h ee x p e r i m e n t a ls i m u l a t e di nl i n u xe n v i r o n m e n tp r e s e n t st h a te v e n d e l e a s i n g t h en u m b e ro fc h e c k p o i n t ， c o o p e r a t i v ec h e c k p o i n t c a n g e t s i m i l a r p e r f o r m a n c ec o m p a r et op e r i o d i cc h e c k p o i n t s oc o o p e r a t i v ec h e c k p o i n tr e d u c e s c h e c k p o i n tc o s ta n de n h a n c e ss y s t e mf a u l t t o l e r a n tc a p a b i l i t y i i a b s t r a c t k e yw o r d s ：s u r v i v a b i l i t y , r e a l t i m es y s t e m ，r e a l t i m ef a u l t t o l e r a n ts c h e d u l e ， c o o p e r a t i v ec h e c k p o i n t i i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：黎刚 日期：年月 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：一誉娜导师签名：么越 导师签名：垦21 1 = 日期：年 月 日 第一章引言 1 1 引言 第一章引言 大量的实时系统作为安全关键系统的核心在运行着。安全关键系统运行一旦 故障和失效，就有可能造成重大的财产损失，甚至人身伤害，导致灾难性的后果【i 】。 对于高可信系统的六个分支，可靠、可用、安全、机密、完整、可维护，已经有 很多研究。这些都是在检测和防止错误的思路上进行的。但是在现实中，大多数 情况下系统不可能检测到所有的错误和故障；保护措施不可能阻止所有的破坏和 失效；而同时关键设施又必须不问断地提供服务1 2 。因此，从分布式网络和信息系 统发展出的生存性研究就很有必要，其目的就是在受到外部攻击破坏和内部错误 故障失效已经影响系统运行情况以后，系统已经不能保持完整的正常工作能力， 应该如何限制损害程度，保存受危害的信息，维护重要和关键服务的策略。 自从1 9 9 3 年b a r n e s 等人提出了可生存性的概念【3 】以来，生存性研究有了一定 的成果。但目前生存性还没有形成统一的定义。e l l i s o n 定义【4 】：生存性是系统在遭 受攻击、故障等事件下还能实时提供基本服务的能力。不少学者基于e l l i s o n 的定 义，提出了信息系统的生存性定义，m o i t r a 认为生存性是系统能多大程度上抵抗 攻击以及被攻击后仍能提供一定程度的服务 5 1 ；h a 定义生存性为面对故障和入侵 等异常事件下，系统维持一系列基本服务的能力【6 】；w i l s o n 认为是在确定的故障等 事件下，系统仍能保持工作状态的能力【j 7 1 。 上述定义给出了信息系统生存性的定性概念，但都缺乏具体的性能指标用于 判定系统的生存性。j o h nc i c n i g h t 认为生存性是一个可度量的系统特征，并且强 调，对于同一种要求，应定义系统能提供不同形式的替换服务集，并对系统在某 种情况下每种服务的可用性做出概率评估。因此给出了一个六元组 s ，ed ，矿，l 日来刻画系统需满足的生存性规范【引。 但由这些定义来衡量一个系统的生存性，并由此指导构建系统生存性的技术， 还需要进行更多的研究。目前，并没有发展出新的符合生存性的技术，而是将容 错等技术向符合生存性方向进行改造。 实时系统必须具有高度的可靠性和严格的时间确定性【9 】。实时调度算法与时间 冗余的结合是实现系统容错的重要手段，即通过预留时间资源为容错操作提供保 电子科技大学硕士学位论文 证。如何在不影响系统容错能力的情况下，提高系统的资源利用率，是容错实时 调度算法的研究热点。 检查点( c h e c k p o i n t ) 机制是动态负载、进程迁移，容错等技术的关键支撑【l o 】【1 1 1 。 恢复必须建立在崩溃进程和环境信息部分已知的情况下，因此利用检查点保存这 些信息，有利于缩短失效或故障发生后的恢复过程，提高可用性。 通常检查点的实现，分为系统级和应用级，并各有其优点和缺点【1 0 】【1 1 】。对于 系统级检查点，能够实现在线算法，获取系统内核信息，对用户透明。缺点是没 有应用层的分析和参与，缺乏主动性和灵活性。对于应用级检查点，程序员对需 要保存哪些重要数据，何时程序状态最小等情况更加清楚，并且便于移植，在编 译阶段也可以优化其性能。 因此，如何按照生存性和实时性的要求，并结合系统级和应用级检查点的优 点，对检查点进行分析和改进，成为本文研究的目标。 1 2 研究现状 容错系统一般采用冗余来满足系统高可靠性的要求，冗余可以划分为时间冗 余和空间冗余两类。时间冗余是指出现故障时通过将程序回卷到一个无错的执行 点，采用同种方法或不同方法继续运行得到正确结果。空间冗余通常指由多个相 同组件并行执行，通过将各自执行结果比较或表决的方法来检测错误或者得到正 确结果。空间冗余代价大，成本高，主要应用于特殊领域。时间冗余不仅开销小， 而且行之有效。某些软件错误可通过时间冗余的方法来解决。时间冗余方法中最 常用的是进程检查点( c h e c k p o i n t i n g ) 方法1 1 1 | 。 进程检查点机制是在进程正常运行时周期性的设置检查点，把进程在运行时 的正确状态保存到稳定存储器中。如果在随后运行过程中发生故障，那么将进程 进行卷回恢复，从稳定存储器中读出前一个检查点时的正确状态，从该点继续执 行。这样就避免了由于故障而导致的程序从头重新执行，因而有效的减少了计算 的损失。设置检查点的时刻称为检查点时刻；保存进程状态的文件称为检查点文 件。 检查点机制能保存和恢复程序的运行状态，因此在许多领域都有重要应用： 1 进程迁移 目前大多数操作系统不能提供进程迁移功能，利用检查点可以保存进程在某 台机器上的运行状态，然后在其他机器上恢复进程的运行实现进程迁移。进程迁 2 第一章弓l 言 移能使机群负载平衡，从而提高计算速度和机群的利用率。 2 。容错 分布式系统的故障率随着系统机器数增加而增加，长时间运行的作业蓿在每 次出现故障雌都从头开始执行，该作业将很难被执行完毕。因此，剩用检查点可 以实现多枫系统容错，提高系统可用性。 3 卷回调试 在程序调试过程孛，剩震捡查点保存程瘩在多个时刻翡运行状态。当错误发 生时，把程序卷回到保存的某一时刻的状态重新往下运行，以再次产生相同的错 误来查找镂误发生条件鹣调试方法称隽卷圆调试。分布式程痔毫含较多躲不确定 成分，当发现运行错误重新运行程序查找错误原因时，同样的错谈很难再次出现。 利爝卷回调试在很大程度上提离错误苒次发生的概率。 进程检查点可 ：1 分别在操作系统级、用户缀或者应用程序级实现，谩各自有 其优缺点。u n i x 操作系统下的进程检查点实现技术已经得到了较多的研究，典型 蕊捡查点系统l i b e k p t ，c o n d o r ，v m a d u m p ，c r a k 帮b l c r 两个以v m a d u m p 秀 核心的检查点系统【l o 】。 一般翁检查点算法研究，都餐设其故障概攀分布丞数为指数爱数，不定与 实际情况吻合。或者因为分段函数或多个函数的叠加，而难以求得泊松过程的最 小闻隔时闻，增加了分析的难度。丽a d a mo l i n e r 在文献【1 2 】中提出系统和应用结台 的协同检查点( c o o p e r a t i v ec h e c k p o i n f i n g ) 设置方法，具有某些优点。一方面， 能根据实际运行情况下的不同故障概率分布，提供更准确和灵活的检查点服务。 另方面，憝否决检查点兹执行，那么就麓够主动韵根据运行情况，控制检查点 服务等级。 1 3 本文的主要工作 所以本文的工作为： 首先对生存性研究，实时容错调度算法，检查点技术研究的现状进行综述。 指爨了满是生存牲对于霰务的要求。分据了霜户级霜系统级检查点的优点和缺点， 介绍了结合两者优点的协同检查点算法，对协同检查点进行了实时容错调度的研 究，分褥了检查点帮任务集静可调度性之闻嚣约束条昝，戳符合生存牲要求，帮 助系统在不同性能情况下选择适合的检蠢点策略。 最后在b l c r 基础上设计并实现了协霹检查点系统，在l i n u x 环境下进行了实 3 逛子科技大学硕士学位论文 验模拟。实验结果显示，协同检查点减少了检查点的执行个数，但取得了和周期 检查点类似的效果。因此减少了检查点开销，提高了系统的实时容错能力。 重。4 论文结构 本文的结构为： 第盖章对对生存性研究的现状进行了介缮，归纳了生存性研究对检查点服务 的要求。对实时系统技术现状进行了综述，并着重介绍了提高实时系统生存性的 容错检查点技术。 第三章对检查点技术研究的现状进行综述，分析了用户级和系统级检查点的 优点和缺点，分析了结合应用级和系统级优点的协圊检查点算法，并对其进行了 实时容错调度的研究，考虑了检查点和任务集的可调度性之间的约束条件。 第朋章在分析协同检查点的基础上进行了系统模块设计，并总结了一些优化 技术。 第五章实现系统模块功能，特别对检查点的获取和恢复进程上下文信息的关 键技术，和系统执行和恢复的过程进行详细的介绍。并对实验模拟结果进行了分 析。 第六章对王作进行了总结，对未来的工作进行了展望。 4 第二章生存性与实露窑锩技术概述 第二章生存性与实时容错技术概述 本章将介绍生存性、容错与实时的基本概念及相互关系。2 1 节对生存性研究 进行概述。2 2 节主要论述实时系统基本概念和主要技术，着重介绍了提高实时系 统生存性的容错检查点技术。2 3 节介绍了失效分布对检查点容错技术的影响。 2 1 生存性研究溉述 目前，大量的实时系统作为安全关键系统的核心在运行着。安全关键系统运 行一旦故障和失效，就有可能造成重大的财产损失，甚至人身伤害，导致灾难性 的后果。 大型信息处理系统由于覆盖面大，以至于成为无边界信息系统。相对于有乔 系统能被统一标识，集中管理和控制，无边界系统没有完整、统一的安全策略， 在任意时刻连入系统的节点数量和节点属性都是动态变化和不可舞的，因此几乎 无法获得关于系统完整的、准确的信息。 对于信息安全经历了3 个阶段的发展【2 】。 第一代信息安全基于保护与隔离的思想，着重在存取控制，前提是假设能够 划分明确的网络边界并能够在边界上阻止非法入侵。然而，实际情况往往比设计 者和评估者怒象静还要复杂得多。诲多著名的安全协议和系统都被发现存在漏洞。 仅仅依靠保护与隔离技术是无法挡住所有攻击的。 于是第二代安全技术基本愚想是发现入侵及其造成的破坏，采取相应对策进 行修复或补救，称之为“信息保障技术 。信息保障包括了保护、检测、响应技 术并提供信息系统恢复能力，目的是保护和捍卫信息系统的可用性、完整性、真 实性、机密性以及不可否认性。但是，检测系统不否检测出所有的攻击，信息保 障中的恢复技术也不能达到完全满意的效果。 如果说第二代信息安全技术是基于检测和响应的，那第三代技术就是要增强 网络系统的免疫能力，被称做可生存技术。 在现实中，大多数情况下系统不可能捡测到所有的错误和故障；保护搪麓不 可能阻止所有的破坏和失效；而同时关键设施又必须不间断地提供服务。因此， 从分布式网络和信息系统发展逝的生存性研究就缀有必要，其基的就是在受到外 5 电子科技大学硕士学位论文 部攻击破坏和内部错误故障失效已经影响系统运行情况以后，系统已经不能保持 完整的正常工作能力，应该如何限制损害程度，保存受危害的信息，维护重要和 关键服务的策略。 基于以上的特点和技术发展的趋势，1 9 9 3 年由b a r n e s 等人提出生存性研究【3 】， 最初是针对大型信息系统和分布式网络领域。研究重点包括生存性的基本概念、 生存性体系结构、生存性系统模型、生存性系统分析与设计、生存性系统工程方 法和工具、生存性风险评估、生存性系统评价与测试等。生存性和安全性、容错 性、可靠性等既联系紧密又有所区别。可以吸收安全性、容错性、可靠性等技术 的设计思想，或者将具体的机制采用到生存性的设计中。 2 1 1 生存性定义 目前，国内外对可生存嵌入式系统的研究还处于起步阶段，对生存性还没有 形成统一的定义和标准。 e l l i s o n 给出了针对信息系统的生存性定义【4 】：生存性是系统在遭受攻击、故障 等事件下还能实时提供基本服务的能力。这个定义给出了信息系统生存性包含的 若干基本概念，如生存性涉及到的攻击等事件、基本服务以及实时性等。但其并 没有具体给出系统应该达到什么条件才算具有生存性，即没有给出具体的标准规 范来对现有信息系统进行生存性评测。 不少学者基于e l l i s o n 的定义，提出了信息系统的生存性定义，如m o i 仃a 认为生 存性是系统能多大程度上抵抗攻击以及被攻击后仍能提供一定程度的服纠5 】；j h a 定义生存性为面对故障和入侵等异常事件下，系统维持一系列基本服务的能力【6 1 ； w i l s o n 认为是在确定的故障等事件下，系统仍能保持工作状态的能力 7 】。 上述定义给出了信息系统生存性的定性概念，但都缺乏具体的性能指标用于 判定系统的生存性。而弗吉尼亚大学( u n i v e r s i t yo f v i r 百n i a ) 的k n i g h t 等人提出的 生存性定义，即生存性是指即使系统或运行环境受到破坏，但系统仍然具有在这 种运行环境下提供持续服务( 或者降级服务) 的能力【8 1 。 k n i g h t 认为生存性是一个可度量的系统特征，将生存性当作一个必须严格设计 的系统特性，通过定义一系列的生存性规范来判定系统的生存性【8 1 。生存性规范是 一个六元组 s ，己d ，乃乃p ) ，其中s 是规范集，即系统服务可接受形式的规 范集。腥服务值因子，即影响系统服务的因素以及这些因素可能取的值。d 是可 达环境状态，i p e 中所有因素的可实现的组合，也就是可存在的环境条件。陧相 6 第二章生存性与实时容镄技术概述 对服务值，即在各个可到达的环境状态下，从跏范集中顺序定义用户感知到的服 务傻。兰是有效的转换集，鄙所有可熊组合的一个s 怒坳子集。p 是服务概率。 在k n i g h t 构想的基础上进行扩展【1 3 】，生存性可以由个十元组来表示： e s u r v = 球，e ，s ，k ，z ，d ，五，b ，五 尺是用户对系统生存性的需求定义。它是一个非空有穷集，v ne r ，r i 是用户 的一种生存性需求定义。在不同的使用环境中，用户对系统的生存性需求不相同。 例如，当系统处在不同的温度，湿度，电磁干扰强度等使用环境中时，用户对系 统的响应时间，数据的精确性等要求就不同，对系统的生存性需求也就不相同。 霞此可以针对不同的使用环境来配置适合不同应用环境的生存性需求定义，使系 统的运行更符合当前使用的环境，降低系统的使用成本。 互是影噙系统生存性的环境变量：如温度、湿度、电磁干扰等。它是一个菲空 有穷集，ve fe e ，嘶是一种影响系统工作的环境变量。嵌入式系统所处的使用环 境不同，影响系统工作的环境变量也不同。嚣此必须针对各种不丽的应用环境定 义当前情况下可能影响系统运行的环境变量，这样才能根据这些不同的环境变量 和用户的生存性需要来决定系统必需完成的关键服务。 s 是系统提供给用户的所有种类任务的非空有穷集。v 两s ，蕊表示一类具有 相同功能的任务。s 是系统在所有使用情况中所提供的任务的并集，在每种应用环 境中出现的任务都是s 的子集。 k 是关键任务的非空有限集合，v 忽鄙，岛表示一类关键任务或几类关键任务 的集合。用户对系统生存性需求定义不同，受到的环境嚣素影镌不同，系统必须 提供的关键服务也就不同。它也体现了在不同的使用环境中，不同任务之间的优 先级。 五是冀，e 到爱的函数映射，即z ( ，；，e i ) ：r x e k ，其中r i 锹，e i e e 。五产生 式的含义为，在用户生存性需求r i 和系统使用环境e i 下，系统必须提供的关键任 务为鬈。爱既可以是个任务，也可以是一系列关键任务的菲空有穷集合。 d 是受到破坏的关键任务的集合，v 西d ，磊表示一类受到破坏的关键任务， 也可以表示一系列受到破塥的具有穗阕功能的关键任务的嚣空集合。 石是e ，k 到d 的函数映射，即正( 岛，k i ) ：e x k - - d ，其中e i 镪| j j f 趸。五产生 式的含义为，在使用环境昱下，系统提供的关键任务怒受环境变量e i 的影响而遭 到破坏。 丁是对受损的关键任务进行处理的一系列措施的集合，v t i 乃鑫表示一类功 7 电子科技大学硕士学位论文 能相同的处理措施。例如可以对遭到破坏的关键任务进行降级服务，冗余调度等。 b 是任务运行过程中的数据备份的集合，用于任务的数据恢复，vb i b ，b i 表示一个或一组数据。 石是d ，乃b 到k 的函数映射，即ac a , ，6 j ) ：d x t x b _ k ，其中盔印，向z 魏b 。居产生式的含义为，经过处理措旋白，利用备份数据岛，将关键任务恢复或 替换为其他相同功能的关键任务，使系统恢复提供关键服务。 总的来说，生存性技术目前的实施主要是综合各个领域现有的技术，主要有 安全技术、容错技术等等，但是生存性并不单纯等同于其中任何一项技术。生存 性与可用性，可靠性，防危性，既有联系又有区别。以下先列出可用性，可靠性， 防危性的概念【1 4 】【1 5 1 ，再对它们进行比较。 1 可用性( a v a i l a b i l i t y ) 可用性一般用a ( t ) 度量，表示系统在时刻t 可正常运行并交付期望服务的概 率。当f 趋于无穷大时，如果彳( f ) 的极限存在，则称该极限为系统的稳定可用度， 它表示期望系统可用来执行有用计算的时间。可用性通常用来度量可延迟或短暂 停止提供服务而不会导致系统发生严重后果的品质。 2 可靠性( r e l i a b i l i t y ) 可靠性一般用尺( f ) 度量，假设系统在时刻气时是正常的，可靠性则是指系统在 给定的环境及时间区间【t o ，t 内连续提供期望服务的条件概率。通常假设系统的失 效具有马尔科夫性。设单位时间内系统失效的概率为允，则可靠性r ( t ) 服从负指数 分布r ( f ) = e 。在工程实际中，通常用平均失效时间来表征系统的 加可靠性。平均失效时间定义为从时刻气到系统失效时，系统可持续运行时间的 期望值。 3 防危性( s a f e t y ) 一般用s ( f ) 度量，是指系统可继续提供正常功能或以不 破坏其它系统及危害人员生命安全的方式中断服务的概率。假设系统在时刻气时可 正常工作，防危性则是指系统在时间区间 t o ，t 内不发生灾难性事故的概率。在安 全关键实时系统中，未被检测到的错误是导致灾难性事故的主要原因。由于未被 检测到的错误具有马尔科夫性，设单位时间内出现未被检测到的错误的概率为f ， 则防危性s ( f ) 服从负指数分布s ( f ) = e 。在工程实际中，可从s ( f ) 中抽取一个反 映基本特征的简单参数平均危险失效时问，来表征系统的防危性。平均危险 失效时间定义为从时刻气到系统处于危险状态时，系统持续防危运行时间的期望 值。 可用性，可靠性，防危性，都是强调在错误，故障情况下仍能提供完整的正 第二章生存性与实时容错技术概述 常服务。生存性强调的是发生错误和故障已经影响系统运行情况以后，系统对其 抵抗、恢复及优雅降级提供重要或关键功能的能力。可靠性和生存性又有联系和 重合，也有微妙的区别。 可靠性关注于系统的所有失效，特别是发生频率较高的失效，且无论其危害 性的大小；而防危性和生存性则只关注于部分失效，特别是风险( r i s k ) 较大的失 效。 可靠性更强调运行的内部错误和故障。生存性因为开始是在信息和网络领域 发展，还关注外部的误操作和攻击。不仅研究如何在异常输入和应力环境条件下 保持正常工作能力，更进一步的考虑在不能保持完整的正常工作能力情况下，应 该如何限制损害程度，保存受危害的信息，维护或保存基本和重要服务的策略。 容错的定义强调的是在容错技术保证下可以忽略故障，即故障不会影响系统 运行，还能提供正常的标准的服务。容错的另一个定义表现为一些具体的技术和 机制，可以应用于可信性设计不同部分，实现可信性各部分的性质。容错既可以 应用于可靠性可用性，又可以应用于生存性。它更多体现的是系统的设计，而可 信和生存性体现的是系统运行的特征。 生存性是对可信性六项特征的补充，是可信性的一个分支。并且生存性除了 有容错的设计，还可以应用其他的技术来达到系统整体的生存特性。 不同于可靠性或可用性强调服务某一方面的特征，生存性更强调对系统整体 特征的度量。各种服务的特征都隐藏在对系统、环境和服务的抽象之下，用户只 关心系统提供的服务而不关心具体的细节，系统服务作为一个整体提供给用户。 另外，生存性更强调系统多样化的研究。生物系统的健壮性就是来源于系统的多 样性。一部分族群在遭遇灾害时，另一部分族群可能因为基因上的差异而能够存 活下来，从而保护了种族能够继续生存繁衍。虽然在系统中用开发不同版本实现 的方法来增强系统多样性以提高抵抗力的手段可能代价较为高昂，但是仍然应该 研究如何用简便易行的方案达到增强系统多样性的目的。 2 1 2 系统生存性分析 与传统的可信属性相比，生存性不仅容忍已定义好的常见的破坏的发生，还 容忍未知破坏的发生。生存性的核心是确保关键任务在受到破坏后能及时完成， 此外还关心破坏之后任务的恢复能力。而在系统的实际应用中，充满未知破坏因 素，不能预先定义所有种类的破坏。因而系统中没有一个组成部分是可以避免错 9 电子科技大学硕士学位论文 误、故障或失效的发生。为保障系统的可生存性，必须利用系统的每个组成部分 的配合来实现，即可生存性是全局性的，它不仅要依靠专门处理破坏的部件，还 要充分利用系统未遭破坏的资源，在它们的基础上来持续完成关键任务。具有可 生存性的系统必须满足四个关键属性【l6 j ： 1 抵抗破坏( r e s i s t a n c e ) ，即系统具有抵御来自内部和外部的破坏的能力； 2 识别破坏( r e c o g n i t i o n ) ，即系统具有检测破坏和评估损失的能力； 3 恢复服务( r e c o v e r y ) ，即系统受到破坏后及时维持和恢复关键任务，确保 关键任务按时完成的能力； 4 自适应和演化( a d a p t a t i o n ) ，即系统在已获取的破坏信息的基础上增强其可 生存性的能力。 这四个关键属性是通过相关策略来体现和保障的。满足这四个关键属性要求 的系统在遭到破坏后，会采取以下的措施逐层保障系统的可生存性，以上措施是 从系统整体体现出的反应。要实现这些保障措施，必须使系统各个组成部分提供 对整体可生存性的支持。它不是各部分提供的支持的简单叠加，而是通过各个部 分相互配合来实现的，即为保障系统生存性而采取的四层措施中，每一层都是在 各部分的相互配合下完成的。要确保系统受到破坏后能够迅速恢复，最基本的策 略是建立在冗余的基础上，采用各种备份措施来使受损系统迅速切换到后备软硬 件上。为应对自然灾害等导致的大面积故障，可以采用分布的方式配置备份设施。 因此利用检查点技术缩短恢复过程，是一种重要的生存性技术。 2 1 3 生存性对服务的要求 生存性描述中将服务划分为两种：关键服务和一般服务。在可生存系统中， 这两种服务被分别对待，享有不同的重要程度。因此在可生存操作系统中，第一 步需要做的就是能够分辨哪些为关键服务，哪些为一般服务。 在系统运行时，各种服务是以任务实例的形式出现在系统中并接被系统所管 理的。以下的讨论中，将对关键服务的运行实例用关键任务来表示，对一般服务 的运行实例用一般任务来表示。 显然，系统的生存性要求，使得关键任务和一般任务拥有不同的管理原则。 系统中的关键任务的重要性总是强于一般任务的重要性。 系统在运行过程中，会不断接收到关键任务或者一般任务。无论这些任务产 生的来源是什么，目的是什么，操作系统必须能够为它们提供合理的、区别对待 l o 第二章生存性与实时容错技术概述 的方式来处理每一个任务。这就使得操作系统需要在尽量保障关键任务按时、顺 利完成的基础上，还要尽量充分使用系统资源( 这里主要指处理器资源) 去完成 非关键的一般任务，从而能够提高系统的吞吐量。 在本文的可生存操作系统当中，对关键任务和一般任务最根本的区别对待， 在于为关键任务提供高于所有一般任务的优先权力被系统调用执行。在系统资源 总数有限的情况下，在某些情况下，可以利用一般任务占用系统的资源用以执行 关键任务，以保证关键任务能够顺利完成。也就是说，这里是以性能换取系统的 可信性，通过放弃执行一般任务，来为关键任务提供更高的可信性。 如前所述，k n i g h t 认为生存性是一个可度量的系统特征，并定义了六元组来 刻画系统的生存性规范【8 】。从中可以看出，要对系统的生存性进行评估，必须首先： 1 定义系统对同一要求提供不同形式的替换服务集，强调应区分安全关键功 能和一般功能，给予不同级别保护。 2 对其提供的服务进行分析，量化服务的特征和可用性概率。 因此，本文按照以上生存性对服务的要求对检查点进行了分析。 2 2 实时系统概述 2 2 1 实时系统特性 实时系统是一种特殊的计算机系统，其运算结果的正确性由输出值及其产生 时间共同决定，即用户要求实时系统在规定的时间范围内得出正确的运算结果。 实时操作系统是实时系统的核心部件。实时应用通过实时操作系统提供的标 准编程接口获得实时系统提供的各种服务。不同的服务由不同的模块实现，通过 函数接口实现相互调用，降低模块间的耦合程度。典型的实时操作系统包括 v x w o r k s 、p s o s 、s p r i n g 、m a r s 和c r t o s 等。 实时系统必须具备的特性有： 1 实时系统必须具有良好的时间确定性和可预测性【9 】。时间确定性保证实时 系统能够在规定的时间范围内获得正确的输出，可预测性保证实时系统在任何状 态下的行为是可知的，进而保证系统是可控的。实时系统的时间粒度较小，可以 保证系统具有更快的响应时间和更高的控制精度。实时任务资源竞争造成的优先 级反转是影响时间确定性的主要因素，优先级继承和优先级天花板是解决这一问 题的主要方法。 2 实时系统必须支持并发操作，以便在同一时段内处理不同的外部输入，控 电子科技大学硕士学位论文 制不同的外部设备。 3 实时系统必须具有高的可靠性，因为越来越多安全关键系统是以实时系统 为核心构建的。实时系统需要利用避错、容错等技术保证系统的可靠性。 尽管采用了诸如先进的软件设计方法、形式化验证和大规模的测试等手段， 仍然无法避免在软件设计阶段引入缺陷。同时实时系统的运行环境中同样不可避 免的存在缺陷。因此，必须利用容错技术，在出错后控制实时系统，使之恢复正 常状态，或避免灾害性事件的发生。不同的应用对实时系统的出错行为要求不同， 相应的出错行为的实现难度也不同，所列五种行为具有以下包含关系：继续运行3 软失效3 平稳降级3 错误导向安全3 错误导向停止。继续运行的实现难度最高， 而错误导向停止的实现则最为简单。 因此实时系统的生存性研究必须考虑实时系统的以上特性。特别是时间确定 性对实时任务的时限要求较高，而增加检查点机制会增加任务执行时间。因此要 考虑在检查点机制下怎样确保时间确定性。 2 2 2 实时系统生存性技术 导致系统失效的因素来自于系统生命周期的每个阶段，分布在系统的内部及 其运行环境中。若缺陷引发的错误不能被及时地处理，则有可能造成系统失效。 就是尽早发现和处理错误，将系统失效的概率尽可能地降低。针对不同类型的缺 陷和错误，系统应该采取不同的检测和处理手段【1 4 1 ，分为避错，容错，排错和预 测错误。 容错是一种通用的可用于生存性的保障机制，其目的是使系统在运行中出现 错误时能够继续提供标准或降级服务【1 4 1 。随着软件应用的飞速增长，以及硬件可 靠性的增长和硬件容错技术的成熟，软件错误已经成为影响系统可靠性的最主要 的因素。因此，软件容错能力成为决定计算机系统生存性的关键。 软件容错分单版本的容错技术和多版本的容错技术。单版本软件容错又可分 为异常处理、检查点和回卷恢复、数据变换三种。多版本软件容错可分为恢复块 容错策略和n 版本编程策略。 容错的基础是冗余，包括硬件冗余、软件冗余和时间冗余等。软件冗余指系 统中存在多个功能相同的软件模块，当其中部分模块出错时，其功能由其它模块 实现。时间冗余指系统预留空闲时间供错误处理和恢复操作使用。时间冗余对于 实时系统有着特殊的意义，如执行检查点则需要系统具有时间冗余。实际应用中， 几种冗余可以并存。冗余资源的数量决定系统的容错能力，称为冗余级别。 1 2 第二牵生存性与实时容错技术概透 容错技术可以大体从两方面考虑，一方面是关注系统某一部分的具体机制， 如检测，备份，恢复等。另一方面必须认识到，要构建一个符合生存性的操作系 统环境，不仅依赖予部分的机制，而且和操作系统本身构建的特征休戚相关。 因此以下分两部分介绍了容错技术。 2 2 2 1 软件容错技术 软件容错设计的主要方法有：信息容错、时闻容错及软件系统结构容错。悉 任何一种容错方法都包含错误检测、错误处理、错误恢复三个过程h 4 1 。 1 错误检测 错误检测是设计容错系统的关键。通常错误检测技术可分为并发性错误检测 和强制性错误检测两种。并发性错误检测指在服务交付的过程中进行检测，可进 一步缀分为复制、看门狗定时器、反尚、编码及可接受性等检测技术；强制性错 误检测则在任务被悬挂之后进行，它主要用于系统潜在错误及静止缺陷的检测， 可进一步缨分为故障诊断及结构佬检查。 错误检测用于发现系统中部件的运行进入非正常状态。错误检测的常用方法 包括运行时间检测、误码检测( 如循环冗余校验) 和比较算法( 两模块或多模块比较) 、 合理性捡测和结构检测等。通常，错误检测与系统功能在同一个结构中实现，形 成自检结构。自检结构形成错误限制区，即错误限制在本结构内，不能影响其他 部件的运行。 2 错误诊断 错误诊断焉于评价错误可熊造成的损失，或分析造成当蓠错误的原因。壹予 错误诊断十分复杂，开销很大，在线诊断往往得不偿失。因此，被检出的错误通 常被记录下来，供离线诊断和系统维护时使用。 2 错误恢复 错误恢复使系统由错误状态返回正常状态。错误恢复具有三种方式：后向恢 复、前商恢复和补偿。后向恢复将系统恢复到如错前的状态。后向恢复需要建立 检查点，即在系统运行到确定位置时保存系统状态信息，而系统在出错后返回距 盘罐点最近的检查点。前向恢复在系统出错后为系统装入一个满足正常运行要求 的新状态。补偿指直接用一个正确的部件代替出错部件。 后向恢复首先需要错误检澳l 的支持，其次需要建立一系列的检查点，丽检查 点数据必须被正确地存储和保护，以供系统恢复时使用。前向恢复需要错误诊断 的支持，因为只有在正确地分析当前状态后，才能为系统设定新的运行状态。后 邀子科技大学硕士学位论文 向恢复直接用正确的状态替换系统的错误状态，因此无需错误诊断。后向恢复和 前彝恢复可以同时使用。当系统邀错时，首先采焉后惫恢复，若错误依然存在， 则采用前向恢复。在前向恢复和后向恢复中，最大的问题是恢复机制的时间开销。 检查点机铺将在以下的章节详细讨论。 上述每种容错技术均具有多种不同的实现形式，其成本、效能各不相同。在 工程实际中，设计人员首先根据系统的应用领域、功能和性能需求、成本限制和 资源限制等诸多因素，确定系统的失效语义。然后，根据失效语义，多种合适的 可靠性保障手段相结合，处理在系统生命周期的不同阶段出现的缺陷和错误，保 障系统的可靠性。 2 2 2 2 系统级容错技术 徽魂核结构的实时操作系统采用c l i e n t s e r v e r 的概念，在操作系统核心代码 中仅实现任务管理、中断管理和进程通信管理等少数核心系统功能，其余系统功 麓分尉以服务器的方式实现，与实时应震起运行与操作系统之上。实黠应用采 用消息通信机制，通过微内核与服务器进行交互。与主流实时操作系统相比，微 内核实时操佟系统曩有更好的可靠性、防危健、灵活缝、可扩展性鞍可移植性， 对分布式实时计