（计算机应用技术专业论文）基于检查点的进程迁移技术在pvm系统中的实现.pdf

北京交通大学硕士学位论文 摘要 对科学计算处理能力的不断追求以及分布式信息系统的巨大发展， 使得 通过集群进行分布式计算成为一种极具吸引力的计算模式。广泛的研究表 明， 工作站 3 3 % 到 7 8 % 的时间是处于空闲的，因 此为了构建高性能的 集群 就必须为系统提供负载平衡机制。 通常情况下采用集群计算的都是运行时间 长的应用程序， 为了使这些程序在系统崩溃时不丢失以 前的运行结果而在一 组新的工作站上自动恢复， 系统必须提供容错技术。 所以， 要建造高性能的 集群系统， 负载平衡和系统容错是必需的。 本文正是从这种需求出发， 对于 实现负载平衡和系统容错的关键技术进程迁移进行了 研究， 并在并行环 境p v m系统中实现了基于检查点的进程迁移。 本论文的工作主要包括以下 几个方面: 1 .简要介绍了集群系统及集群中的负载平衡与容错管理，并分析 了它们与进程迁移的关系从而说明了 研究进程迁移的必要性。 然后提出论文的主要任务，并简要介绍了国内外在这方面的发 展现状。 2 ，对目前的检查点算法进行了概括、总结和分类。进而对各种算 法进行了详细的描述与分析，比较其优缺点，提出了一些改进 方法。然后讨论了 集群系统中的基于检查点的进程迁移机制。 3 .阅读p v m系统的源代码， 并对其内核进行了分析。 深入讨论了 其实现机制中的一些重要的数据结构、 关键技术等。 特别对p v m 系统的消息传递机制进行了详细的分析与讨论。 4 详细地阐述了l i n u x 操作系统中进程的内存映象及上下文状态。 分析了实现进程检查点与映象恢复的关键问题及解决方法。 5 .首先分析了在p v m中实现基于检查点的进程迁移需要解决的一 些问题，之后提出本文对这些问题的解决方案 了进程迁移算法的设计思想与具体的实现过程 足之处进行了分析，提出改进的方法， 。然后详细阐述 ，并对其中的不 并对后续工作进行展望 关键词: 隽 群 pv人弓 进程迁移 进程映像 检查点 恢复 负载平衡容错 来经作浇、 今加io l 备 勿全文公 i : 北京交通大学硕士学位论文 abstract wi t h c o n t in u a l l y p u r s u i n g t h e p e r f o r m a n c e o f d e a l i n g w i t h s c i e n t i f i c c o m p u t in g a n d t h e d e v e l o p m e n t o f d i s t r i b u t e d i n f o r m a t i o n s y s t e m , c l u s t e r c o m p u t i n g h a s b e c o m e a v e r y a t t r a c t iv e c o m p u t i n g m o d e . c o m p r e h e n s i v e r e s e a r c h i n d i c a t e s t h a t a b o u t 3 3 p e r c e n t t o 7 8 p e r c e n t o f w o r k s t a t i o n s a r e i d l e . t h e r e f o r e , i n o r d e r t o c o n s t r u c t c l u s t e r s y s t e m w i t h h i g h p e r f o r m a n c e , i t i s n e c e s s a r y t o p r o v i d e l o a d b a l a n c e . t h e a p p l i c a t i o n s t h a t r u n o n c l u s t e r s a l w a y s a r e p r o g r a m s w i t h l o n g r u n t i m e . f o r t h e s e a p p l i c a t i o n s , f a u l t - t o l e r a n c e i s a b s o l u t e l y n e c e s s a ry . f a u l t - t o l e r a n c e e n s u r e s t h a t p r o c e s s e s c a n k e e p t h e i r r e s u l t s a n d r e c o v e r a t a n e w s e t o f w o r k s t a t i o n s a u t o m a t i c a l l y w h e n s y s t e m i s b r o k e n d o w n . f o r t h e s e p u r p o s e s , i h a v e s t u d i e d t h e p r o c e s s m i g r a t i o n t h a t i s t h e s i g n i f i c a n t t e c h n o l o g y o f l o a d b a l a n c e a n d s y s t e m f a u l t - t o l e r a n c e . f u rt h e r m o r e , p r o c e s s m i g r a t i o n b a s e d c h e c 助o i n t h a s b e e n r e a l i z e d i n p v m t h a t i s a p a r a l l e l e n v i r o n me n t . t h e c o n t r i b u t i o n s o f t h i s d i s s e rt a t i o n a r e a s f o l l o ws : 1 . i n t r o d u c e s c l u s t e r , l o a d b a l a n c e a n d f a u l t - t o l e r a n c e m a n a g e m e n t i n t h e c l u s t e r , a n a l y s e s t h e r e l a t i o n o f p r o c e s s m i g r a t i o n , l o a d b a l a n c e a n d f a u l t - t o l e r a n c e , th e n b r i n g s f o r w a r d t h e p r i m a r y t a s k o f t h i s a r ti c l e , a n d e x p l a i n s t h e s t a t u s q u o i n c h i n a a n d f o r e i g n c o u n t r i e s . 2 . g e n e r a l i z e s a n d c l a s s i fi e s t h e a l g o r i t h m s o f c h e c k p o i n t . e v e ry a l g o r i t h m i s d e s c r i b e d a n d a n a l y z e d i n d e t a i l . c o m p a r i n g e a c h a l g o r i t h m , t h i s a rt i c l e a n a l y z e s t h e i r a d v a n t a g e s a n d d i s a d v a n t a g e s a n d b r i n g s f o r w a r d s o m e m e t h o d s t o i m p r o v e p e r f o n m a n c e . t h e n d e s c r i b e s t h e m e c h a n i s m o f p r o c e s s m i g r a t i o n b a s e d o n c h e c k p o i n t i n t h e c l u s t e r . 3 . a n a l y z e s t h e s o u r c e c o d e o f p v m s y s t e m a t i c a l l y a n d d i s c u s s i t s i m p o rt a n t d a t a s t r u c t u r e a n d s i g n i f i c a n t t e c h n o l o g y i n t e n s i v e l y . e s p e c i a l ly , th i s a r ti c l e a n a l y z e s t h e m e c h a n i s m o f m e s s a g e p a s s i n g i n p v m d e e p l y . 4 . d e s c r ib e s t h e m e m o r y i m a g e o f a p r o c e s s in l i n u x o s , a n d a n a l y s e s h o w t o m a k e c h e c k p o i n t f o r a p r o c e s s a n d h o w t o r e c o v e r t h e i m a g e o f a p r o c e s s . f u rt h e r m o r e , t h i s a r ti c l e s u mm a r i z e s t h e p i v o t a l t e c h n i q u e s 5 . t h e m a i n c o n t e n t i s t h e d e s ig n i n g a n d r e a l i z i n g p r o c e s s m i g r a t i o n . t h i s a r t i c l e a n a l y z e s t h e d i ffic u l t y i n r e a l i z i n g th e p r o c e s s m i g r a t i o n i n p v m a n d r e s o l v e s t h e s e p r o b l e m s . t h e n d e s c r i b e s t h e a l g o r i t h m o f / 北京交通大学硕士学位论文 p r o c e s s m i g r a t i o n i n d e t a i l a n d r e a l i z e s i t . f u r t h e r m o r e t h i s a r t i c l e a n a l y z e s t h e d i s a d v a n t a g e s o f t h i s a l g o r i t h m a n d b r in g s f o r w a r d t h e a m e n d i n g me t h o d s k e y w o r d s c l u s t e r p r o c e s s m i g r a t i o n i n t l o a d b a l a n c e f a u l t - t o l e r a n c epvm c h e c k p o i m a g e o f ap r oc e s sr e c o v e r y m 北京交通大学硕士学位论文 第一章 引言 ， . ，概述 1 . 1 . 1论文背景 对科学计算处理能力的不断追求以及分布式信息系统的巨大发展， 使得 通过集群进行分布式计算已经成为一种极具吸引力的计算模式。 广泛的研究 工作表明，工作站的 3 3 %到 7 8 %的时间是处于空闲的，而处理机则在 9 3 % 的时间都是空闲的。 因此， 为了提供高性能的计算系统就必须为程序提供一 个有效的分配机制。 两个负载共享策略可应用于处理系统的动态变化: 一是 动态放置， 它可以根据当前系统状态来分配程序; 另一个是进程迁移， 它能 够根据系统和应用程序的发展变化来对进程进行移动。 尽管进程分配有诸多优点， 但只有为数不多的几个系统实现了负载平衡 策略， 并且大多数提出的算法都只是使用模拟结果来指出其不足之处 在这 些系统当中， 进程最初是根据有多重标准的放置算法来放置到一组工作站上 的， 这些算法将主机的负载和用户的行为考虑在内。 并且这些算法使用了系 统状态监控机制和应用程序执行管理机制。 基于此， 分配策略可以提高应用 程序的响应时间， 并有效利用分布系统的计算资源。 迁移能够将进程从一个 工作站移到另一个工作站， 它一般处理三种情况: 用户在做了一个最初的放 置决定之后要回到自己的工作站， 一个主机负载变重而系统中还有其它的轻 载主机，执行较快的主机轻载而执行较慢的主机重载。 当今采用集群模式的应用类型很多，包括客户端/ 服务器系统、事务处 理、 www、 科学计算等等。 而集群随着规模的不断扩大， 它在计算过程中发 生故障的 几率也会呈指数增长， 同时由 于集群通常为多用户使用， 节点 等资源 在某一时刻可用， 而另一时刻则可能不再可用， 具有较大的可变特性。 系统在 发生异常事件时会导致本次并行计算的彻底失败。 另外这些应用程序执行时 间都很长， 在执行期间系统很容易发生故障， 如果不进行容错管理， 集群系 统的计算潜能是不能完全发挥的。 当出 现硬件故障或者某个处理器被重新启 动、关闭或与网络失去连接时，执行了很多小时的应用程序可能就会丢失。 这就需要并行程序设计者掌握有关容错的专门技术。 为了使应用程序设计者 避免这样的设计困难， 系统必须提供容错功能， 使得因系统崩溃而受影响的 进程能在一组新的工作站上 日动恢复。 北京交通大学硕士学位论文 由以上的分析可知，要实现高性能的集群计算，必须考虑系统的负载 平衡和容错性能，而进程迁移技术则是实现负载平衡和系统容错的关键技 术。本文正是在这样的背景下展开研究的。 1 . 1 . 2集群系统 集群是一个正在发展中的并行计算机类型， 它的定义和分类还不很统 一 。 根 据p f i s t e r - 的 定 义 ， 集群 是并 行 或分 布 计 算 机系 统的 一 种 类型它 是 由一组完整的计算机互连而成的， 应能作为一个单独的统一计算资源来使 用。也就是，集群是一群以网络技术连接起来的工作站或p c 机的组合。这 种系统将一群工作站用某种结构的网络互连起来，充分利用各工作站的资 源， 统一调度， 协调处理，以实现高效计算。 计算机节点可以是一个单处理 器或者多处理器的系统，拥有内存、f o设备和操作系统。典型的集群系统 的结构如图 1 . 1 所示。 并行程序 并行编程环境 ( p v m, mp i , j a v a ) 串行应用 集群中间层 ( 单一系统映像和可用性低层结构) 操作 系统 操作 系统 操作 系统 操作 系统 操作 系统 节点节点节点节点 图 1 . 1集群系统的体系结构 集群的研究、开发和应用已经引起很大的重视， 几乎所有的计算机生产 厂商 都 宣 称 它 们已 推出 集 群产品 ，像 i b m 的s p 2 和 h a c m p ,c o m p a q的 h im a l a y a和 t r u c l u s t e r ,s g i 的 p o w e r c h a l l e n g e a r r a y , s u n的 s o l a r i s m c和 s p a r c c l u s t e :等等， 都被列为集群的商业产品。集群有时称为工作站集群 c o w( c l u s t e r o f w o r k s t a t i o n ) , i作站网 络n o w( n e t w o r k o f w o r k s t a t i o n s ) 或者 计算机集群( c l u s t e r o f c o m p u t e r s ) 。集群在我国也有译作群集或机群的 ， 它已 成为发展可扩放并行计算机的一个新的热点。 与其它并行系统相比， 集群在 实用上具有一些明显的优点: 1 .投资风险小: 用户在购置传统巨型机或mp p系统时， 总是担心使用效率 不高和性能发挥得不好，如果购置后在一定程度上确实出现此问题，就 相当于搁置或者浪费了大批资金，但集群不存在此问题，因为即使集群 北京交通大学硕士学位论文 在技术上不够先进 金; 但每台高性能的工作站仍可照旧使用，不会浪费资 2 .编程方便: 用户无需学用新的并行程序设计语言 ( 如并行c 、 并行c + + , 并行f o r t r a n 等) ， 只要利用所提供的并行程序设计环境， 在常规c , c + + 和f o r tr a n 等程序中相应的地方插入少量的几条原语， 即可使这些程序在 集群上运行， 这一点是最受用户欢迎的; 3 . 系统结构灵活:用户将不同性能的工作站使用不同的体系结构和各种互 连网络构成同构或者异构的工作站集群系统，从而可弥补单一体系结构 适应面窄的弱点，可更充分地满足各类应用要求; 4 . 性能/ 价格比高: 一般一台巨 型机或mp p 都很昂贵 ( 费用常以几百万元， 几千万元计、 ， 而一台高性能工作站相对便宜 费用仅以几万元或十几万 元计、 ，一个集群系统从浮点运算能力来看，虽然每台工作站只有几 m fl o p s 到几 十m fl o p s ， 但一 群工作站的总 体 运算性能 可高 达g fl o p s 的 量 级，能接近一些巨型机的性能，但价格却低了很多: 5 .能充分利用分散的计算资源:当个人工作站处于空闲时， 集群可在空闲 时间内 给这些工作站加载并行计算任务，从而工作站资源可得到充分利 用; 6 . 可扩放性好: 用户可根据需要增加工作站的数目，以高带宽和低延迟的 网络技术支持获得高的加速比，从而获得应用问题的高可扩放性。 从以上的分析可知，集群计算是一种性能卓越，价格低廉的计算模式， 集群技术是并行计算机发展的主流趋势。 1 . 1 3集群计算中的负载平衡 负载平衡的目 标是根据处理机的性能来分配与其相称的任务， 以最小化 应用程序的 执行时间z 1 。 集群系统中的负载平衡可能是静态的即在编译时 进 行，也可能是动态的即在运行时进行。如果处理机的速度和内存资源不同 或者存在短暂的外部负载以及迭代时间不一致， 那么任务的划分就会变得更 为复杂一些。 尽管静态调度防止了运行时调度所产生的额外开销， 然而在一 个多用户的处理机负载不断变化的环境当中， 动态的方法往往更合适。 而且 在程序和系统参数变化的情况下， 不同的应用程序宜采用不同的机制。 因此， 应用程序驱动的可动态配置的负载平衡对于获得好的性能是非常必要的。 对于集群计算的并行程序支持经常忽视了程序员的需要、 真实的负载条 件和用户的行为。 为了更好地利用空闲主机， 一些不同的策略被一些系统采 用来实现负载平衡。 然而， 允许程序员以负载共享的角度来描述并行应用程 序的公开万法还很少。 实际上最优的负载共享策略是很难实现的。 其中的主 要原因是: 北京交通大学硕士学位论文 1 .在一个给定的时刻获取系统全局状态的精确信息是不可能的。 2 .复杂分配算法的执行可能会产生很大的开销。 3 .由于获得的信息不准确，分配算法的行为是不稳定的。 并行程序的放置问题己经得到了广泛研究。很多研究集中在静态调度， 它适用于用户与开发应用程序间没有交互的多处理机系统 ( 专用环境) 。 关 于集群计算的动态负载共享， 大多数研究工作都只是处理处理机负载， 并不 适合整个并行应用程序的分配。另外一些工作则考虑的是程序需求而不是 c p u ，但它们未能提供一个并行程序设计环境。这些工作可以分为两类: 1 .动态放置。进程在启动时分配并处于同样的位置。 2 .进程迁移。进程能够根据工作站过载或工作站被其所有者激活等条 件来进行移动。 1 . 1 . 4集群计算的可用性支持一容错管理 在构造和使用一个集群时，需要考虑几个重要的问题。尽管在这以前对 这些问题己 作了大量的研究和开发工作， 它们仍是目 前活跃的研究和开发领 域。 这四个难点是: 可用性支持、单一系统映像、 作业管理和高效通信。 在 此， 本文仅对集群的 可用性支持进行讨论3 1 可用性概念 在设计健壮、高可用的系统时，以下 3 项要同时考虑: 可靠性、可用性 及可维护性 ( 简称为r as ) 。其中可用性标准最令人感兴趣，它结合了可靠 性和可维护性两个概念: . 可靠性:测量在没有故障的情况下一个系统能工作多长时间。 . 可用性: 一个系统可以为用户所使用时间的百分比， 即正常运行 时间的百分比。 . 可维护性: 指系统是否易于维护， 包括硬件和软件维护、 维修和 升级等。 在研究r a s 时， 将任何阻止系统正常工作的事件称为一个故障。 故障包 括: 1 .非预期故障: 造成系统崩溃的原因有:操作系统瘫痪、硬件故障、网络 断接、人为操作错误及断电等等。所有这些简称为故障，为了修复故障 耍对系统进行维修 2 预期停机:系统未崩溃，但为了升级、重配置及维护，要周期性地停止 正常运行。系统还可能会在周末或假期内停机。 3 .瞬间故障和永久故障:许多故障是瞬间的，它们暂时出现然后消失 4 .部分故障及整体故障:如果某一故障使整个系统不可用称为整体故障 北京交通大学硕士学位论文 若某个故障仅影响系统的一部分，系统仍可用，只是能力有所下降，称 该故障为部分故障。 可用性技术 相互独立的冗余设备改善任何系统可用性的一个重要技术是使用冗 余部件。当一个部件 ( 主要部件)发生故障时，由另一个部件 ( 备用部件) 继续提供服务。 此外主要部件和备用部件之间必须相互隔离， 即不会因为一 个原因发生故障口 在精心设计的集群中， 冗余设备也是相互隔离的。 冗余设备的 相互独立 有以下优点: 1 .如果某个部件有与其相隔离的冗余部件，它不可能成为单点故 障，该部件的故障不会导致整个系统的失败。 2 ，在系统的其它部件正常工作期间，可对发生故障的部件作修理。 3 .主要部件和备用部件之间可相互测试和调试。 故障接管对于现在的商用集群来说故障接管可能是最重要的性能需 求。 一个部件发生故障时， 故障接管技术允许剩下的部分系统能继续提供原 来由 故障 部件提供的服务。 一个故障接管机制应该有几个功能， 如故障诊断、 故障通知及故障恢复。 故障诊断指的是检测故障和定位故障部件。 常用的技术有心跳( h e a rt b e a t ) 技术， 即集群中的节点向 其它别的节点发出一串心跳消息流。 如果系统没有 收到来自 一个节点的心跳消息流， 便说明或是该节点或是网络连接发生了故 障。 一旦诊断出一个故障， 系统会通知需要了解故障事件的各个部件。 故障 通知是非常必要的， 因为不仅是主节点需要了解故障信息， 资源管理器要对 工作负载重新分配， 并接管该节点剩下的工作负载。 另外还要向系统管理程 序报警，以便它能启动相应的动作来修复节点。 恢复方案故障恢复是指为了接管一个己发生故障部件的工作负载所 要做的动作。 有两类恢复技术。 在后向恢复方案中， 周期地为运行在集群中 的进程在稳定存储设备中保存它的一个一致状态 ( 即检查点) 。 发生故障后， 系统重组以与故障部件相隔离，恢复前一个检查点， 然后继续正常的操作， 整个过程叫做卷回。在独立于应用程序的可移植万式下向后恢复较容易实 现，并己 被广泛运用。然而，卷回过程要花很长的执行时间。 如果执行时间是一个很重要的参数， 比如在实时系统中不能容忍卷回恢 复花掉如此长的执行时间， 此时应使用前向恢复方案。 在这个方案中， 系统 不是卷回到故障前的某个检查点， 相反， 系统利用故障诊断信息重构一个有 效的系统状态， 继续执行下去。 前向恢复依赖于应用程序且可能需要额外的 硬件设备加以支持。 北京交通大学硕士学位论文 1 . 1 . 5负载平衡、容错管理与进程迁移的关系 在前面两小节中对集群的负载平衡及容错管理的介绍中可以看到实现 集群的动态负载平衡与故障恢复的关键技术就是进程迁移技术了。 这一节将 介绍这三者之间的关系。 负载平衡的目 标是根据处理机的性能来分配与其相称的任务， 以最小化 应用程序的执行时间。 动态负载平衡由下面四个基本步骤完成: 监控处理机 性能、 在处理机之间交换信息、 计算新的任务分布并做出任务迁移决定以及 实际移动数据， 亦即进程迁移。 进程迁移主要是解决运行时的负载平衡， 监 控模块实时地跟踪系统的负载情况， 收集各个机器的负载参数， 然后重新计 算整个系统的任务分配情况， 做出某个任务需要从一个负载过重的节点迁移 到某一个负载轻的节点上，从而实现整个系统的负载平衡。 随着规模的不断扩大， 集群在计算过程中发生故障的几率也会呈指数 增长。 系统在发生异常事件时会导致本次并行计算的彻底失败， 计算必须从 零开始， 以致不能完全发挥集群系统的计算潜能。 可以采用基于检查点的进 程迁移技术来避免这种情况的发生。 系统周期地为运行在集群中的进程在稳 定存储设备中保存它的一致状态， 使得因系统崩溃而受影响的进程能在一组 新的工作站上自 动恢复， 这样就提高了系统的计算性能， 从而达到整个系统 的高可用性。 由以上的分析可知， 为了保持集群的负载平衡和高可用性， 常常需要进 行进程迁移。 本论文正是出于这种需求，集中研究探讨进程迁移技术在集 群系统中的应用。 1 . 1 . 6 p v m系统简介 近年来， 一些支持集群进行并行程序设计的语言和环境不断出现， 其中 包 括p v m系 统 a s l , e x p r e s : 系 统 e6 1 , l in d a 语 言、 f m 7 1语 言 等 。 在 这 些 系 统 和语言的有力支持下，集群并行计算成为一项迅速发展的技术。 p v m ( p a r a l l e l v i rt u a l m a c h in e ) 是一个软件系统，它最早是由e m o r y 大学的v . s u n d e r a m与o a k r i d g e 国 家实 验室的r .m a n c h e c k 开始研究， 现尚 在继续开发中。 p v m 的主要功能是把网络上各种同构或异构的计算机都利 用起来，当成一台单一的“ 并行虚拟机” 来使用， 从而给用户提供一个统一 的和灵活的并发计算资源。p v m 提供了一个可以让用户在其中利用现有硬 件有效而简单地开发并行程序的统一框架。 它允许将一 组多机种计算机系统 看作是单个并行虚拟机器。p v m 可在体系结构互不兼容的计算机网络上透 明地处理所有消息 、 路径选择、数据转换及任务调度 北京交通大学硕士学位论文 p v m 计算模型既简单而又非常通用，它适用于很多种应用程序结构。 程序设计接口 有意设计得非常简明，因而允许直观地实现简单的程序结构。 用户将其应用程序写成一组相互协作的任务。 所有任务通过一个标准接口例 行程序库来访问p v m资源。 这些例行程序允许在网络上启动和终止任务以 及在各任务间进行通信和同 步。 p v m消息传递原语是面向 多机种操作的， 包括一些用于缓冲和传送的强类型结构。 通信结构包括那些用来发送和接收 数据的结构及一些高级原语，如广播、栅栏同步、全局规约等。 p v m任务可以拥有任意的控制和相关性结构。也就是说，在执行并行 应用程序的任何一点， 任一现行任务皆可以启动和终止其它任务， 或者向虚 拟机增加或减少计算机。任一进程都可以与其它任何进程进行通信或同步。 通过恰当地使用p v m结构和主机语言控制流语句，可在p v m系统下实现 任何特定的控制和相关性结构。 由 于其无处不在的特征( 具体而言就是虚拟机概念) 以及由于它的既简 单而又完备的程序设计接口，p v m 系统在高性能科学计算领域已获得广泛 认可。 1 . 2论文的任务、组织与国内外现状 1 . 2 . 1国内外发展现状 尽管现在很多科研机构都在进行集群容错及进程迁移技术的研究， 但真 正的商业应用还很少见。 有些系统虽然实现了基本功能， 但实际的性能并不 太好， 系统开销很大。 根据不同的设计目 标和应用方向， 这些系统都有所侧 重地在减小开销和增加可容故障数目 等方面上做工作。 美国 威 斯 康星大 学 计 算 机系 推出的c o n d o r g 系 统 是 一 个自 动寻 找 空闲 处理机以执行长时间运行任 务的软件 。c o n d o r的检 查点机制 c k t p ( c h e c k p o i n t i n g ) 已 被应用于c o d i n e , l o a d l e v e l e r 等分布式计算机系 统中。 另 外一些著名的分布计算系统如d q s , l o a d b a l a n c e r , l s f 也正 在进 行对c k p t的开发工作以 支持它们的检查点机制和进程迁移的功能19 1 。 德 国 慕 尼 黑 一些 专 家 研 究的d y n a m i c p v m系 统 1 10 1试图 利 用c k p t 支 持p v m 进程迁移达到动态负 载平衡， 美国卡耐基梅隆大学研发的f a i l - s a f e p v m系 统 t 1 利用c k p t 支持系统容错 国内 也开展了 这方面的 研究。 如吉林大学正在研究的d p v m系统 12 1 主 要解决任务的 迁移与排队问 题， 清华大学的c h a r m i 系统则实现并行程序的 回卷恢复与进程迁移。 此外， 国内的一些知名大学也都在进行这方面的研究 与开发，只是还没有相对成熟的系统出现1 4 1 北京交通大学硕士学位论文 1 . 2 .2论文的任务 p v m 是当前在大型并行处理机系统和以工作站集群为代表的分布式计 算系统中 广泛使用的软件系统， 但它并不支持容错、 进程迁移和负载平衡等 系统功能。本论文就是要把基于检查点的进程迁移技术引入 p v m 中，在 p v m 的通信库上对其功能进行扩充，实现了基于检查点机制的并行程序进 行回滚恢复和进程迁移的功能， 同时为进一步实现负载平衡和系统容错奠定 基础。 要把进程迁移引入 p v m系统中，需要修改p v m系统的通信机制。首 先要了解 p v m 系统的通信机制及实现技术，因此这就需要对 p v m 系统的 源代码进行深入的剖析， 掌握其实现精髓。 其次， 要实现保存通信进程的一 致性状态的检查点技术，最后在前两步的基础上，修改p v m的通信机制， 在其中实现进程迁移。 1 . 2 .3论文的组织 第一章首先简要介绍了集群系统、 集群中的负载平衡及其高可用性即 系统容错，分析了进程迁移与负载平衡及系统容错的关系，介绍了p v m系 统。然后提出论文的主要任务，并介绍了国内外在这方面的发展现状。 第二章对目 前的检查点算法进行了概括、 总结和分类。 详细地描述了 各种算法并进行了比较， 从而分析了其优缺点并提出改进方法。 然后讨论了 集群系统中的基于检查点的进程迁移机制。 第三章、 第四章 对p v m系统的源代码进行了详细的、系统的分析， 介绍了p v m系统的一些重要的数据结构与关键技术。 特别对其消息传递机 制进行了深入的分析与讨论。 第五章分析了l i n u x 系统下进程的内存映像， 介绍了如何实现进程的 检查点与映像恢复，并分析了一些关键技术进而阐述了 在p v m系统中实 现基于检查点的进程迁移的算法思想及其实现过程， 分析了其中的不足， 并 提出改进思想。 第六章对论文进行总结，并对下一步的工作进行展望。 北京交通大学硕士学位论文 第二章 基于检查点的进程迁移 2 . 1检查点与回滚恢复 检查点用于保存和恢复程序的运行状态， 检查点对程序状态进行保存的 时刻成为检查点时刻。 根据检查点算法的适用范围可把目 前的检查点算法分 为两类:单进程程序检查点算法和分布式程序检查点算法。 2 . 1 . 1单进程的检查点 单个进程的检查点是进程地址空间在给定时刻的一个快照， 也即在某一 时刻进程的状态。 进程的状态是指， 为了保证进程在迁移之后能够继续正确 地执行所必需的信息。 进程状态应该包括进程的数据段、 用户栈内容， 还应 包括程序计数器 p c 、处理机状态字 p s w、栈指针 s p内容、活动文件信息 以及中断、信号等信息。 单进程程序检查点算法用于保存和恢复单进程程序的运行状态。 在内 存 中一个进程的运行状态由用户区和核心区两部分组成。 检查点不是操作系统 的一部分， 不能保存和恢复进程核心区的全部信息。 因此， 检查点通常不能 打断系统调用的执行。对于单进程的恢复只需要重新执行检查点文件。 用户地址空间 检查点文件 图 2 . 1检查点信息 要实现正确的回卷恢复， 必须保证进程保存信息的完备性 决定进程行 为的要素有进程状态和进程环境。其中进程状态又分为易失状态( v o l a t i l e 北京交通大学硕士学位论文 s t a t e ) 和持久状态 ( p e r s i s t e n t s t a t e ) 。 前 者即 进程上下文， 包括 进程正文段、 数据段、操作系统核心态结构等。后者指与进程执行有关的外存空间内容。 进程环境指进程面临的操作系统环境， 包括进程通过操作系统访问的各种资 源，如交换区、文件系统、通信通道等。 进程上下文是进程执行活动全过程的静态描述， 因此检查点信息应包括 进程上下文中决定程序运行正确性的关键内容，如图2 . 1 所示，检查点应保 存的进程上下文内容为: . 进程数据段、用户栈内容。 . 与上下文切换有关的项，包括程序计数器 p c 、处理机状态字寄 存器p s w,栈指针s p等。 . 活动文件信息， 包括文件描述符、 访问方式、 文件大小、 读写指 针等。 . 有关信号信息， 包括信号量屏蔽码、 信号量栈指针、 信号量处理 函数句柄，以及被挂起的信号量。 . 与进程相关的外存空间内容， 即用户文件内容也应该保存。 因为 在以读写方式打开文件并进行交替读写的情形下， 只保存活动文 件信息， 很可能导致回卷恢复后文件内容与全局状态不一致， 产 生不易觉察的执行错误。 因此完整的检查点信息还应包括: 与进 程执行有关的用户文件内容。 2 . 1 .2分布式进程的检查点 当进程相互交换信息的时候， 采用恢复独立进程的简单方法来恢复通信 进程就显得不够了。 为了将通信进程从故障中恢复回来， 就必须将进程回卷 到一个全局一致性状态中去。 基本概念 .全局一 致性状态 设分布程序p由 进程p i ,， ， p 。 组成，c i.m为进程p 、 的第m个检 查点文件，一个进程间消息 m，有两个与之相对应的事件;消息发送事件 s e n d ( m ) 和消息接受事件r e c e i v e ( m ) ，当进程p 、 发 送消息m的时刻早于进程 p ， 做第m个检查点的时刻， 称s e n d ( m ) e c i. , ; 当进程p i 接收消t , m的时刻 早于进程p . 做第m个检查点的时 刻， 称r e c e i v e ( m ) e c i, n 。 定义 设集合s = ( c l m 1 ,c 2 .m 2 . . . , c n . n ) 是 分布式程序p 各 进程的 检查点 文件组成的全局状态， 若t / 消息m和d 整数i ( 1 i n ) 都有: r e c e i v e ( m) e c i.m = :, 3 j ( 1 1 北京交通大学硕士学位论文 .全局一致时刻 时间 图2 . 2全局一致时刻 如图2 .2 所示， 分布式程序p 由 运行在不同 主机上的 进程p l ,p 2 ,p 3 组成， m l , . . . . . . , m 4 是进程间发 送的消息， c l , c 2 , c 3 ， 表示 三个不同的时刻， c i 与p i 的交点表示进程p i 在c i 时刻所处的运行状态， c i 与m i 共有三种关系: ( 1 ) 不 交叉，如c l 时刻:( 2 ) 左交叉，如c 2 时刻与消息ml , m 2 。消息ml , m 2的 发送时间 早于。 2 , 接收时间晚于。 2 ; ( 3 ) 右交叉，时 刻0与消息m 4 , 消息m 4 的发送时间晚于c 3 ， 接收时间早于c 3 . 并非在任何时刻对分布式程序做检查点操作， 都能够使程序正确地卷回 执行， 如在有右交叉消息m 4 的。 3 时 刻对程序p 做检查点， 此时p 3 进程的 检查点文件中 所记录的 进程状 态是p 3 进程己 接收到 消息m 4 ， 而p 2 进程的 检 查点文件所记录的进程状态是p 2 进程并未发送消息m 4 ， 当把程序p 卷回到 0 时刻重新运行， 若p 2 进程卷回到c 3 时 刻再次运行时不再发送消息m 4 , 那么p 3 进程就等于是接收到了 一个任何进程都未发送的消息m 4 , 这显然是 错误的。 定义 没有右交叉消息的时刻称为全局一致时刻。 在全局一致时刻对各 进程做局部检查点， 各进程检查点文件组成的集合就是一个一致的全局状态 9 ,1 0 1 。 分布式程序在卷回 执行时， 必须卷回到一个一 致的全局状态。 .多米诺效应 为了将通信进程从故障中恢复回来，就必须将进程回卷到一个全局一 致状态中去。 在这样一个状态被找到之前， 一个进程的回卷可能会导致其它 进程的接连回卷。 有时候， 可能所有进程回到其初始状态， 这种情况叫多米 诺效应 。 北京交通大学硕士学位论文 恢复线( r e c o v e ry l i n e ) 八/ 检查点( c h e c k p o i n t ) a】、 、 、c/ x ye f 故障 图 2 .3 回 滚传播、恢复线和多米诺效应 如图 2 . 3所示， 假定系统发生故障，进程 p卷回到它的局部检查点 e , 接下来它需要通过通信 z 从进程q获得一个重发的消息。 为完成任务， 进 程q必须卷回至检查点d . 。 现在q又需要通过通信y 从进程p 获得一个消 息。因此p 又必须卷回到检查点。 。 最后， 进程p 和q都卷回到初始状态a 和b ， 也就是说这种情况下检查点操作毫无用处。 因此在考虑设置检查点的 时刻时要避免多米诺效应。 2 . 2 检查点算法 分布式进程的检查点算法可以分为两类:独立式检查点和协调式检查 点。在下面的章节中分别予以介绍。 2 . 2 . 1独立式检查点算法 .算法概述 采用独立式检查点，每个进程独立保存它的状态而不与其它进程同步， 也就是说， 各个进程在什么时候设置检查点是相互独立的。 独立式检查点算 法也称为异步检查点算法， 程序各进程周期性地相互独立保存自己的运行状 态和记录所接收的消息; 在程序状态恢复过程中， 各进程之间则需要相互协 调、 通过复杂的卷回算法各目 卷回到合适的检查点时刻以 使整个程序恢复到 一个全局一致的状态。 独立式检查点给进程以最大的自 主权来决定什么时候设置检查点， 最大 的优点是进程可在其最方便的时候来设置检查点。 比如， 在其状态信息最少 时进行记录以减少系统开销但因此也会带来一些缺点。主要是: ( 幼在找全局一致的状态的过程中.可能会出现多米诺效应.以使许多 检查点变得无效，甚至回滚到程序执行的最初。 北京交通大学硕士学位论文 ( 2 ) 某些进程可能会记录一些永远不可能是全局一致状态中的检查点。 这些检查点是无效的， 因为它不但浪费系统的资源， 而且在回滚恢复过程中 是无用的。 ( 3 ) 独立式检查点使每个进程要维护不同时刻的多个检查点文件，这就 需要定期运行无用检查点收集算法来回收那些无用的检查点， 以释放系统资 源。 独立式检查点算法采用消息日 志来防止多米诺效应的发生。 日 志的方法 可以分为两类: 被动消息日志和主动消息日 志。 在被动消息日 志方法中， 系 统在将到来的消息发送给应用程序之前，先将它写到稳定的 存储区当中 1 8 1 当重新启动的时候， 故障进程被回卷到最近的检查点并响应由日 志立即 送来 的消息。 而且该进程在消息被写入稳定存储区之前是被阻塞的。 或者， 系统 可以将消息立即发送给应用程序， 但在消息尚未被写入稳定存储区之前不能 再发送消息。 在主动消息日志方法中， 消息被打上标记以允许系统跟踪进程 间的依赖关系 1 9 7 。 进程之间的依赖信息用于决定哪个进程需要在重启的时 候被回卷。 这个方法减少了日志所带来的额外开销， 但是幸存的进程仍可能 需要回卷。 或者消息可以集中在发送主机的主存当中， 并被异步地保存在稳 定存储区内。 上面所列出的益处是以消息作为日志所带来的时间和空间开销 为代价而获得的。由于当前硬盘容量很大， 所以空间开销影响不大。 而且在 每一个新的检查点处， 所有消息都将从相应的备份中删除 ( 日 志将在每个检 查点后被完全删除) 。 主要的开销是输入/ 输出所产生的额外开销 ( 也就是访 问稳定存储区的延迟) 。 凡卜 一 一一j一 图 2 . 4检查点图示 为了具体说明独立式检查点回滚算法， 先