（计算机应用技术专业论文）基于pvm的并行检查点系统的关键技术研究.pdf

华中科技大学硕士学位论文 摘要 f 以工作站群为代表的并行计算环境是当前分布式系统和并行计算的研究热点之一。 、p v m 是一种当前被广泛应用的并行计算环境，并通过它所提供的消息传递机制支持了高 效的异构网络计算。但标准的p v m 缺乏对系统容错的支持，为保证p v m 并行计算环境的 高可靠性，通过检查点的回滚恢复方式可予以弥补。检查点技术是一种在并行计算和分 布式计算环境中广泛使用的，采用回滚恢复的容错技术。它通过记录程序当前执行状态 的方式，使系统在崩溃之时可恢复到某一个保存了程序执行状态的时刻重新开始执行 在对各种传统的5 n i x h i n u x 检查点算法进行分析和分类评述的基础上，采用基于 p w m 的交错的菲阻塞一致性并行检查点算法，在l i n u x 工作站群环境下实现了一个可应 用于p v m 的并行检查点系统p v m c k p t 。它不仅为p v m 提供了容错能力，也为用户对并行 任务的进行检查点设置回滚恢复操作提供了一个图形控制接口，并为在此基础上进 步实现p 的进程迁移和动态负载平衡提供了个基本的系统框架。 p v m c k p t 的基本检查点设置回滚恢复算法主要涉及了进程状态、打开文件状态的 保存与恢复，信号的处理以及对系统调用的扩充等。在检查点优化方面，采用了增量检 查点技术以减少检查点文件的大小，并采用写时拷贝技术减少检查点设置操作的时延。 p v m c k p t 在处理任务进程间通信的致性同步方面，采用了交错的非阻塞一致性并 行检查点算法。与传统的一致性同步检查点算法相比，该算法在进行检查点设置操作时 不会因为一致性同步操作导致用户进程的冻结。而且当节点机具有多个处理器时，进行 检查点操作不会由于对存储器的争用而导致用户进程的冻结，提高了检查点算法的效 率。 关键词：并行计算：容错；检查点；p ：冻结时间 华中科技大学硕士学位论文 a b s t r a c t c o m p u t i n ge n v i r o n m e n te x e m p l i f i e db yc l u s t e r so fw o r k s t a t i o n si so n eo ft h eh o t s p o t s i ns t u d yo fd i s t r i b u t e ds y s t e ma n dp a r a l l e lc o m p u t i n g a saw i d e l yu s e dp a r a l l e lc o m p u t i n g e n v i r o n m e n t ，p v mp r o v i d e st h en e c e s s a r ys u p p o r tf o re f f i c i e n t h e t e r o g e n e o u sn e t w o r k c o m p u t i n gb y i t s m e s s a g e p a s s i n gm e c h a n i s m b u tp v ml a c k s t h e a b i l i t y t o s u p p o r t f a u l t - t o l e r a n c e ，w h i c h c a nb ce n h a n c e d b y r o l l b a c k r e c o v e r y w i t h c h e c k p o i n t i n g c h e c k p o i n t i n gi s af a u l t - t o l e r a n c et e c h n o l o g yw h i c hp l a y sa ni m p o r t a n tr o l ei nd i s t r i b u t e d c o m p u t i n g a n d p a r a l l e lc o m p u t i n g c h e c k p o i n t i n g c a ns a v e r u n n i n g s t a t eo ft h e p r o g r a m w h e n t h es y s t e m c r a s h e s ，i tc a nb er e s t o r e dt oa p o i n tt h a tt h er u n n i n gs t a t eh a sb e e n s a v e db e f o r eb y u s i n gc h e e k p o i n t i n gf i l e s o nt h eb a s i so fa n a l y s i sa n dd i s c u s s i o ni nd e t a i lt o i m p l e m e n t a t i o no fm a n yb a s i c c h e c k i ：i o i n t i n g r o l l b a c kr e c o v e r ya l g o r i t h m ，ap a r a l l e lc h e c k p o i n t i n gs y s t e m - - p v m c k p ti s i m p l e m e n t e di n t h ec l u s t e ro fl i n u xw o r k s t a t i o n s b yu s i n gt h es t a g g e r e dn o n b l o c k i n g c o n s i s t e n tp a r a l l e l c h e c k p o i n t i n ga l g o r i t h mi np v m ，p v m c k p tn o to n l yp r o v i d e st h e a b i l i t yo ff a u l t t o l e r a n c e f o rp v m ，b u ta l s op r o v i d e sag r a p h i c su s e ri n t e r f a c ef o ru s e r st o c o n t r o lt h eo p e r a t i o n so f c h e c k p o i n t i n ga n dr o l l b a c kr e c o v e r yo fp a r a l l e lt a s k si np v m a n d 0 dt h i sb a s i s ，as y s t e ms k e l e t o ni se s t a b l i s h e dw h i c hc a nb eu s e df o r p r o c e s sm i g r a t i o na n d l o a db a l a n c es y s t e mi nt h ef u t u r e t h eb a s i c c h e c k p o i n t i n 掣r o l l b a c kr e c o v e r ya l g o r i t h mm a i n l y i n v o l v e s s a v i n g a n d r e c o v e r i n go f s t a t e so ft h ep r o c e s s ea n dt h ef i l e so p e n e d ，s i g n a lh a n d l i n ga n de x t e n s i o no f s y s t e m c a l l i no p t i m i z a t i o no f c h e c k p o i n t i n g ，i n c r e m e n t a lc h e c k p o i n t i n g i sa d o p t e dt or e d u c e t h es i z eo f c h e c k p o i n t i n gf i l e sa n d c o p y o nw r i t ea l g o r i t h mi sa d o p t e dt or e d u c e d e l a y i n g i nc o s n s i s t e n t s y n c h r o n i z a t i o no fc o m m u n i c a t i o na m o n gt a s k p r o c e s s e s ，s t a g g e r e d n o n b l o c k i n g c o n s i s t e n tp a r a l l e l c h e c k p o i n t i n g i s a d o p t e d c o m p a r e d t ot r a d i t i o n a l c h e c k p o i n t i n ga l g o r i t h m s ，i tw o n tc o n d u c et of r e e z i n go f u s e rp r o c e s s e s e s p e c i a l l y , w h e n i l 、 华中科技大学硕士学位论文 s o m e 。o m p u t i n g “o d 。8i nt h es y s t e mh a v em o r et h a no n ep r o c e s s o l t h i s a l g o r i t l l r nw i l l i p o 。e f f i c i c e n c yo fc h e c k p 。i n t i n g ，b e c a u s e c h e c k p o i n t i n go p e r a t i o nw o n tc o n d u c et o 。o m p e t i t i o nf o rs t r o g ew h i c hw i l lr e s u l t ei nf r e e z i n go f u s e rp r o c e s s e s k e yw o r d s ：p a r a l l e l c 。m p u r i n g ；f a u l t t o l e r a l i c e ；c h e c k p o i n t i n g ；p v m ；f r e e z i n gt i m e i l l 华中科技大学硕士学位论文 1绪论 1 1 课题背景 1 随着并行处理和分布式处理技术在科学研究和航天、航空、石油等工程技术领域的 广泛应用，人们对计算机系统的性能和可靠性提出了越来越高的要求。并行处理是提高 计算能力、满足不断增长的应用需求的有效途径，而容错技术是提高计算可靠性的重要 保证。 机群系统是利用现有的工作站资源，通过高速网络以某种结构连接起来而构成的并 行系统，目前己成为并行处理发展的主流方向之一。机群系统随着规模的不断扩大，它 在计算过程中发生故障的几率也会呈指数增长，同时由于机群系统通常为多用户使用， 结点等资源具有较大的可变特性。系统在发生异常事件时往往会导致本次并行计算的彻 底失败，此前的大量计算不再可用。大规模科学工程计算任务执行时间都较长，一旦某 计算结点发生上述异常事件，将导致系统运行失败，程序不得不从头开始执行。为了避 免系统在发生上述事件后由于从头开始执行而引起计算上的大量浪费，充分提高机群系 统的可用性，在系统正常运行的适当时刻设置检查点( c h e c k p o i n t ) ，保存系统当时的规 范状态，并对各进程进行相关性跟踪和记录。系统发生故障后，将相关进程回滚( r o l l b a c k ) 到故障前系统的一致性状态( 设置检查点的时刻) 。程序经过状态恢复后从该检查点处 重新执行，而不是重新开始执行，从而节省了大量的重复计算时间，充分体现机群系统 的并行性能。这种基于检查点的后向恢复技术不仅可以对系统瞬时间歇故障进行自动 恢复，也是恢复未知故障在某一应用设计过程中末预料到的故障的有效手段。 人们很早就开始从各个角度对检查点技术做了广泛深入的研究，并取得了许多成 ，。 绩。检查点技术可以在许多层次上实现。有在语言级使用编译技术的，如m i t 的 p o r c h ( p o r t a b l ec h e c k p o i n tc o m p i l e r ) 2 1 ，这是一个把c 程序转换成语义相同的，具 有检查点设置和回滚恢复能力的程序的源到源编译器，它的特色是生成的检查点具有良 好的移植能力，可以在异构环境中恢复执行。有在用户级以函数库形式供用户调用、链 接的，如w i s c o n s i n - m a d s i o n 大学的c o n d o r 系统( 3 】，p r i n s t o n 的l ik a i 、j a m e sp l a n k 等人写的l i b c k p t 【4 等。前者利用检查点技术在工作站网络上实现了一个基于进程迁移 华中科技大学硕士学位论文 【5 l 自分布式作业管理系统，它的检查点技术是用户级检查点的典范，被许多容错系统使 用或借鉴；后者则着重于检查点技术的优化。也有一些操作系统本身就被设计成具有检 查点保存恢复的能力。从八十年代中到现在，更多的工作致力于分布式系统检查点技 术的研究。人们深入研究分布式系统的一致状态的性质，通过消息记录和重放等技术 ( m e s s a g el o g g i n g a n dr e p l a y ) ，实现了许多分布式检查点系统。 近年来随着计算机软硬件技术的飞速发展，工作站网络日益成为流行的并行计算平 台。工作站网络各节点通过网络传递消息来通信，m p i 、p v m 等系统给用户提供了并 行程序编程环境并让用户通过消息传递的标准调用接口控制并行程序各进程之间的通 信，是目前流行的并行计算环境。它们所提供的消息传递机制支持了高效和高性能的异 构网络计算。而对用户而言，p v m 环境提供了完整的虚拟机概念和良好的消息传递编 程界面。但m p i ，p v m 等系统都不支持诸如进程迁移和负载平衡等功能，对于这些架 构于多个通过网络连接的独立的计算机构成的机群系统之上的并行计算系统，这些功能 的实现都与它们的基于检查点的容错功能密切相关，需要检查点技术的支持。 基于上述情况，我们考虑将检查点技术引入到p v m 中，并基于p v m 本身的消息 传递机制，实现基于p v m 的分布式检查点算法。并根据此算法设计和实现一个基于 p v m 的并行检查点系统p v m c k p t ，不仅为p v m 提供容错能力，还可以使用户对任务 进程进行检查点操作的过程进行监控和交互。这样，以此系统为基础，可进一步实现 p v m 的进程迁移和动态负载平衡。 1 2 国内外研究概况 检查点算法的研究是当前国际学术研究的热点和难点，现在已经有了很多检查点算 法。并且，很多分布式系统在设计和实现中都使用了检查点算法，不仅为分布式系统提 供了容错功能，还在此基础上为分布式系统实现了进程迁移和动态负载平衡功能。而且， 近年来，在操作系统的研究方面，尤其是l i n u x 和分布式操作系统方面，也正在逐步采 ， 用检查点技术，以使得操作系统本身具有容错功能。 2 华中科技大学硕士学位论文 1 2 1 国内外类似系统的研究概况 1 c o n d o r c o n d o r 是w i s c o n s i n - m a d s i o n 大学研制的一个异构型分布式系统。它的核心实现方 式为使用位于工作站池中的空闲资源来得到高吞吐量计算。充分利用工作站的空闲时间 是c o n d o r 的最显著特征。c o n d o r 管理的机群由网络中的工作站组成，工作站主人可以 自愿加入或退出。c o n d o r 监测网络中所有工作站的状态，一旦某台计算机被认为空闲， 便把它纳入到资源池( p o o l ) 中。资源池中的工作站被用来执行作业。当工作站的主人 丌始使用该工作站时，c o n d o r 便将运行在该工作站上的作业迁移到其它节点上继续运 行，从而避免了对工作站主人的影响【6 1 。所有这些特征并不需要修改底层的u n i x 操作 系统核心，只需在用户级 7 1 进行，而且不需修改用户程序，只需与c o n d o r 提供的库函 数重新链接。 c o n d o r 的主要特征是：充分利用工作站的空闲时间；用户只需与库函数重新链接 便可利用c o n d o r 提供的检查点和进程迁移功能；对于远程执行的进程，本地的执行环 境被保留：工作站主人对该工作站拥有最高优先级和完全的控制权：作业保证彻底完成， 不会因为系统的故障或工作站的退出而终止：本地磁盘空间不会被c o n d o r 作业所占用： 对网络资源、数据传送和检查点操作的有效监控：对网络资源、c p u 的协同调度。用 户可以从工作站池中的任何一台机器提交任务，系统将自动从c o n d o r 池中查找最合适 的空闲机运行任务，它利用将大型计算任务派至远程空闲机执行的方式，把空闲处理机 的c p u 资源分配给其他用户，从而实现负载的共享。 但是，c o n d o r 的检查点技术仅支持单进程任务。在c o n d o r 中，不支持使用f b r k 及 类似系统调用的任务。使用这些系统调用的任务在父子进程间进行通信，协调进行工作， 而c o n d o r 无法为多个进程生成检查点文件。而且c o n d o r 也不支持使用信号和信号处理 程序的应用程序。 2 f a i l 一s a f ep v m f a i l s a f e p v m s l 是由卡内基梅隆大学j u a n l e o n 等研制的一个基于p v m 的分布式容 错计算系统。系统在实现时包含了进程迁移的功能。f a i l s a f ep v m 不但保证进程状态 的正确恢复，而且实现了故障恢复后重新执行的分布式程序不受进程位置变化的影响。 为保证分布式程序的一致性，f a i l s a f ep v m 在对全局做检查点之前进行一次全局同步 华中科技大学硕士学位论文 过程，确保所有已经发出的报文都到达目的地。 f a i l s a f ep v m 主要具有以下特点：( 1 ) 与应用程序无关。可支持任意计算模型的应 用程序。( 2 ) 对应用程序的透明性。由于容错的存在，系统的故障对于应用程序的运行 是不可见的。( 3 ) 兼容性。f a i l s a f ep v m 所提供的用户接口与p v m 的用户接口相兼容。 ( 4 ) 完全在操作系统外部实现。f a i l s a f ep v m 的实现只使用了操作系统提供的标准接口， 这种实现方式使f a i l s a f ep v m 具有好的可移植性，能够在不同的操作系统平台上实现。 对于一个由多个任务进程组成，且进程间也互相进行通信的并行计算任务来说，每 个进程在任一时刻对整个系统的状态都有着不同的影响。更重要的是，如果不采用延时 使系统达到一个全局一致的状态，每个任务进程都无法知道其他进程何时进行检查点操 作。各个进程各自独立地进行检查点操作会导致系统进入不一致的状态从而导致消息的 丢失、重发。f a i l s a f ep v m 就是通过在各进程进行检查点操作前先进行一次全局同步， 以保证全局状态达到一致。虽然这种方法会导致任务进程的冻结，效率低下，但陔算法 实现简单，f a i l s a f ep v m 从实现的角度出发选择了这种算法。 3 c r a c k c o l u m b i a 9 1 大学网络计算实验室在2 0 0 1 年发布的c r a c k 则是在操作系统级 ”1 以 内核模块的形式实现的检查点系统。这是第一个在u n i x l i n u x 中实现的完全透明的检 查点系统。由于c r a c k 是以内核模块的形式实现的，操作系统中的进程可以完全透明 的进行检查点和恢复，既不需要对操作系统进行改动和重新编译，也不需要对用户程序 的代码进行任何的改动和重新编译。而且c r a c k 对网络套接字也提供了支持。 c r a c k 主要实现了以下功能：( 1 ) 不需要修改内核就可以完全透明地实现应用程 序的迁移。( 2 ) 除了真正的检查点恢复操作，没有运行时开销。( 3 ) 实现了没有“主节 点”和“代理”进程的真正的进程迁移。( 4 ) 以较低的开销实现了虚拟网络。( 5 ) 对网 络连接的迁移提供了支持。 c r a c k 与其它的进程迁移系统的不同就在于它不需要对源代码( 操作系统或应用 程序) 进行修改。对操作系统源代码的修改往往会导致系统难于部署，因为不是所有操 作系统都提供源代码可以修改，而且，直接对内核打补丁也往往会导致操作系统内核过 大。c r a c k 主要利用了大多数u n i x l i n u x 都支持的可装卸内核模块。这些模块主要在 操作系统启动的时候或某些特定的函数被调用时加载到内核中。一旦被加入内核，它就 华中科技大学硕士学位论文 以优先级模式运行在内核空间。 c r a c k 一个关键的设计思想就是将检查点设置回滚恢复功能以内核模式实现，这 也是c r a k 的设计中最具挑战性的地方。虽然内核模块与内核运行于同一优先级模式， 但它只能与内核进行协作而不能任意改变内核的行为。c r a c k 使用设备文件( 通常在 d e v 中) 实现用户程序对内核模块的使用。内核模块在启动时将自己注册为一个设备文 件( d e v c k p t ) ，用户程序通过标准的文件操作( o p e n ，c l o s e ，r e a d ，w r i t e ) 与模块进行 交互。c r a c k 的研制成功证明了为流行的操作系统( 如l i n u x ) 设计一个通用的透明 的检查点包，而且不用对操作系统或用户程序添加补丁是完全可行的，这是目前第一个 真正实现操作系统级透明的检查点系统。 近年来检查点技术也正在从研究阶段逐步走向实用化，许多机群计算机环境都利用 检查点机制来增强系统的容错功能。但国内在检查点技术的研究主要着重于算法和理论 研究上，在系统实现上还相对较少。 1 2 2 主要关键技术的研究概况 分布式检查点的研究主要包括以下几方面的技术： 1 u n i x l i n u x 进程基本的检查点设置回滚恢复方法。 2 文件检查点技术。 3 检查点的优化技术。 4 分布式检查点技术。 ( 1 1u n i x l i n u x 进程基本的检查点设置和回滚恢复。 检查点各部分内容有着相互独立而又相互联系的保存和恢复方法。除用户文件内容 外，其余各部分内容的保存和恢复的基本方法【“】如下：进程的数据段和用户栈保存 与恢复。检查点设置时，未经优化的完全保存模式将数据段自起始地址到新分配的最高 地址拷贝到检查点文件中。恢复时，将检查点文件中数据段内容拷回到地址空间的原来 位罱。进程用户栈的保存和恢复与此类似。但是恢复用户栈时，由于当前调用过程：= j ) i 在 用户栈中运行，为防止其返回地址和局部数据结构被拷回的用户栈内容覆盖进而导致程 序运行错误，必须先保证当前用户栈中有用内容不会被覆盖后，才可进行用户栈的拷回。 一般系统采用的是转移法，即将栈指针改为指向数据段中的一个安全的b u f f e r t “】。另外 华中科技大学硕士学位论文 一种办法是栈增长法。即在恢复用户栈之前，若发现当前栈顶地址大于欲拷回栈的栈顶 地址，或虽然小于但非常接近以至相差小于某一闽值( 假定在系统中用户栈由高地址 向低地址方向增长) ，则表明当前调用过程要用到的栈中数据可能因拷回而被覆盖，此 时，反复调用当前过程直至当前栈顶地址小于欲拷回栈的栈顶地址，且其差值大于阈值 为止。与上下文切换有关的项的保存与恢复。检查点设置时，与上下文切换有关的项， ， 包括程序计数器p c 、处理机状态字寄存器p s w 、栈指针s p 可利用系统调用s i g s e t j m p 保存到一环境变量中。恢复时，用相应的系统调用s i g l o n g j m p 将它们恢复。与信号有 关的信息的保存与恢复。系统调用s i g s e t j m p s i g l o n g j m p 在保存和恢复与上下文切换有 关的项的同时，还附带保存和恢复信号量屏蔽码以及信号量栈指针。另外在设置检查点 时，通过系统调用s i g a c t i o n 和s i g p e n d i n g 分别获取信号处理函数句柄和被挂起的信号， 记录到数据段中的一个信号信息表中，随数据段保存而保存。恢复时，在数据段拷回后， 取出其中的信号信息表，通过相应的系统调用将信号处理函数旬柄和被挂起的信号逐一 恢复。活动文件信息的保存与恢复。在数据段中定义文件信息表用于活动文件信息的 保存和恢复。在正常执行过程中，监督o p e n ，r e a d ，w r i t e ，c l o s e 等文件操作系统调用， 并维护文件信息表中相应文件表项。检查点设置时，文件信息表将作为数据段的一部分 被保存。恢复时，在数据段恢复完后，依据文件信息表中记录的活动文件信息，按原访 问方式打开文件，并恢复其文件描述符和读写指针。 ( 2 ) 文件检查点技术。 对于用户打开文件的信息的保存 1 3 1 ，a t & t 公司的l i b c k - p 将l a z yc o o r d i n a t i o n e “1 的 概念应用到文件内容的保存恢复：在打开文件时把文件大小存于硬盘，当某段文件区域 即将被修改时或文件即将被删除时，对整个文件进行备份。当发生故障时，使用备份文 件来恢复用户文件内容。但是，由于一个检查点间隔内，用户文件中可能只有很小一部 分内容发生改变，对整个文件进行备份不必要，所以这种方法的时间、空间开销依然很 大。而且每个检查点间隔内的第一次写操作必须在整个文件备份完毕后才能进行，引入 了较大的正常运行时间开销。 针对l i b c k p 所用方法的缺点，可以有两种优化方案，一种是“备份法”，一种是“恢 复写”。“备份法”的基本思想也是基于对用户文件的备份，但是它备份的时机与l i b c k p 不同。它在每次设置检查点时对上次设置检查点以来修改过的用户文件进行备份，而这 6 华中科技大学硕士学位论文 一备份工作又可以与其它状态的保存并行进行，这样就避免了每个检查点间隔内的第一 次写操作等待时间。备份法最大的优点是实现简洁，但是其空间开销依然很大。“恢复 写”策略是设置完一次检查点之后，当某块文件区域即将被修改时，先要根据写操作的 内容和当时文件的内容组织出对应的u n d o 操作，并将其保存到硬盘上的u n d o 日志 文件中。一旦进程发生故障并卷回到上一检查点重新执行，则按照从后向前的顺序逐一 执行记录在日志文件中的u n d o 操作，将从上一检查点开始到故障前一刻被修改的文 件内容恢复。a t & t 实验室对l i b c k p 进行了优化，实现了这一策略。这种策略在设置检 查点时，只需保存活动信息而不必做任何其它工作，但这种策略使得每次正常的写操作 都引入额外的读操作和写操作各一次，而且必须等组织完u n d 0 操作并写入u n d o 日 志文件之后才能对原文件进行写操作，其带来的正常执行开销可能是无法容忍的。 在l i b c s m 系统中采用一种低开销的延迟写( w r i t eo p e r a t i o nb u f f e r i n g ) 1 5 1 文件检 查点策略。w o b 策略实现了对用户活动文件的检查点设置，支持用户进程进行任何文 件操作，有效地解决了在发生故障时用户文件的卷回恢复的问题。w o b 策略的基本思 想是使得相邻两个检查点之的所有文件写操作( 包括删除操作) 具有原子性，即这些操 作或者全都正确执行完毕，或者由于发生了全都故障全部放弃。w o b 策略使得用户文 件内容在设置下一个检查点之前不会被改变，实际上是对文件内容做了检查点设置。它 对用户透明，并通过优化设置内存缓冲区大小、时延隐藏等手段，使得这种策略在空间 开销、正常运行时间、恢复时间等性能指标上优于上述其它方法。 ( 3 ) 检查点的优化技术。 检查点文件信息的大小直接影响到检查点设置的时间和空间开销。检查点优化的基 本思想主要是通过时延隐藏技术尽可能使得检查点设置操作不影响进程的正常运行；同 时，在保证检查点信息完备的基础上尽可能减小检查点文件容量。 时延隐藏( 1 a t e n c yh i d i n g ) 【1 6 1 就是通过使检查点保存与程序的计算并发进行，而使 写盘带来的延迟并不体现在检查点设置的时间开销上，也就是隐藏了部分时延。这种方 式付出的代价是检查点延迟略有增加。典型的优化手段有：检查点缓存( c h e c k f i o i n t b u f f e t i n g ) 。写时拷贝缓存( c o p y - o n - w r i t eb u f f e r i n g ) 。克隆( c l o n e ) a 检查点缓存技术在主存足够大时，能显著地减小检查点设置开销，但是当主存不足 以供整个检查点傲缓存时，减小的开销就不那么明显了。写时拷贝缓存技术是较为有效 7 华中科技大学硕士学位论文 的一种优化方式，对检查点设置开销的减少很可观，但这又与应用程序对内存的访问方 式有关。克隆是一种写时拷贝缓存优化的一种非常简单并且移植性很好的实现，其性能 与写时拷贝缓存大致相当。 减小检查点文件大小。检查点设置延迟通常是造成检查点设置时间开销的主要原 因，而在设置延迟中的大部分时间都是在进行写盘操作，所以可以通过减小检查点的大 j , ( c h e c k p o i n ts i z er e d u c t i o n ) 来达到减小检查点设置时间开销的目的。典型的优化手段主 要有：检查点压缩( c o m p r e s s i o nc h e c k p o i n t i n g ) 。内存区域排除( m e m o r ye x c l u s i o n ) i ”】。 检查点压缩方式通过使用标准的压缩算法，减小了检查点的大小，从而减小了检查点设 置的时间开销。但是由于压缩本身要带来一定的开销，只有在其减小的开销小于其本身 带来的开销时，这种方式才是可取的。另一种是内存区域排除。在进程的内存区域中， 有两种类型的内存区域可被排除在某次检查点之外：一种是d e a d 内存区域，在此内存 区域中保存的数据不会再被进程访问，或者在对这个区域进行读操作前，要先进行写操 作，因此不用保存；二是c l e a n 内存区域，这种内存区域中保存的数据从上一次设置检 查点后，没有被修改过，那么这种内存区域中的数据一定已经保存在以前设置的检查点 中，这次不需保存。内存区域排除优化所要解决的主要问题是如何透明、有效地识别 d e a d 和c l e a n 内存区域。根据实现的方法不同，又可以分为增量方式、程序号指导的区 域排除和编译器辅助的区域排除等策略。其中一些方法在后续章节中会详细阐述。 ( 4 ) 分布式检查点技术 分布式程序包括多个进程，整个程序的运行状态由每个进程的运行状态和进程间的 消息组成 1 8 1 。为保存程序的运行状态，每个进程不但要做局部检查点保存本进程的运 行状态，而且还要对进程间的消息进行同步或记录。分布式程序的检查点算法通常可分 为两类：异步检查点算法和同步检查点算法。 采用异步检查点算法，程序各进程周期性地相互独立地保存自己的运行状态和记录 所接收的报文，程序各进程间不需相互协商：在程序状态恢复过程中，各进程之间则需 要相互协商通过复杂的卷回算法各自回滚到合适的检查点时刻以使整个程序恢复到一 个一致的全局状态。异步检查点算法的优点是允许分布式程序进程拥有最大程度的自治 性，因而算法的延迟较小。其缺点是：由于每个程序进程需要保存若干时刻的检查点 文件，空间开销较大：在程序状态恢复过程中可能会重复卷回【1 9 】，最坏时出现多米 华中科技大学硕士学位论文 诺效应，使程序一直卷回到仞始状态。许多异步算法通过使用时间戳技术来防止多米诺 效应的出现，准同步算法 2 0 l 在允许分布式程序自治性的基础上吸取了同步算法的优点， 通过加入强制性检查点操作避免了多米诺效应，且该算法通过较为简单的步骤进行程序 恢复，是较为理想的异步检查点算法。 同步检查点算法也称为全局一致的检查点算法。它在程序状态保存时，需要较为复 杂的同步算法使程序各进程同步到一个全局一致时刻再对程序各进程做局部检查点。这 时程序各进程的检查点文件组成的集合就是一个一致的全局状态【2 旧”。因此，同步算法 在恢复程序状态时只需执行各进程的检查点文件。同步算法的优点是每个程序进程只需 保存最近时刻的检查点文件，空间开销较小，且程序状态恢复时没有多米诺效应。其缺 点是，在程序状态保存时由于各进程间的同步使程序运行中止时间较长，且牺牲了分布 式程序的自治性【2 玷4 1 ，同步检查点算法是目前在实际系统中较为常用的算法，其典型算 法有s n s ( s y n c a n d s t o p ) 算法和c l ( c h a n d y l a m p o r t ) 算法。 s n s 算法选取没有左交叉报文的时刻保存程序运行状态，满足全局一致时刻要求 2 。5 2 6 1 。该算法的缺点是在程序状态保存过程中需要两次全局同步，对程序的运行中止时 间比较长。但s n s 算法易于实现，因此在许多实际系统中都采用了这种算法，如 f a i 卜s a f ep v m ，m i s t 2 ”，c o c h e c k 28 1 。与s n s 算法相比，c l 算法减少了两次全局同步的 丌销。c l 算法的缺点是其控制报文的数目与机器间的拓扑结构有关。当机器间为全连 通结构时( 如用总线网相连) ，其控制报文的数目为0 ( n 为机器数) 。当n 值较大时，该 数目将不可接受。 1 3 本课题主要研究工作 本课题研究的是一个可应用于p v m 。”并行检查点系统，我们以l i n u x 为开发环境， 利用检查点技术，为p v m 并行计算环境实现了一个并行检查点系统。主要的研究内容包 括基本的检查点回滚恢复算法和任务进程间通信的一致性同步算法。概况起来包括如 下几个方面： 1 检查点回滚恢复算法 由于本课题所研究的检查点算法是基于p v m 并行计算环境的，用户程序在运行前必 须与p v m 库进行链接。因此我们在实现检查点算法时也选择了库级的方式。检查点卷 9 华中科技大学硕士学位论文 回恢复算法主要涉及了进程状态、打开文件状态的保存与恢复，信号的处理以及对系统 调用的扩充等。在检查点优化方面，采用了增量检查点技术以减少检查点文件的大小， 并采用写时拷贝技术减少检查点操作的时延。 2 任务进程间通信的一致性同步算法 要实现分布式检查点算法，不仅要完成各任务进程的进程状态的保存号恢复，还要 对进程间的通信进行同步和记录，以保证整个计算任务状态的全局一致性。我们在实现 分布式检查点算法时所采用的是同步检查点算法( 也称一致性检查点算法) 。与传统的 一致性同步检查点算法相比，本算法采用了非阻塞的一致性算法，在进行检查点操作时 避免了全局同步等待。而且，当计算节点具有多个处理器时，通过对检查点设置操作进 行交错，避免了由于多个进程同时进行检查点操作而造成对存储器的争用，减少同节 点上任务进程的冻结时间，进一步提高了系统的效率。 3 基于p v m 的并行检查点系统p c k p t 的实现 p v m c k p t 系统是对交错一致性分布式检查点算法的具体实现，并与p v m 相结合，为 p v m 提供容错【30 l 功能。其i p c 机制是基于p v m 的i p c 机制，并根据算法对其i p c 机制进 行了相应的修改。我们之所以将该算法实现为一个系统，而不仅仅是一个检查点库，一 方面是为了向p v m 提供容错能力，另一方面也为用户对并行任务的检查点设置操作进行 交互和控制提供了一个接口。为在此基础上进一步实现p v m 的进程迁移和动态负载平衡 提供了一个基本的系统框架。 本文的章节安排如下： 第一章为绪论，介绍了课题的背景、国内外研究发展概况及主要研究内容； 第二章对基本的检查点设置回滚恢复算法的实现进行了详述； 第三章对分布式检查点算法进行了综述，并介绍了基于p v m 的交错的非阻塞一致性 并行检查点算法； 第四章对p v m c k p t 的系统结构和组成进行了介绍，并对各组成部分的功能，具体实 现以及相关的数据结构和算法进行了详细的分析； 第五章对p v m c k p t 进行了功能分析和性能测试： 第六章对所作工作进行总结，并对检查点技术更进一步的完善和发展提出了探讨。 i o 华中科技大学硕士学位论文 2 检查点设置回滚恢复算法 本课题实现的检查点设置回滚恢复算法是在l i n u x 操作系统下进行研究的。因此 本章首先简单介绍u n i x l i n u x 有关进程概念的基础知识，然后对基本的检查点设置回 滚恢复算法进行详述，接着给出几种提高检查点效率的方法。 2 1u n i x l in u x 中进程的概念 从用户的角度看，程序( p r o g r a m ) 是指可执行文件，进程( p r o c e s s ) 则是指程序在数据 集上的运行实例。与进程相关的主要有以下一些概念： 1 可执行文件的格式 用户对一个程序的源代码进行编译、链接而建立的可执行文件，主要有以下部分 组成： ( 1 ) 首部( h e a d e r ) ：描述文件的属性，程序的格式及结构； ( 2 ) 程序正文( t e x t ) ：即程序的指令序列； ( 3 ) 数据( d a t a ) ：通常包括一个经初始化的数据段和一个尚未初始化的数据段 b s s ( b l o c ks t a t i cs t o r a g e ) 。初始化的数据段中，数据按其大小分配了空间，并赋有初 值；未初始化的数据段只有一个空间指示，表示核心应该为它分配多大的空间，而 该空间的分配仅在运行时进行，初始值置为0 ； ( 4 ) 其他段：诸如符号表等信息； 2 用户态和核心态 u n i x l i n u x 进程通常有两种运行态：用户态和核心态。当运行在用户态时，进程受 到限制：不能访问本进程空间以外的地址，不能直接访问外设等等，这些都只能通过系 统调用进入核心态来完成。操作系统在核心中为每个进程维护_ 些信息，通过各种系统 调用，用户可以修改其中的一些。 3 进程的上下文 进程的上下文是指进程当前的运行环境，包括描述进程的所有信息。主要由如下部 分组成：( 1 ) 用户地址空间。由正文段，数据段，栈和一些匿名内存区等组成。( 2 ) 控 华中科技大学硕士学位论文 制信息。核心为管理进程而维护的信息，包括核心栈、地址空间分布、页表，u i d 、p i d ， g i d ，打开文件信息，信号处理信息，汜帐信息，进程状态等。( 3 ) 环境变量，通常保 存在用户栈的底部。( 4 ) 硬件上下文。寄存器内容等。 4 用户地址空间的进程映象 在现代的虚存系统中，每个进程在自己的虚地址空间中运行。从用户程序的角度看， 进程的地址空间是一段线性编址内存区域，从0 开始，上限取决于硬件和操作系统。 u n i x l i n u x 核心代码将可执行文件装入内存后，用户的虚地址空间应包含以下逻辑区 段：正文段，包含程序的机器指令序列，对应于可执行文件的正文段；数据段；栈段， 由系统创建，并在运行过程中动态改变。栈由一些逻辑栈帧构成，当调用一个函数时一 个栈帧被压入栈中，函数返回时从栈顶弹出。栈帧包含函数调用的参数，函数的局部变 量，函数调用前保存的返回现场一其中包括程序计数器和栈指针的值。每个进程都有两 个栈：用户栈和核心栈。前者用于用户态执行指令，后者用于核心态执行指令。 5 信号处理机制 u n i x l i n u x 利用信号机制来通知进程发生了异步事件。每种信号都有一个缺省的处 理，多数信号缺省地使进程终止，有些信号缺省地被忽略，另一些使进程停止或继续执 行。另一方面，用户可以通过相应的库函数和系统调用，来指定信号的非缺省处理，可 以指定激活一个指定的处理过程，也可以指定忽略或恢复缺省。 当进程即将从核心态返回用户态时，或进程要进入或离开一个适当的低优先级睡眠 态时，核心检查它是否收到了信号并做相应处理。 6 进程间通信( m c ) 进程间通信机制允许任意进程交换数据和同步执行。在传统的单机u n i x l i n u x 中， 常用下列进程间通信方式：管道、命名管道、信号、信号量、消息队列、共享内存等。 随着互连网络的发展，人们又发展了许多可以支持远程进程通信的通信方式。其中基于 套接字( s o c k e t ) 进程通信机制被广泛使用。 2 2 进程状态的保存和恢复 检查点技术一般有多种实现层次，本文中我们采用的是用户级( 库级) 的检查点 技术，而且侧重于对用户透明的技术。用户级检查点技术的优点是可移植性好，易于修 华中科技大学硕士学位论文 我们采取的方法是连共享库的正文段一起保存。这样除了避免鉴别共享库外，还有 几个好处： ( 1 ) 共享库动态链接时系统不保证链接到同一地址，不保存正文并把它恢复到同一 地址就无法保证已做的链接有效。 ( 2 ) 保存恢复正文也有利于防止进程迁移时可能遇到的共享库版本不致问题。 为了安全地恢复，共享库还有一个问题要解决。从上面的分析我i l i o n 道，保存的 进程数据段中包含了一些重要的动态链接信息( g o t 表、p l t 表) 。恢复过程我们使用 m m a p m p r o t e c f f r e a d 来恢复进程映象，而这些函数通常在共享的c 库中。这样，在恢复 数据段时，如果我们先用m m a p 破坏了恢复进程的g o t 表、p l t 表，再去调用 r e a d m p