（计算机应用技术专业论文）移动环境下低开销的非阻塞检查点策略的研究.pdf

哈尔滨工程大学硕士学位论文 摘要 近年来无线网络得到了爆炸性的发展。但与有线网络相比，无线网络中 系统出错的概率大大增加，网络入侵也更为隐蔽和多样，这对其可靠性问题 的解决提出了巨大挑战。因此，研究移动环境下的容错技术既具有理论意义 亦具有实用价值。 检查点恢复技术的容错是通过在无错执行期间周期性地保存进程的状态 来实现的。出错时进程就从保存的状态处重新开始执行，从丽减少出错带来 的计算上的损失。在分布式系统中设置检查点时，除了要考虑在单进程应用 程序中所存在的减少检查点开销，优化检查点时间间隔等问题外，还要考虑 分布式系统中由于进程之间相互发送消息而导致的进程状态间的相互依赖关 系。这是分布式系统中的检查点技术的难点。怎样保证形成全局一致性检查 点，避免多米诺效应，同时尽量减少由于引入检查点而带来的额外开销，是 分布式系统中的检查点协议所要考虑的主要问题。 由于移动环境下移动主枫的低无线频道带宽、频繁的断开连接，缺少可 靠存储等特性，使得传统检查点算法不能很好地适属于移动计算环境。针对 上述问题，本文提出了一耪高效的检查点算法来降低了协同开销。通过利用 通信向量，大量减少了参与到检查点算法中的进程数。在设置检查点过程期 间，该算法通过发送检查点请求给依赖的进程以节约用来描绘依赖树的时间。 另外，在该算法中进程是非阻塞的，并通过信息捎带技术解决了不一致问题， 因此可以避免不必要消息和孤儿消息。与传统的协同检查点算法相比，本文 提出的非阻塞检查点算法使得最小数圈的进程采取检查点，并且减少了检查 点的反应时间，给拥有有限资源的移动系统带来了较少的开销。 关键词：移动计算：容错；检查点；卷回恢复 啥尔滨工程大学硕七学能论文 _ i i i i i i ii i i i i ii ii i i i i i i _ a b s tr a c t w i r e l e s sn e t w o r k sa r eb e c o m i n ge x p l o s i v eg r o w t hr e c e n t l y 。u n f o r t u n a t e l y , s o l u t i o n st or e l i a b i l i t yo fw i r e l e s sn e t w o r ka r eg e t t i n gm o r ea n dm o r ed i f f i c u l t c o m p a r e dt of i x e dw i r e dn e t w o r k s s i n c et h ep r o b a b i l i t yo fs y s t e mf a i l u r e si s d r a m a t i c a l l yi n c r e a s i n gw h i l et h es o p h i s t i c a t i o nl e v e la n dk n o w l e d g et oc o n d u c t a t t a c k sh a v eb e e nd e c r e a s i n g c o n s e q u e n t l y , t h er e s e a r c ho ff a u l t - t o l e r a n c ei n m o b i l ec o m p u t i n ge n v i r o n m e n th a st h e o r e t i c a lc o n t r i b u t i o n sa sw e l la sp r a c t i c a l a p p l i c a t i o nf u t u r e f a u l tt o l e r a n c eo fr o l l b a c kr e c o v e r yi sa c h i e v e db yp e r i o d i c a l l yu s i n gs t a b l e s t o r a g et os a v et h es t a t e so fp r o c e s s e sd u r i n gf a i l u r e f r e ee x e c u t i o n t od e a l 、】l r i t ha f a i l u r e ，af a i l e dp r o c e s sr e s t a r t sf r o mo n eo fi t sf o r m e r s a v e ds t a t e s ，w h i c h t h e r e f o r er e d u c e st h ea m o u n to fl o s tc o m p u t a t i o n t h eo p t i m i z i n gs c h e m e ss u c h a sc h e c k p o i n t i n gc o s tr e d u c t i o n ，c h e c k p o i n t so p t i m a li n t e r v a ld i s c o v e r y , w h i c h a r ep r e s e n t e di nu n i p r o c e s s o r sc h e c k p o i n t i n gc a nb ea d o p t e di nt h ed i s t r i b u t e d c h e c k p o i n t i n gs c e n a r i o f u r t h e r m o r e ，d i s t r i b u t e ds y s t e m sc o m p l i c a t er o l l b a c k r e c o v e r y , s i n c et h a tt r a n s m i tm e s s a g e si n t r o d u c ei n t e r - p r o c e s sd e p e n d e n c i e s d u r i n g f a i l u r e f r e e o p e r a t i o n i t i sd e s i r a b l et or e d u c et h eo v e r h e a do f c h e c k p o i n t i n g ；a n da tt h es a m et i m e ，k e e pt h ed o m i n o e f f e c tf r e e d o mt oe n s u r e t h ec o n s i s t e n tg l o b a lc h e c k p o i n t s 。 w h e na p p l i e dt om o b i l ec o m p u t i n gs y s t e m s ，c h e c k p o i n tp r o t o c o l sf o r d i s t r i b u t e dc o m p u t i n gs y s t e m sw o u l df a c em a n yn e wc h a l l e n g e s ，s u c ha sl o w w i r e l e s sb a n d w i d t h ，f r e q u e n td i s c o n n e c t i o n sa n dl a c ko fs t a b l es t o r a g ea tm o b i l e h o s t s 。t h i st h e s i sp r o p o s e sa ne f f i c i e n tc h e c k p o i n tp r o t o c o lt oe f f e c t i v e l yr e d u c e t h ec o o r d i n a t i n go v e r h e a d b yu s i n gac o m m u n i c a t i o nv e c t o r , t h en u m b e ro f p r o c e s s e s t h a tp a r t i c i p a t ei nt h e c h e c k p o i n t i n g e v e n ti s r e d u c e d d u r i n g c h e c k p o i n t i n g ，t h ep r o p o s e ds c h e m ec a ns a v et h et i m ei nt r a c i n gt h ed e p e n d e n c y t r e eb ys e n d i n gc h e c k p o i n tr e q u e s t st od e p e n d e n tp r o c e s s e ss y n c h r o n o u s l y i n 吩尔滨工程大学硕士学位论文 a d d i t i o n , p r o c e s s e sa r en o n - b l o c k i n gi nt h i ss c h e m e ，s i n c et h ei n c o n s i s t e n c yi s r e s o l v e db yt h ep i g g y b a c kt e c h n i q u e 1 1 h i ss t r a t e g ya d d r e s s e st h ep r o b l e mo f u n n e c e s s a r y a n d o r p h a nm e s s a g e s 。c o m p a r e dt ot r a d i t i o n a lc o o r d i i n a t e d c h e c k p ) o i n ta p p r o a c h ，t h ep r o p o s e dn o n - - b l o c k i n ga l g o r i t h mm i n i m i z e st h en u m b e r o fp r o c e s s e st ot a k ec h e c k p l o i n t s ，a sw e l la sr e d u c i n gt h ec h e c k p o i n tl a t e n c y , w h i c hb r i n g sl e s so v e r h e a dt om o b i l es y s t e mw i i t hl i m i t e dr e s o u r c e s 。 k e y w o r d s ：m o b i l ec o m p u t i n g ；f a u l t - t o l e r a n c e ；c h e c k p , l o i n t ；r o l l b a c kr e c o v e r y 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ：嘞刍l 趸裔 哈尔滨下稃大学硕十学位论文 1 i 研究的目的及意义 第1 章绪论 移动计算设备和移动通信设备为今天的信息社会带来了革命性的变化， 使我们正从个人计算时代转向无处不在的计算时代。无线网络是互连无处不 在的设备的最直接的解决方案，近年得到了爆炸性地发展。未来的互联网络 将是由有线网络、基础结构移动网络( 移动i p 网络) 和非基础结构移动网络 ( 如移动色组网) 组成的集成穗络。僵与有线嬲络相比，移动网络中系统出 错的概率大大增加，网络入侵也更为隐蔽和多样，这对其可靠性问题的解决 提出了巨大挑战。解决可靠性阌题的基本途径一是避免错误发生，这可以通 过保护设计如硬件冗余、软件的广泛测试、数据备份来实现；二是系统容错。 解决安全性问题的基本途径一是加强系统自身的保护，如采用数据加密、身 份认证、安全路由等安全技术；二是进行入侵检测。由于错误是不可避免赡， 因此系统容错是解决可靠性问题的根本途径。本文以解决移动网络的可靠性 问题为叠标，研究移动环境下的容错技术。 移动网络作为分布式网络的一种形式具有低频道带宽、移动存储空间有 限、节点可移动、移动主机经常从网络中断开以及移动主机电池供给有限等 特性【l j 。在移动网络中，传统的容错技术存在效率低下或不适合笼线网络移 动特性的问题，因而需要研究移动环境下的新的高效容错技术，包括研究固 定网络分毒式系统下检查点技术，以高性能计算为誉标静移动环境下的检查 点恢复协议的研究。研究成果对移动网络在高性能计算领域的推广应用和提 供可靠的通信服务方面具有重要的理论和实际意义。 1 2 检查点的研究现状 容错系统一般采用冗余技术来满足系统高可靠性的要求，分为时间冗余 晗尔滨t 程大学硕士学位论文 和空间冗余两种溺。时闻冗余是指当系统蹬现故障时逶过将程序卷圈到无错 的执行点重新运行的方式。空闻冗余是指由多个相同组件并行执行，通过将 所有结果比较或者表决的方法来得到正确结果。两者相比，空间冗余成本高， 代价大，主要应用于特殊领域，因此时间冗余是最常用的回卷恢复技术。 检查点技术，也称为“网溯恢复，是软件容错的重要手段，其具体方法是 在程序运行的适当时刻设置检查点，保存程序执行状态，当故障发生后，相 关进程回溯到故障发生前的一致性状态，从保留信息中恢复程序执行状态， 从该检查点处重新执行，从而避免了系统在发生故障时由予从头开始执行而 弓| 起的计算时闻的大量重复浪费，提高了系统可用性1 4 1 。 在进程无锩执行时，检查点协议按一定的策略周期性地存储每个进程的 状态到稳定存储器中。稳定存储器可以保证即使在系统发生失效的前提下， 被保存的进程状态仍然不被破坏。这个被存储在稳定存储器中的进程的状态 被称作该进程的一个检查点( c h e c k p o i n t ) 。系统失效后，从上一个检查点状态 开始重新执行的过程称为卷回恢复。当一个进程失效时，创建一个新的进程 用来恢复失效的进程，这个新创建的进程被称作恢复进程。恢复进程的状态 取自失效进程存储的最后的检查点，这相当于进程卷回到最近的检查点，然 后从这个恢复状态继续执行。虽然这个过程对单一进程的应用是完全正确的， 但是对于有多个进程的分布式应用却会产生闯题：恢复进程继续执行后，全 局的系统状态可能不再是一致的。因此如何保证全局检查点的一致性，著且 在一致性的基础上降低检查点的开销，提高系统的性能一直是检查点恢复技 术研究的重点和难点。 根据检查点算法的使用范围可以把目前的回卷恢复协议分为两奖s 】：单 进程程序检查点算法以及分布式程序检查点算法。单进程程序检查点算法是 容错回卷技术的基础，舀前囡内外的研究己经比较成熟，并且己有一些产品 问世t 6 - 7 1 。随着分布式系统的推广，分布式系统审的检查点协议也逐渐成为了 研究的热点。嚣前国际上对容错圆卷技术的研究主要集中在u n i x 系统和 w i n d o w s 操作系统 s - 1 2 。其中对于u n i x 系统，这方面的研究已经比较成熟， 但是对于w i n d o w s 操作系统，相对来说还比较缺乏。由于w i n d o w s 操作系统 的广泛使用，尤其是基于w i n d o w sn t 的操作系统在个人用户p c 机和大型工 作站机群上的广泛应用，对于怎样在基于w i n d o w sn t 的操作系统上实现透明 2 晗尔滨t 稃大学硕士学能论文 _ l 皇黼葺i 冒黼i - i _ 鞘i i i _ 躺i i _ - _ _ l 一 的容错回卷也变得重要起来。在文献【8 】中张悠慧，汪东升等人对w i n d o w sn t 环境下的进程检查点设置与圈卷恢复进行了研究，在国内对这方面的研究也 逐渐增多，w i n n tc h e c k p o i n t 是正在研制开发的高可用性枫群计算环境的核 心，也是在机群环境下实现进程迁移和负载平衡的技术基础。 根据设置检查点与恢复机制的不同。检查点与恢复机制被分为两大类： 基于检查点的卷回恢复浅1 3 和基于日志的卷回恢复1 1 4 。基于检查点的恢复协议 又分为三类：非协同检查点协议m _ 1 9 、协同检查点协议 6 , 2 0 - 2 4 以及通信引发的检 查点协议 2 5 - 3 0 1 。非协同检查点协议允许每个进程独立设鬣检查点，不需要进 程之间的协同，一定程度上可以减少检查点的开销，毽缺点是有可能引起多 米诺效应( d o m i n oe f f e e t ) t 3 t j ：协同检查点协议，韶所有进程协同检查点设置完 成全局一致性状态，恢复时，所有进程都恢复到最近的一个检查点开始重新 运行，操作较简单，而且可以避免多米诺效应的发生：通信引发的检查点协 议，通过在计算消息中捎带协同信息来完成检查点，系统中生成两种检查点： 基本检查点与强迫检查点。这种方法不需要专门处理协同消息，并且可以避 免多米诺效应。基于日志的卷回恢复协议也分为三类：悲观日志协议1 3 2 - 3 3 1 ， 乐观品志协议i m - 3 5 1 和因果日志协议f 溯露。悲观日志协议中，每一个非确定性事 件的信息在影瞧到计算之前就被记入位子稳定存储器的霞志中，消息只有在 做了记录之后才分发给应用程序，每个进程同样要周期性的设置检查点，减 少错误恢复阶段重做的工作；乐观日志协议假设在发生错误之前，能够将接 收的消息保存到稳定存储器中。系统首先将日志保存在内存中，然后定期将 易失性日志刷新到稳定存贮器中。乐观日志协议不必阻塞基本应用的执行， 有更好的非失效性能；因果闷志协议把每一个与进程状态变化有先后因果关 系的事件记入日志中或者保证这些事件可以被当前的进程访问。该方法避免 了溺同步方式存取稳定存储器，具有乐观嗣志协议在非故障条件下的性能， 缺点是该协议过于复杂。 根据一个进程在做检查点时与其它进程的关系，协议又分为；同步检查 点协议和异步检查点协议。同步检查点协议有阻塞同步检查点协议和非阻塞 同步检查点协议之分。同步检查点算法也称全局一致的检查点算法。在程序 状态保存时，它协调程序各进程使其在合适的时刻做局部检查点，这时各进 程的检查点文件组成的集合就是一个一致的全局状态。同步算法的优点是每 哈尔溟下程大学硕士学彼论文 个程序进程只需保存最近时刻的检查点文件，空闯开销较小，且程序状态恢 复时没有“多米诺 效应。其缺点是应用糕序的运行受检查点操作影响较大； 异步检查点算法中，程序各进程周期性地相互独立地保存自己的运行状态和 记录所接收的消息，在程序状态恢复过程中，各进程之间则需要相互协调、 通过复杂的卷回算法各自卷回到合适的检查点时刻以使整个程序恢复到一个 一致的全局状态。异步检查点算法允许分布式程序进程拥有最大程度的自治 性。缺点是：一是由于每个程序进程需要保存若干时刻的检查点文件，空间 开销较大；二是在程序状态恢复过程中可能会重复卷回，最坏时出现“多米 诺 效应，使程| 事一直卷回到初始状态。 设置检查点的开销是影响系统性能的一个主要因素。程序在故障条件下 的运行开销有两个主要来源。一个来源是系统在设置每个检查点时都必须完 成保存程序状态的操作，所以不可避免地要引入一定的时间和空间开销。开 销的另一个主要来源是因故障而引起的卷回，因为每次卷回都会损失已经完 成的计算。减少设置检查点的开销，不仅可以直接减少为保存检查点而付出 的额外代价，还能够使系统适当增加检查点的数量，减少检查点之间的时间 闻隔。这样在发生故障时，可以减少卷回的工作量。所以检查点开销的大小 直接影响了系统的梭能。现行酌减少检查点开销的方法一是减少设置检查点 时要保存的数据，主要有增量式检查点设置、程序员指导的内存排除和检查 点压缩：二是隐藏设置检查点的时间，主要有检查点缓存和写时复制。 现代计算机与网络技术的发展，使检查点协议的瓶颈己经从网络传输变 为对稳态存储器的存储。由于采取协同检查点需要进程间的协同操作，将引 入大量的通信开销，而且任何一个进程提交输出之前都必须进行协同检查点 的设置，因此协同检查点算法生成检查点的费用比较大，但是它有很多优点， 例如算法简单，对存储空间要求少，不会产生卷回扩散，发生错误时，所有 进程都恢复到最近一个检查点重新开始运行，恢复操作十分简单等，因此入 们正在利用各静技术以降低生成协同检查点的费用，使该算法能更实用化。 协同检查点策略正在成为最主要的检查点手段嚣得到越来越多的关注。如何 实现最简捷容易、系统开销最小、恢复最简单的检查点算法一直是人们在该 领域追求的目标，也是本文的研究目标。 4 哈尔滨工程大学硕士学位论文 1 3 检查点恢复技术介绍 检查点恢复技术是把分布式系统看作一个应用程序进程的集合，这些进 程通过网络进行通信。移动分鑫式计算系统中，随着结点数的增加系统发生 错误的概搴也会大大增加。使用分布式计算的应用程序一般都是计算量大的 程序，若系统的平均无故障时间小于某一程序的执行时间并且程序在出现故 障后都从头开始执行，那该程序永远无法执行完。检查点恢复技术是指这些 进程在无错执行期间周期性地保存进程的状态，一旦发生错误，出错的进程 就从保存的状态处重新开始执行，从而减少了出错带来的损失。检查点恢复 技术在适当间隔对该程序做检查点操作，记录程序的中间运行状态，在故障 出现后程序回卷到最近的一次全局一致状态继续执行，以最大限度地减少因 出错带来的损失。检查点恢复技术的研究涉及以下几个方面的闯遂： ( 1 ) 检查点数摆的存储技术。检查点定期保存进程状态，包括处理器内 部描述符表、栈、静动态数据段、o s 的动态数据等，这需要较大的存储空 间和时间。有线网络常采用的技术是：增量式检查点嘲；c o p y o n w r i t e 技术 p g l ；d i s k l e s s 检查点。由于移动主机的低带宽、低电池容量、低存储器、频 繁的断开连接的特性，这些在有线网络成熟的检查点技术能不能直接应用于 移动计算环境，还有待进一步研究。 ( 2 ) 检查点对应用程序的透明性。它所关心的问题是用户的应用程序是 否可以不经过重新编译即可以运用于检查点系统以及是否方便移植。透明和 不透明的检查点各有优缺点，不透明的检查点需要程序员的参与儇移植性好， 而透明的检查点依赖于软件的版本。 ( 3 ) 检查点间隔的求解。系统周期性的做检查点，实际应用检查点时系 统都面临如何确定优化的检查点间隔的问题，如何比较采用不同的检查点机 制的系统性能的问题。检查点间隔的大小取决于错误率、系统的负载、检查 点开销、可靠性等级等因素，间隔的大小要适中，否则间隔过大或过小都会 降低系统性能。 ( 碡) 检查点时机和滚复机制。根据检查点保存的内容，检查点协议可 分为单一检查点协议和消息圜志检查点协议。对于单一检查点协议，这类协 5 哈尔滨工程大学硕士学静论文 黛置i 嗣誊置置眷篇宣暑i 笛麓置皇i i 篁墨宣暑一i 1 1 1 麓i i 薯皇一 议的共同缺陷是在卷回时需交换额外的同步消息。阻塞同步单一检查点协议 和菲阻塞同步单一检查点协议要求进程同步它们的检查点和恢复活动以达到 全局一致状态，固定支持站借助于高速网络和足够的固定存储器，可以运用 同步协议 ! 寻到全局一致性检查点。然丽，任何同步消息都不适合于移动环境 的低频道带宽、低能量、频繁断开连接、频繁的主机切换等特性。文献 3 9 4 0 1 介绍了一组基于移动计算的单一同步检查点协议。当检查点间隔结束时，由 一个进程充当发起者，只有那些在上一个检查点间隔直接或传递影响了发起 者的进程才需要作检查点。其目标是尽量减少需做检查点的进程数。异步单 一检查点协议中，各个进程周期性地独立执行检查点操作，但各移动站需保 留多个检查点在固定存储器上，这是不现实的。另外在恢复时，各个进程闻 相互通信来决定彼此是孬有因果联系，这需要多个进程的协调圆滚，带来了 大的恢复负载和延迟，而且有可能导致多米诺效应。丽消息日志检查点协议 可确保异步恢复，错误进程以外的其它进程不受影响。单一协调检查点设置 以及回卷恢复技术已经广泛地应用在很多基于有线网络的并行容错系统中， 比如慕尼黑理工大学信息学院的c o c h e c k ，俄勒冈科学技术研究院m i p s ， 威斯康星大学计算机系的c o n d o r ，清华大学的c h a r m 系统。但基于移动环 境的检查点技术尚未进入实用。我国学者在传统有线网络中的检查点技术研 究取得了一些进展，但对于移动环境中的检查点容错技术的研究还处于起步 阶段，本文将对这个问题进行深入的研究。 1 4 工作内容及论文结构 本课题来源于哈尔滨工程大学基础研究基金项目，移动计算网络的可靠 性恢复策略及其模拟评估研究。资助编号：h e u f p 0 5 0 2 0 。 本文的内容包括： 对霉前分布式系统检查点状况的研究：在现存的分布式系统检查点协议 中，对分布式系统进行检查点设置时在考虑减少检查点自身费用的同时，更 要考虑分布式系统不同进程间的一致性，保证分布式系统卷回重做的结果与 该系统无错执行的结果是一致的，保证分布式系统下的检查点设鼹不会产生 多米诺效应，也不会使系统出错时回滚到计算的起点。在保证系统正确性的 6 哈尔滨工稗大学硕七学位论文 前提下，如何减少检查点的设置费用，最大限度地提高计算机系统的性能， 是分布式系统中的检查点设避技术所要考虑的主要问题。分布式系统下蛉卷 回恢复协议分为三类：非协同检查点协议，协同检查点协议以及通讯引发的 检查点协议。本文主要介绍了协同检查点技术，为了防止多米诺效应的发生， 所有进程可以协同检查点的设置使这些检查点构成全局一致性状态。发生错 误时，所有进程都恢复到最近的一个检查点重新开始运行，恢复操作十分简 单，使进程协同设置检查点的直接方法是在设置检查点协议执行期间，阻塞 进程间的通信。通常使用两段阻塞协议完成检查点的协同操作但阻塞进程通 信会显著降低系统的性熊。因此采用毒# 阻塞豹协同检查点协议对必须保证部 分已设置的检查点的进程之间的通讯不影响全局检查点的一致性。另外可以 通过减少参与检查点进程的数目，减少协同消息的的数网来进一步降低协同 检查点的开销。协同检查点较菲协同检查点的优点是不会产生多米诺效应、 只需保存最近的一个检查点、生成检查点与卷回恢复简单，但其不足之处是 无错执行时生成检查点的费用太大，这将降低系统的整体性能。因此设计出 生成协同检查点时费用最小的算法，提高整个系统的性能是我们研究的晷标。 检查点技术在移动分布式系统的应用：移动分布式系统作为分布式系统 的一种特殊形式，固定网络环境下的成熟的检查点恢复技术不能直接应用， 因此在采取检查点时面临很多新问题，有限的频道带宽，频繁的断开连接， 有限的资源等，这使得采取低开销的检查点恢复技术对拥有有限资源麴移动 主机变得非常重要。由此，针对移动环境的新特性，利用信息捎带技术与通 信向量，本文提出了一种移动环境下低开销的非阻塞检态点策略。有效的降 低了系统的开销，提高了系统的性能。 本文章节内容安撵如下： 第1 章介绍了本文的研究目的及意义；检查点研究现状以及卷回恢复技 术；概括了作者研究低开销的检查点策略所做的工作以及论文结构。 第2 章分绍了分在式系统模型；一致性与可恢复全局状态理论及其判定定 理；分布式系统检查点协议及其策略：检查点协议的开销及性能评价标准。 第3 章介绍了移动分布式系统模型及其新特性；移动分布式系统检查点协 议的相关技术；在对现有算法进行分析研究基础土，指出现有算法存在的闻 题，针对该问题提出了一种综合利用通信向量和信息捎带技术的非阻塞低开 7 哈尔滨下程大学硕士学髂论文 销的检查点算法。 第4 章针对移动环境麴薪特性，新要求，对提出的一种适合予移动环境的 低开销的非阻塞的检查点算法进行了详细的描述。与现行检查点算法相比， 该算法能有效减少参与检查点的进程数以及协同消息数，具有低开销的特点。 第5 章对本文算法进行实验模拟与性能分析，通过理论与实验结果的双重 分析，进一步证明了该算法在降低移动系统开销方面的高效性。最后是本文 的结论以及对将来工作的展望。 8 哈尔滨下稃大学硕士学侮论文 第2 章分布式检查点算法概述 2 1 系统模型 一个分布式计算e h n 个进程的集合组成 p o ，p i ，p ，进程间只通过 交换消息来通信和同步。c i ，l 表示进程i 的第i 个检查点。假设任何一对进程之 间都通过可信的、直接的逻辑渠道相连，并存在不可预计的但是有限的延迟。 进程服从f a i l s t o p 的模式 4 1 1 。进程执行过程包含三种状态，分别是内部状态， 发送状态以及接收状态，分别对应有三种事件，即内部事件，发送事件以及 接收事件。进程在没有进行通信时执行予内部状态，检查点事件属予内部事 件。消息发送和接收事件分别发生在发送状态和接收状态，分别用s e n d ( m ) 和r e c e i v e ( m ) 来表示。同一个进程中两个相继的基本检查点之间的时间间隔称 为基本检查点间隔，用l 表示。每个进程存贮它的状态产生局部的检查点。进 程p i 的第k 个检查点被分配序号k ，并且表示为c i 。k 。存在于c i , k 1 与c i , k 之间的事 件被称作e i 洋，e i x 属于c i 。k 。第k 个检查点间隔表示在第k 与第( k + 1 ) 个检查点之 间的事件，包括第k 个检查点但不包括第( k + 1 ) 个检查点。消息传递会产生孤 儿消息，它是导致系统不一致的原因。 2 。2 检查点的一致性与可恢复全局状态 在分布式检查点协议中，一个进程的检查点保存的是该进程的一个局部 状态，所有参与分布式计算的进程的单个局部状态以及通信渠道状态的集合 构成了系统的一个全局状态。而分布式系统中的检查点算法，是力求保证全 局一致性检查点，即达到全局一致性状态【4 3 】。对于系统的某个全局状态，如 果组成该全局状态的任何一个进程的局部状态反映了己经接收到了条消 息，那么相应的，发送消息的进程的局部状态也反映了已经发送了该消息， 就称此全局状态为全局一致性系统状态。褥相应的组成此全局状态的，保存 9 哈尔滨t 程大学硕士学侮论文 _ i l l - - i _ 各个进程局部状态检查点的集合称为全局一致性检查点。 如图2 1 所忝，鳓，p l 和如表示分密式计算中的三个进程，从左到右的箭 头表示进程的执行过程，m l 和m 2 两个箭头表示进程间发送的消息，矩形a ， b ，c 表示进程的局部检查点，用虚线把这三个局部检查点连接起来表示这三 者构成的全局检查点。t 表示时间从左至右逐渐增加。图2 1 中局部检查点a 所保存的系统状态反映了消息m 1 己经由进程p o 发送，局部检查点b 没有反映 m l i j , 经由进程p l 接收，表示m l 仍在传送过程中，存在于通信子网上，我们称 之为在途消息。a ，b ，c 三个检查点可以构成全局一致性系统状态。相反，如 图2 2 所示表示的则是不一致的系统状态。 羚 p l p 2 图2 1 全局一致性状态 圈2 2 不一致状态情况 在图2 2 中，检查点c 反映了己经接受了消息m 2 ，但是检查点b 则没有反映 己经发送了m 2 ，这样两者状态之间就存在不一致。这种不一致状态会导致系 统出现无法预料的错误。这些局部检查点不能形成全局一致性检查点，因此 不能用来达到容错的旦的，当分布式计算出错藤，系统必须不断回卷，直到 找到全局一致性检查点，从丽形成全局一致性状态。但是在某些最坏的情况 下，系统一直找不到全局一致性检查点，所有进程就可能一直回卷到系统最 初执行的时刻，丢失之前所有的有效计算，这样检查点技术就失去了容错的 1 0 哈尔滨下程大学硕十学能论文 意义。这种情况称为分布式检查点按议中的多米诺效应。多米诺效应，就是 在分布式计算出错后，在寻找全局一致性检查点的过程中，出现的一种无限 割的，层叠的回卷现象。多米诺效应会导致系统丢失大量有效计算，使分布 式检查点技术失去容错的效果，是应该避免的。如图2 。3 所示，进程p 3 在故障 之后豳卷到检查点c 3 ，2 ，但c 3 ，2 与c 2 ，3 不致，迫使进程p 2 回卷到检查点c 2 。2 ， 但c 2 , 2 与e l ，3 不一致，迫使进程p l 回卷到检查点c l o 。进程p l 回卷到检查点c l o 后，c 3 ，2 与c l ，2 不一致，迫使进程p 3 回卷到检查点c 3 ，l 。递归下去，最后进程p l ， p 2 辜 h p 3 都回卷到最开始时的状态c i 。0 ，c 2 。0 和c 3 。所有的检查点都成了无耀检, o 查点。为了避免多米诺效应，保证全局一致性检查点的存在，国内外对此进 行了深入豹研究，提出了一套完整的理论 2 1 - 2 4 枞，1 。 c 1 ，0e l ，1c 1 。2c 1 ，3 图2 3 多米诺效应的例子 任何卷网恢复协议的基本目标就是当系统因失效丽导致系统状态不一致 时，使系统返回到个一致性状态。重新构造的系统一致性状态不一定就是 失效麓己发生的状态，也可以是在失效兹“可能发生的正确状态。任何一 个卷回恢复算法的基本目标都是将由于发生错误而导致不一致的系统带到一 致的状态。有两类系统消息会在进程发生错误时使系统产生不一致，它们分 别是在途消息与孤儿消息f 4 2 l 。 在途消息：系统中存在进程p i ，a j ，存在检查点对( c i ，x ，c j y ) ，消息m 是进 程焉发绘进程马的消息。如果发送m ( s e n d ( m ) ) 属于c i x ，两接收m ( d e l i v e r ( m ) ) 不属于c h ，则称m 为在途消息。 孤儿消息：系统中存在进程p i ，p j ，存在检查点对( c i ，x c i y ) ，消息m 是进 程p i 发给进程p j 的消息。如果接收m ( d e l i v e r ( m ) ) 属予岛y ，丽发送m ( s e n d ( m ) ) 不属予c i 朋刚称m 为孤儿消息。 虽然以上两种消息都会在进程发生错误时导致系统的不一致，但通过重 晗尔滨工程大学硕十学豫论文 i _ u l i ii il l r 1 i 一i i 一1 1 1 1 i 置毫篇苹i 暑皇一 敖记录的在途消息，可避免由于在途消息弓l 超的不一致，而孤儿消怠弓| 起的 系统不一致是无法消除的。孤儿消息对应于发送者还没有发出楣应的消息焉 接收者就已经接收到该消息，这在实际情况中是不可能发生的。 如图2 3 所示，虚线表示全局一致性检查点。孤儿消息m l ：当发送消息 的进程p o 回滚到消息的发送之前的一致性状态，而消息的接收进程p l 仍然记 载着该消息的接收事件。在途消息m 2 ：如果接收消息的进程p 2 回滚到消息的 接收之前的状态而发送进程p i 并未回滚到消息的发送之前的状态。 ：二竺率蜀= 二 m l 、一k p i 弋熏叫p k 陀 ，圣 - p 2 了7 廿 盖7 图2 3 孤儿消息与在途消息 一致性全局性检查点( c o n s i s t e n tg l o b a lc h e c k p o i n t ) 是指多个局部检查点 的集合，每个进程一个局部检查点，它们组成了一个全局检查点。如果全局 检查点中不存在孤歹乙消息，则称它为致的全局检查点。一致的全局检查点 也称为恢复线( r e c o v e r yl i n e ) ，当系统出错时，每个进程都恢复到一致的全局 检查点可以把系统带到一个以前的全局一致性状态。为了使损失的工作最小， 应选择最近的一致性全局检查点进行恢复。基于检查点的卷回恢复协议曾先 应确保在发生错误时系统能确定恢复线。全局状态s 是全局检查点g 与一组纪 录的关于g 的在途消息m c 的集合。如果m o 中包括关于g 的所有在途消息的内 容，则称m g 是一致的脚】。 2 3 全局检查点及一致性判定定理 全局一致检查点的重点在予“一致( c o n s i s t e n c y ) ”焉不是“全髑( g l o b a l ) 舻， 因为系统中所有进程的检查点文件及所保存的通信通道状态就构成该系统的 一个全局检查点，但是该全局检查点却未必一致。所谓全局一致检查点是指： 在全局检查点中，若某个进程的检查点文件显示其已接收到一条消息，则必 1 2 眙尔溟下稃大学硕士学位论文 有相瘦进程的检查点文件显示对该消息的发送。故障恢复必颓从一个全属一 致捡查点开始。n e t z e r 和x u 等对全局检查点的一致性进行了研究并提恕了 相应约判定定理澎l ，在弓| 入该定理前，首先介绍z i g z a g 路径的概念瀚。 当满足如下条件时，两个检查点c i x 和q ，y 之间存在个z i g z a g 路径i q ： ( 1 ) p i 在检查点c x 后发送消患m l ； ( 2 ) 若斌( l ( c s n j i ，则p l 要采取牦时检查点，否则系统可能 在以后的运行中产生不一致。称该临时检查点为计算检查点，它是由于发送 计算消息引起的一种临时检查点：永久检查点：当采取临时检查点的进程， 收到初始检查点进程发送的确认消息时，将临时检查点变为永久检查点，完 晗尔溟工程大学硕士学僚论文 i i i i i i i ii _ 麓i i 暑置宣嗣- | - _ _ _ 墨皇 成全局一致性状态。 本文算法的恢复策略：一个移动结点发生故障恢复时，相关移动支持站 可以检测到错误并将该错误通知检查点初始进程p i ，并在广播消息中附带上 该移动结点的检查点序号。进程p i 依据保留的通讯向量v i 通知那些相应的条 目驴1 的进程p i 回卷到最近的一致恢复线。该恢复策略保证恢复到一致的系 统状态。 3 7 本章小结 本章在对移动分布式系统模型及其薪特性研究的基础上，着重介绍了适 合于移动计算环境的检查点算法及其相关的信息捎带技术。并对现有利用通 讯向量的非阻塞的检查点策略进行了分析研究，在此基础上提出了现存算法 存在的问题。 略尔滨工程大学硕十学位论文 第4 章移动环境下低开销非阻塞的检查点算法 4 。 引言 为了适应移动计算低带宽，储存空间限制，能量限制等不同于固定网络 分糍式系统地新特性，人们开始研究了大鬟适用于移动计算特点躺算法 2 2 , 2 4 a i , 4 4 , 5 7 - 6 0 。本章提懑一种移动环境下低开销的菲阻塞检查点( l o w - o v e r h e a d n o n - b l o c k i n gc h e c k p o i n t i n gs c h e m ef o rm o b i l ec o m p u t i n gs y s t e m s ) 算法，简 称l n c s m 算法，有效的降低了移动主枫的协同费震和参与检查点鹩进程数 西。通过剩用相关支持站的遴信向量，只有少量兹进程参与了检查点事件。 利褥消息捎带技术，可以有效避免孤儿消息和不必要的检燕点。霸此该算法 有效的降低了拥有有限资源的移动系统熬开销。 4 。2 系统模型 缓设一系列的主枧运行一个分布式应鞴程序，该程序有连续的檬有 p l ，阮。欺的n 个协同进程运行在潮络中的移动主机上。每一个移动主规 都有有限的存储。进程之间进行通信的唯一方式是进行消息传递。每个进程 把髑部的状态存储在稳态存储器中来产生局部检查点，稍爝检查点的副本被 传送到相关的移动支持站。一个进程采取的每一令检查赢都分配一个唯一的 检整点序号( c s n ) 。进程敬的第i 个检查点的序列号必l ，并虽记必c k 。, i 在第k 个检查点和第k 1 个检畿点之间的所有计算称为一个进程的第k 个检 查点闯隔。包括第k 个捡查点，但不毫括第黔1 个检查点1 + 2 1 。 假设只有移动主枫会壶于些锩误丽失效，著显耀关蛉支持站霹以检测 到这次的失效。在该检查点算法中，我们用到三种类型的检查点，即临时检 查点，计算检查点以及永久检查点。两种类型的消息，计算消息和系统消患。 哈尔滨t 稗大学硕士学位论文 瞄黼 7 1 1 1 1 1i i i i i i i i 1 7 1 1 1 1 1 颦i - 4 。3l n c s m 算法 4 3 ，1 算法基本思想 在该算法中，假定在检查点执行袈闻一个进程不会收到积另令检查点 初始者相关的检查点请求。每个进程只有一个检查点存储在移动主机的稳态 存储器中，并且检查点的一个副本也提交给其耀关的移动支持站中。进程聂 的糖关支持站跚s s ) 中保存一个相应的通讯懿量m t 辑，长度为n 。t n t 颤= 玢，屹加 代表进程玟直接鳃依赖关系。条嚣玢，翡蘧为l ，当盈枝强自从 上次全局一致检查点结束后，进程p l 发送过消息给进程p i 。而向量砟代表 进程p i 壹接和阗接的侬赖关系。当进程p i 初始化个检查点麴时候，进程 砖相关的移动支持站与扁量t n t 绥中条露忙l 熬进程p 相关的支持站一起更 改向量v , = m tk ut n t 巧。同时，向量t n th ，t n t 立即清零。在当前的检查 点阉隔蠹，向量以蒋根据向量t n t 辑，t n tv j 的变优及时更新。这种方法可 以有效缝解决拖沓消息，这稀消息可麓孳| 入新的依赖关系。 在该算法中，使用了三种类型的检查点；临时检查点，计算检查点，永 久检凌点。初始卷依赖的进程应该采取临时检查点。计算检查点用来避免孤 歹毛消息的产生。个采取计算检查点的进程不将它麴依赖关系提交给检查点 襁始