（计算机软件与理论专业论文）基于集群的并行虚拟机容错技术研究与实现.pdf

华中科技大学硕士学位论文 摘要 与传统的单机系统相比，集群系统具有更高的可扩展性、更高的性能价格比和 更高的可靠性，因而愈来愈被广泛地应用到国民经济的各个领域。随着集群系统规 模的不断扩大，集群系统内部发生故障的概率也会呈指数增长。对于集群系统内部 发生的节点机故障，一般采用优美降级的方法。但是对于运行时间较长的并行数值 计算，如在计算过程中，它所在的节点机发生故障，就会导致整个并行计算的彻底 失败，故障之前的大量计算不可再用，程序不得不从头开始执行。为了避免因为单 个故障导致整个并行计算失败而引起的计算上的大量浪费，就必须采用相应技术来 进一步提高集群系统的可靠性。而检查点技术( c h e c k p o i n t i n g ) 正是目前被国内外 广泛研究的一种用来提高集群系统高可靠性的关键技术。 检查点技术的基本思想是在系统正常运行的时刻设置检查点，保存系统当前相 关进程的进程级信息到可靠的存储器上，当系统发生故障时，将系统卷回( r o l i b a c k ) 到上一个检查点处重新执行，而不是从程序开始执行。在美国国家橡树岭实验室开 发的并行虚拟机( p v m ) 的基础之上，针对提高系统可靠性的要求，进行了内核一级 的分布式检查点技术的研究与实现工作，研制了f t p v m 原型系统。ff t p v m 原型系统 在l i n u x 核心中实现了检查点设置技术的内核支持。针对并行分希式程序的特性， 实现了分布式同步检查点设置技术。为了保证全局致性，在同步等待过程中，利 用p v m 通信的f i f o 特性，驱赶并且缓存中途消息，最终在无孤儿消息和丢失消息 的全局一致状态下建立分布式全局检查点。为了保证通信的可恢复性，实现了消息 重定向技术，确保了p v m 任务在恢复后依然能够正常通信。针对节点机发生永久性 故障的可能t 实现了检查点设置时的镜像存储技术，各节点除将其上进程的检查点 文件保多到本地磁盘外，还通过后台进程将这些检查点文件信息镜像到其它节点磁 盘上。) 这样，f t p v m 原型系统不仅实现了对于集群并行计算机系统瞬间故障的恢复， 而且也实现了对于集群并行计算机系统永久性故障的恢复，从而最终成功地实现了 集群环境下的并行计算的高可靠性。 关键词： 集辞：并行计算；容钱检查点： 、 狱 卷茵 华中科技大学硕士学位论文 a b s t r a c t c o m p a r e dw i t ht h et r a d i t i o n a ls i n g l ec o m p u t es y s t e m ，t h ec l u s t e rs y s t e mh a sh i g h e r s c a l a b i l i t y , h i g h e r r a t i oo fp e r f o r m a n c ea n dp r i c ea n dh i g h e rr e l i a b i l i t y i th a s b e e n a d o p t e dm o r ea n dm o r ew i d e l y i n m a n ya r e a s o fn a t i o n a le c o n o m y w i t l lt 1 1 es i z e e n l a r g e m e n to f t h ec l u s t e r , t h ep r o b a b i l i t yo ft h en o d ec r a s hi nt h ec l u s t e rh a sg o t t e na n e x p o n e n t i a li n c r e a s e w h e no n en o d ec r a s h e di nt h ec l u s t e r , t h ep e o p l ea l w a y sl n s u l a t e t h ec r a s h e dn o d ef r o mt h ec l u s t e r , s om a k et h ec l u s t e rs t i l la v a i l ，b u tt h ep e r f o r m a n c eo f c l u s t e rf a l l s b u ts o m e t i m e st h em e t h o dm e n t i o n e da b o v ei sn o te f f e c t i v e ，f o re x a m p l e ， w h e nw ea r er u n n i n gad i s t r i b u t i o np a r a l l e lc o m p u t i n gp r o g r a mw h i c hn e e dal o n gt i m e t of i n i s h a n dw h e no n en o d eo ft h ec l u s t e rc r a s h e s ，t h ec o m p u t i n gp r o g r a mw i l lc r a s h e s t o o ，a n dh a v et or u nf r o m t h eo r i g i n a lb e g i n n i n ga g a i n t os a v et h ec o m p u t i n gt i m ew h e n o n ef a u l th a p p e n e di nt h ec l u s t e r , w em u s ta d o p to n et e c h n i q u et oi m p r o v et h er e l i a b i l i t y o ft h ec l u s t e r t h et e c h n i q u eo fc h e c k p o i n t i n gi st h ep o p u l a rk e yt e c h n i q u ei nt h ew o r l d t h a th a sb e e nd e v e l o p e dt oa d dr e l i a b i l i t yt ot h ec l u s t e rs y s t e m t h eb a s i ct h i n k i n go ft h e c h e c k p o i n t i n gt e c h n i q u e i st os t o r et h e a p p l i c a t i o n s i n f o r m a t i o nt ot h es t a b l es t o r a g ew h e nt h ea p p l i c a t i o ni sr u n n i n gc o r r e c t l y i fa 胁l u r e o c c u r st h a tc a u s e st h ea p p l i c a t i o nt ob et e r m i n a t e dp r e m a t u r e l y , t h ea p p l i c a t i o nc a n r e s t a r tf r o mi t sm o s tr e c e n tc h e c k p o i n t ，a n dn o tf r o mt h ep r o g r a m i no r d e rt oi m p r o v e t h er e l i a b i l i t yo ft h es y s t e m ，al o to fw o r kh a v eb e e nd o n ef o c u s i n go nr e s e a r c ha n d i m p l e m e n t a t i o no f d i s t r i b u t e dk e r n e ic h e c k p o i n t i n gb a s e d o nt h ep a r a l l e lv i r t u a lm a c h i n e ( p v m ) t h a ti sd e v e l o p e db ya m e r i c a n0 a kr i d g en a t i o n a ll a b o r a t o r y t h ef t p v m p r o t o t y p es y s t e mh a v eb e e nd e v e l o p e d f t p v mp r o t o t y p es y s t e mh a sa d d e dt h e0 s k e m e lc h e c k p o i n t i n g t e c h n i q u e t ol i n u x i no r d e rf o rag l o b a lc o n s i s t e n c y , t h em e s s a g e s i n - t r a n si nt h e s y n c h r o n o u sp h a s e h a v eb e e nd r i v e na n dc a c h e d u s i n g t h ef i f 0 c h a r a c t e r i s t i co ft h ep v mc o m m u n i c a t i o n ，a n dad i s t r i b u t e dg l o b a l c h e c k p o i n t i n gh a s b e e nm a d ei nag l o b a lc o n s i s t e n c ys t a t ew i t h o u to r p h a nm e s s a g ea n di o s tm e s s a g e i n o r d e rt om a k et h ec o m m u n i c a t i o nr e c o v e r a b l e t h em e s s a g er e d i r e c t i o n t e c l l l l i q u eh a s b e e ni m p l e m e n t e da n dc a nr e c o v e rt h ec o m m u n i c a t i o n c o r r e c t l ya f t e rp v m t a s kr e c o v e r y f o rt h ep r o b a b i l i t yo ft h en o d e sp e r m a n e n tf a u l t ，t h em i r r o rs t o r a g e t e c h n i q u ea b o u t c h e c k p o i n t i n gh a sb e e ni m p l e m e n t e d ，a n da f t e rt h en o d ec o p yt h ec h e c k p o i n t i n gf i l et o t h el o c a ld i s k ，t h ef i l ec a nb em i r r o r e dt ot h eo t h e rn o d e sd i s k b y ab a c k g r o u n d p r o c e s s n l ef t p v m p r o t o t y p en o to n l yc a nr e c o v e rt h ei n s t a n tf a u l t ，b u ta l s oc a l lr e c o v e rt h e p e r m a n e n tf a u l to nt h ep a r a l l e lc l u s t e rc o m p u t i n gs y s t e m ，f i n a l l ys u c c e e d st or e a l i z et h e p a r a l l e lc o m p u t i n g o nt h ec l u s t e r s y s t e mh i g hr e l i a b i l i t y k e yw o r d s ：c l u s t e r ；p a r a l l e lc o m p u t i n g ；f a u l tt o l e r a n c e ；c h e c k p o i n t i n g ；r o l l b a c k i i 华中科技大学硕士学位论文 1 1 计算机系统容错概述 1 绪言 为了提高计算机系统可靠性，有两种基本方法避错与容错。避错( f a u l t a v o i d a n c e ) 技术靠预先排除所有故障来提高可靠性，试图构造出不包含故障的“完 美”系统，其手段是采用正确的设计与质量管理方法来尽量避免把故障引入系统， 实际上要绝对做到这一点几乎是不可能的，实践证明，避错技术的效果有一定的限 度( 比如最多使系统的平均无故障时间增加一个数量级) ，超过这个限度将使成本急 剧上升，所以单靠实施避错已经适应不了那些可靠性要求特别高的应用领域。于是， 与避错技术互补的提高计算机系统可靠性的另一种方法容错技术应运而生。 “容错”一词是a l g i r d a sa v i z i e n i s 于1 9 6 7 年在他的著名论文“d e s i g no f f a u l tt o l e r a n tc o m p u t e r s ”中首次提出的，即，如果一个系统的程序在出现故障 的情况下仍能被正确执行，那么我们称这个系统是容错的。 目前，一种被普遍接受的“容错计算机系统”( f a u l t - t o e r a n tc o m p u t e rs y s t e m ) 的定义为在出现硬件故障或软件错误的情况下仍能继续正确执行指定任务的计算 机系统。 任何可以阻止系统正常工作的事件称为一个故障( f a u l t ) 。 故障屏蔽( f a u l tm a s k i n g ) 是防止系统中所发生的任何故障向系统的信息结构 中导入差错的技术。 系统重构( r e c o n f i g u r a t i o n ) 是当系统中出现故障后把故障排除并将系统复原 到某个正常操作的条件或状态的技术。故障屏蔽与重构是实现容错的两种最基本的 途径。 个计算机系统的设计、实现及运行的各个阶段中的任何问题都可能把故障引 入到系统之中，可能的故障起因可被归纳为以下四个方面： ( 1 ) 规范错误( s p e c i f i c a t i o nm i s t a k e s ) ：包括不正确的算法、结构、软硬件 设计规范等； ( 2 ) 实现错误( i m p l e m e n t a t i o nm i s t a k e s ) ：实现是把软、硬件规范转化为物理 的硬件与实际的软件的过程，这个过程中可能会因为低劣的设计、元器件选择或软 华中科技大学硕士学位论文 件编码而引入各种故障； ( 3 ) 元器件缺陷( c o m p o n e n tb e f e c t s ) ：制造中的不完善、偶然的设备问题及元 器件老化是元器件缺陷的典型例子； ( 4 ) 外界干扰( e x t e r n a ld e f e c t s ) ：如辐射与电磁干扰、人为或自然破坏、操 作失误以及恶劣环境等； 故障般可以分为：软件故障和硬件故障；或者按其表现形式，分为偶然性( 瞬 间) 故障和永久性故障。计算机系统发生偶然性故障的失效率，通常比其发生永久 性故障的失效率高一个数量级。 故障按其影响的范围，分为局部故障和全局故障。 在容错系统的设计与开发过程中，有很多问题需要认真考虑，最基本的几点为： ( 1 ) 故障检测( f a u l td e t e c t i o n ) ，指识别出一个故障已经发生的过程，故障检 测是任何故障恢复措施所必须的前提； ( 2 ) 故障定位( f a u l tl o c a t i o n ) ，指确定一个故障所发生的位置的过程，只有 故障被定位后，才能采取适当的故障恢复措施； ( 3 ) 故障隔离( f a u l tm a s k i n g ) ，指把己发生的故障隔离开以防止它的影响在系 统中传播的过程： ( 4 ) 故障通告( f a u l tn o t i f y ) ，指把发生故障的信息通告系统其他部分的过程； ( 5 ) 故障恢复( f a u l tr e c o v e r y ) ，指故障发生后通过系统重构，从而使系统维 持正常操作或恢复到正常操作的过程。 实现容错的重要途径都是建立在资源冗余的基础上的。 冗余( r e d u n d a n c y ) 简单地说，就是超出系统正常运行所需之外的附加信息、资 源或时间。冗余的具体方式有四种：硬件冗余、软件冗余、信息冗余和时间冗余。 硬件冗余( h a r d w a r er e d u n d a n c y ) 是为检测或容忍故障而对额外硬件的附加。有 三种基本的硬件冗余形式：被动的( p a s i v e ) 、主动的( a c t i v e ) 和混合的( h y b r i d ) 。 软件冗余( s o f t w a r er e d u n d a n c y ) 可以实现许多故障检测及容错功能，这样就可 以让相应的硬件冗余降为最低。三种主要的软件冗余技术是一致性检测、能力检测 和软件重复。 信息冗余( i n f o r m a t i o nr e d u n d a n c y ) 是通过在数据中附加冗余的信息以达到故 障检测、故障屏蔽或容错的目的，如奇偶校验码、校验和( c h e c k s u m s ) 、循环码、 汉明纠错码、伯格码等检错码或纠错码，他们都是通过在数据字中附加冗余的信息 2 华中科技大学硕士学位论文 或通过把数据字映射到含有冗余信息的新的表示而形成的编码。信息冗余的优点是 所增加的冗余度比上两种方法低，可提供故障的自检测、自定位、自纠错能力，缺 点是产生时延，降低系统在无故障情况下的运算效率。 时间冗余( t i m er e d u n d a n c y ) 是近年来越来越受到人们欢迎的一种容错方式，因 为有许多应用领域中时间资源相对比较充裕，而硬件资源或软件资源却由于成本、 功耗、体积及重量等因素的限制而相对短缺，这时时间冗余就更加具有吸引力了， 其基本恩想是重复执行相应的计算以实现检错与容错，因此它所必需的硬件与软件 冗余都较少，时间冗余方式中故障的检测是关键的一环。时间冗余根据其重复计算 的级别是在指令级还是在程序段级，可被分为指令重执( i n s t r u c t i o nr e d o ) 及程序 卷回( p r o g r a mr o l l b a c k ) 两种。 要实现一个容错计算机系统，必须根据具体应用的性质、所确定的可靠性指标 和成本等因素选择适当的冗余方式，将以上这四种冗余方式的引入定到适当的级 别。 目前，在应用日趋广泛的计算机网络和各种分布式系统中也大量应用冗余技术 来提高可靠性，但通过冗余获得的容错是要靠附加资源的消耗来换取的，所以在系 统设计中，一般应在满足所需的可靠性前提下，尽量减少附加资源的消耗，这就要 求容错计算机系统的设计者不得不在权衡得失后做出一个科学的折中。 1 2 集群系统概述 随着国民经济的不断发展和社会的不断进步，社会的各个方面应用计算机系统 解决问题越来越普遍，并且对计算机系统的性能和可靠性提出了越来越高的要求。 例如，在国防领域、核工业研究领域以及气象预报部门，由于所涉及的数据量和 计算量都非常大，所以对计算机的运算能力要求很高。为了满足这种需求，传统 的解决途径是采用大型计算机，比如p a r a g o n 、银河、曙光、i b mm a i n f r a m e 等 大型机。这些大型和巨型计算机的计算能力可以达到每秒几十亿次，能够较好地 满足应用的要求。但是，这种方法的有明显的不足：成本很高，超出了一般用 户的承受范围，这主要表现在三个方面，一是购买大型计算机的成本高；二是维 护成本高：三是当扩展计算机的计算能力时。所需的成本很高。可扩展性有限， 华中科技大学硕士学位论文 随着用户自身的发展，用户希望在不浪费原有的计算机系统资源的前提下，提高 计算机系统的处理能力，这就要求计算机系统要有很好的可扩展性，但传统的大 型机系统不具备有这方面的能力。操作和维护极其复杂，表现在用户为了能够 使用这些传统的大型机系统，往往需要接受系统开发商的长时间培训或者需要系 统开发商派专员来维护。 与此同时，随着计算机技术的高速发展，高计算能力的c p u 、大容量的随机存 储器、高速网络交换设备、超大容量的磁盘存储阵列和存储局域网等新的技术突破 不断涌现。软件方面也出现了以l i n u x 操作系统为代表的源码开放的系统软件和应 用软件，各种软件技术也有很大的发展。 这样，一种被称为集群系统( c l u s t e rs y s t e m ) 的技术应运而生。最初是在美 国的n a s a 的宇航飞行中心( g o d d a r ds p a c ef 1 i g h tc e n t e r ) ，研究者用网络将一簇 ( c l u s t e r ) 基于i n t e l 芯片的运行l i n u x 的p c 机连接起来，作为一个计算能力更强 的机器协同工作。现代的集群系统是将成百上千台p c 机，通过高速网络设备互连 起来，采用先进的软件技术，使系统中的各台计算机共同承担计算任务，进行并 行计算，达到甚至超过大型机的计算能力“1 。图1 1 是集群系统结构示意图。这 个项目的名字叫b e o w u l f 。现在所有与此类似的集群系统都叫b e o w u l f 集群。由于 l i n u x 可以支持多种硬件平台，比如x 8 6 ( i n t e l ，a m d o t h e r s ) ，s p a r e ， u l t r a s p a r c ，p p c ，d e ca l p h a ，m i p s 等。采用l i n u x 和i n t e lp c 的原因是价格 便宜。但是，这并不影响集群系统有能力提供强大的计算能力。集群系统克服了大 型机存在的一些缺点，同时它还具备下面的一些优点。 一个集群计算机的组成情况如图1 1 所示，高速网络可以是以太网、a t m 、f d d i ： 节点机可以是一般的p c 机、工作站、s m p 等，其他设备可以包含磁盘阵列、s a n 、 专用监控机等；中间件可以是单一映象系统和可用性基础软件：并行编程环境可以 是p v m 、m p i 等。 集群系统还有下面的一些优点： ( 1 ) 价格便宜； ( 2 ) 可扩展性好，集群系统中的各个节点相对独立，当计算能力需要更高要 求的时候，可以方便地在集群系统中增加更多的计算节点，提高集群系统的整体 计算能力： 4 华中科技大学硕士学位论文 图1 1 集群计算机系统结构 ( 3 ) 可靠性高，它采用的容错软件技术，使系统可以在某个节点失效的情况 下，检测出故障节点，将调度到该节点的计算任务分配到其它正常工作的节点上 去，从而保证了计算的可靠性： ( 4 ) 有很好的软件支撑环境，各个计算节点以开放的l i f l u x 为操作系统平台， 加上p t ，m p i ，c c + + ，f o r t r a n 的并行软件开发环境和工具，提高了整个系 统的可用性： ( 5 ) 有较高的易用性。 1 3 并行虚拟机p v m 概述 p v m ( p a r a l l e lv i r t u a lm a c h i n e ) 。“”1 是目前比较流行的一种可移植的支持消 息传递方式的并行编程环境。p v m 是由美国国家基金会资助，由美国国家橡树岭实 验室研制的，1 9 8 9 年夏开始研发，2 0 0 1 年秋推出了最新的版本3 4 4 版。现在在 u n i x 、l i n u x 、w i n d o w s 等几乎所有通用的操作系统上都支持p v m 。用p v m 可以构造 一个全互联节点集的虚拟机，每个节点可以是大规模并行处理机m p p 、对称多处理 机s m p 、分布式共享存储器机d s m 或者是台简单的p c 机。用户可以动态地创建和 管理许多进程在虚拟机上运行。p v m 提供了支持进程间通信的函数库以及其他函数 华中科技大学硕士学位论文 厍。 p v m 有以下特点： ( 】) 支持多用户及多任务：多个用户可以同时使用，每个用户执行多个应用程 序： ( 2 ) 易于编程，提供了丰富的函数库，支持c 、f o r t r a n 高级语言： ( 3 ) 支持进程组的概念，进程组可以动态变化； ( 4 ) 支持异构环境： ( 5 ) 有较好的可扩展性； ( 6 ) 提供了初步的容错功能，可以自动删除故障节点； ( 7 ) 属于自由软件，源代码公开。 由于p v m 具有以上特点，尤其是可以使用一般的p c 机做节点机，可以在同构 异构型网络环境下模拟实现一个通用的基于分布式存储的并行计算系统，提供基于 传递的并行程序设计接口，这样只需要少量的投资就可以建立起一个性能不错的并 行处理环境，所以p v m 在科研部门和教育部门应用非常广泛。 1 4 检查点技术概述 设置检查点( c h e c k p o i n t i n g ) “是计算机系统进行故障恢复的主要手段之一。 系统( 周期性地) 把运行时的正确状态保存到稳定存储器( s t a b l es t o r a g e ) 中；在 必要时，系统可以卷回( r o l i b a c k ) 到设置检查点时的正确状态继续执行“”“。在多 种应用场合，我们都可以看到检查点( c h e c k p o i n t ) 这个术语，比如：f t p 文件传输 中的检查点、数据库恢复中的检查点、双机热备份中的检查点、进程迁移中的检查 点等等“5 1 ”，这些不同的检查点的含义不尽相同，但基本上分为三类：进程级检查 点、数据级检查点和事务处理级检查点。本文所用到的检查点( c h e c k p o i n t ) ，如果 不加特别说明，都是指第一种检查点，即进程级检查点。 设置检查点可以在三个不同的层面上上来实现，具体如下： ( 1 ) 在操作系统核心层内设置检查点，称为内核级检查点。不需要程序员或者 用户来干预，直接由操作系统来设置检查点。现在所有的商用的操作系统本身都不 支持设置检查点的功能，只有少数的实验室产品支持设置检查点，诸如：u n i c o s “”、 k e y k o s “、m a c h “w 、n o m a d t 捌等等。 6 华中科技大学硕士学位论文 ( 2 ) 在用户层透明地设置检查点，称为库级检查点。开发一些设置检查点的函 数库，不修改源程序，但需要把应用程序的源代码重新编译，并且需要链接设置检 查点的函数库。这样，程序自身就可以完成设置检查点。由于这种设置检查点的方 法是在操作系统之上实现的，因此，操作系统自身的某些状态是否可以恢复 ( r e c o v e r a b i l i t y ) ，成为了限制设置检查点技术的应用范围的一个重要问题。在 大多数操作系统中，有些状态是不可以恢复的，比如，进程的进程号p i d 、被应用 进程打开的文件的操作系统核心内的数据结构、系统的时钟。这使得对于某些有着 特定需求的应用程序来说，检查点设置在用户层是不能够实现的。 ( 3 ) 在用户层非透明地设嚣检查点。为了获得设置检查点的功能，程序员需要在 源程序中插入设置检查点的代码，调用检查点的库函数或者是预定义的宏，以及在 适当的地方插入恢复进程的代码。这种非透明的设置检查点的方式，增加了程序开 发的复杂度，尤其是对初级程序员而言，在不正确的时候或者是不正确的地方加入 了设置检查点的代码，会产生严重的后果，轻的可能是性能严重下降或者是耗用大 量资源，重的可能是使应用程序异常终止，更严重的可以使整个系统完全崩溃。任 何方法都有其不利的一面，也定有其有利的面，这种非透明的设置检查点方法 也不例外。程序员可能会很痛苦的思考如何成功地加入设置检查点代码，但是，一 旦程序员掌握了必要的技巧和对整个应用的程序有了完全的了解，只需加入少量的 代码，就能够获得比透明的设黄检查点方法高得多的性能，同时只需要消耗较少的 系统资源。 检查点技术在许多领域都有重要的应用： ( 1 ) 容错。检查点技术最主要的应用是容错。通过周期性地把应用进程信息保 存到磁盘，一旦应用进程异常终止或者检测到故障时，系统就卷回( r o l l b a c k ) 到 前一个检查点时的正确状态继续执行，这样就避免了因故障而导致的任务从头重新 执行，因而有效地减少了损失的工作量。国外有研究证明在故障条件下，如果不使 用检查点，任务平均执行时间随任务的有效执行时间( 假设不发生故障时的执行时 间) 呈指数增长，而使用固定间隔的检查点，则呈线性增长。实际上，当故障率超 过一定值，使两次故障的平均间隔小于任务的有效执行时间时，如果不使用检查点， 任务很难完成。 ( 2 ) 进程迁移。目前大多数操作系统不能提供进程迁移功能，利用检查点可以 保存进程在某台机器上的运行状态，然后在其他机器上恢复进程的运行以实现进程 华中科技大学硕士学位论文 迁移。 ( 3 ) 卷回调试m ，。在程序调试过程中，利用检查点保存程序在多个时刻的运行 状态，当错误发生时，把程序卷回到保存的某个时刻的状态重新向下运行，以再次 产生同样的错误来检查错误发生条件的调试方法成为卷回调试。分布式程序包含较 多的不确定成份，当发现运行错误重新运行程序查找错误原因时，同样的错误可能 很难再次出现。利用卷回调试会在很大程度上提高错误再次发生的概率。 1 5 国内外研究现状 检查点技术是一种多用途的技术，适用于进程容错、卷回处理和进程迁移等多 个方面，它既是当今计算机界研究的一大热点，也是一大难点，各国在该领域进行 了大量的工作，如c h a r m “、l i b c k p t 啪1 、c o n d o r 阱1 、c o c h e c k “等等。 c h a r m 由清华大学开发，在p v m 环境下，一个基于检查点的卷回恢复与进程迁 移系统。它拥有以下功能和特点： ( 1 ) 自动恢复节点瞬时永久故障； ( 2 ) 采用并行和增益的检查点设置方式，减小系统正常运行代价： ( 3 ) 同时支持容错与进程迁移； ( 4 ) 在用户级实现，使用标准u n i x 系统调用，不修改u n i x 内核，不需要额外 硬件支持，适用于不同u n i x 版本： ( 5 ) 对用户程序透明，系统以运行库形式提供给用户。用户使用时只需将其应 用程序目标文件与c h a r m 提供的静态库链接，即可用命令方式或自动方式使用系统 的容错以及进程迁移等功能。 ( 6 ) 在并行计算环境通信库之上实现，具有一定可移植性。 l i b c k p t 由t e n n e s s e eu n i v e r s i t y 开发，它提供了一个检查点技术简单实现的 静态库。 c o n d o r 由w i s c o n s i nu n i v e r s i t 开发，一个异构分布式作业调度系统。它利用 将大计算量任务派至远程空闲机执行的方式，把空闲工作站的c p u 资源配给其他用 户。c o n d o r 的特点在于它能够利用检查点设置实现了进程迁移以达到负载平衡和容 错的目的。c o n d o r 系统监视局域网中工作站的负载情况，将处于空闲状态的机器加 入动态资源缓冲区中。需要c p u 资源的用户可以申请获得空闲机器。它具有以下特 华中科技大学硕士学位论文 点：( 1 ) 使用c o n d o r 时，不需要进行特殊的程序设计。 ( 2 ) 当机器b 上的任务被派到机器c 上执行时，此任务使用的是机器b 上 的执行环境。c o n d o r 保证这个任务不会接触到机器c 的文件系统，这样可保证机 器c 的系统安全。 ( 3 ) c o n d o r 可以自动寻找并分配空闲工作站。 ( 4 ) 工作站的主人对自己的工作站有绝对控制权。 ( 5 ) c o n d o r 完全在操作系统核外实现。 c o n d o r 的功能是较强的。如果在工作站网络中适当地使用c o n d o r ，工作站的 空闲处理能力将会在保证系统安全的前提下以更高的效率得到发挥，提高系统资源 利用率，缩短作业响应时间，用户也不会感到不便。 c o c h e c k 由德国慕尼黑大学开发，采用c o n d o r 的检查点库，在p v m 上实现的一 个的卷回恢复与进程迁移系统。 1 6 本文的研究内容和论文组织 本文的研究内容是关于基于集群的并行虚拟机上的容错技术的研究与实现。 在后面的内容中，我们可以看到容错技术对于集群计算是非常重要的。我们提出 和分析了检查点技术中的几个关键问题，以及几种不同的实现算法，和它们之间 的优缺点。我们针对集群环境下分布式并行计算对容错的要求，设计并实现了 f t p v m ( f a u l tt o l e r a n c ep a r a l l e lv i r t u r a lm a c h i n e ) 原型系统。f t p v m 原型系 统采用并且实现了以下关键技术：内核级检查点技术、分布式同步检套点技术、 消息重定向机制、中途消息缓存机制、故障检测技术、系统重构技术和故障自动 恢复技术等等。 本文分为以下六章： 第一章是绪言，介绍了计算机系统容错问题、集群系统特点、检查点技术、 国内外的研究现状以及我们的研究重点。 第二章是详细阐述了检查点技术中的几个关键问题，对比说明了不同的实现 算法。 在第三章中，我们详细分析了并行虚拟机p v m 的实现机制、通信协议以及已 经具有的初步容错功能以及存在的不足。 华中科技大学硕士学位论文 第四章介绍了的容错并行虚拟机系统f t p v m 的设计与实现方法。 第五章是对f t p v m 系统进行性能评价与分析。 第六章是结束语，对本文进行了总结。 华中科技大学硕士学位论文 2 进程的检查点技术 本文讨论和实现的容错技术，主要是建立在检查点技术之上本章集中讨论单 进程检查点算法和分布式检查点算法，分布式检查点算法中的同步检查点算法和异 步检查点算法，以及其他几个关键问题。 2 1 单进程检查点算法 一个进程的状态主要包括它的内存空间、各寄存器的值( 如图2 1 所示) 以及其 它信息，比如相关联的文件系统状态、进程间通信数据、网络通信数据等等。进程 的内存地址空间分为四个部分：正文段、数据段、堆和栈。其中数据段、堆和栈需 要同c p u 寄存器值一起备份到检查点的文件中去，而正文段在需要恢复时t 可以由 程序的可执行文件恢复。 栈 堆 数据段 代码段 内存检查点文件寄存器 图2 1 单进程检查点备份示意图 2 1 1 l i n u x 进程核心地址空间 l i n u x 进程占用核心地址空间。”的情况如图2 2 所示，主要包括t a s k s t r u c t 华中科技大学硕士学位论文 数据结构和核心堆栈，并且两者被保存在两个连续的物理页面上。 两个连续的物理页面 ( 8 k b ) - 、 | i系统空间堆栈( 划j 7 k b ) 1 i i i s t r u c tt a s k s t r u c t ( 大约1 k b ) 图2 2 进程核心地址空间示意图 l i n u x 中的每一个进程由一个t a s k s t r u c t 数据结构来描述，t a s k s t r u c t 就是 操作系统中通常说到的进程控制块( p c b ，p r o c e s sc o n t r o lb i o c k ) 。t a s k s t r u c t 容纳了一个进程的所有信息，是系统对进程进行控制的唯一有效的手段。 当系统创建一个进程时，l i n u x 为新的进程分配一个新的t a s k s t r u c t 数据结 构，c u r r e n t 指针总是指向当前进程的t a s ks t r u c t 。 t a s k s t r u c t 数据结构包含有大量的数据信息，按功能的不同可以分为： 进程状态( s t a t e ) ； 进程调度信息( s c h e d u l i n gi n f o r m a t i o n ) ； 各种标识号( i d e n t i f i e r s ) ： 进程通信有关信息( i p c ，i n t e r p r o c e s sc o m m u n i c a t i o n ) ； 时间和定时器信息( t i m e sa n dt i m e r ) ： 进程链接信息( l i n k s ) ； 文件系统信息( f il es y s t e m ) ： 虚拟内存信息( v i r t u a lm e m o r y ) ： 处理器相关的环境( 上下文) 信息( p r o c e s s o rs p e c i f i cc o n t e x t ) 。 i n t e l 在i 3 8 6 系统结构的设计中增加有一个新的段，叫任务状态段t s s ，用来 支持进程间的切换。但是l i n u x 内核实际上并不使用i 3 8 6 c p u 硬件提供的任务切换 华中科技大学硕士学位论文 机制，即不使用c p u 内的t s s ，而是在系统空间堆栈中申请了部分空间存放 t s s s t r u c t 数据结构。内核在每个进程切换时，把寄存器的值保存在各个进程自己 的系统空间堆栈中，即t s s s t r u c t 数据结构中。 2 1 2p c b 结构的备份 p c b 结构的备份是指备份进程的t a s k s t r u c t 数据结构中的信息。 所有指向进程的t a s k s t r u c t 数据结构的指针存放在p i d h a s h p i d h a s h s z 哈 希表中，内核中提供了一个函数s t r u c tt a s k s t r u c t 十f i n d - t a s k b y _ _ p i d ( i n t p i d ) ，可以直接根据进程号p i d 得到指向进程号为p i d 的进程的t a s k s t r u c t 数 据结构的指针。如果我们要对该进程进行备份，我们就将这个指针所指向的 t a s k s t r u c t 数据结构写入检查点文件。 p c b 结构备份算法： d u m p t a s k ( 检查点文件f d ，进程p i d ) i f ( f i n d t a s k b y _ p i d ( 进程p i d ) = = 空) 出错返回： e s e ( 获得指向进程p i d 的t a s k s t r u c t 结构的指针p ； 写t a s k s t r u c t 结构的相关项到检查点文件f d ； 2 1 3 寄存器的备份 寄存器上下文：程序寄存器、处理机状态寄存器、栈指针、通用寄存器的值。 当进程处于不同的状态时，寄存器上下文存放的地方不同。在用户态下，寄存器上 下文是存放在用户地址空间中的栈中：在核心态下，寄存器的值保存在核心地址空 间的栈中。在用户态下，寄存器的备份可以通过下一节的对用户地址空间备份来实 现。在核心态下，l i n u x 内核里定义有s t r u c tp t r e g s 数据结构，如图2 3 所示， 其中各项对应与系统存储在核心栈中的各个寄存器。 华中科技大学硕士学位论文 e a x e b x e c x e d x e s l e d i e b p e s p l o r l g _ e a x x d sx e s x c sx s s - e l p e f l a g s 通用寄存器 段寄存器 指令寄存器 状态寄存器 图2 3s t r u e tp t r e g s 数据结构示意图 因而，我们备份s t r u c tp t r e g s 数据结构到检查点文件中去，即可完成对核，巴 态下寄存器值的备份。 寄存器备份算法： d u m p r e g i s t e r s ( 检查点文件f d 写p t r e g s 结构的相关项到检查点文件f d ) 2 1 4 用户地址空间的备份 进程的用户地址空间由正文段、数据段、堆、栈和共享段组成。每段又由各自 的一个的个页表完成从虚拟地址到物理地址的映射。在进程的t a s k s t r u c t 结 构中包含一个指向m m _ s t r u c t 结构的指针。进程的m m _ s t r u c t 则包含装入的可执行 映像信息以及进程页目录指针p g d 。该结构还包含有一个指向v 册_ a r e a _ s t r u c t 结构 的几个指针，每个v ma r e a _ s t r u c t 代表进程的一个虚拟地址区域。如图2 4 所示。 1 4 华中科技大学硕士学位论文 图2 4 进程虚拟地址示意图 进程虚拟内存空间备份算法： d u m p v m ( 检查点文件f d ) 获得指向进程的m m _ s t r u c t 结构的指针； 写m m _ s t r u c t 结构的相关项到检查点文件f d ； f o r ( 由m m a p 指向的虚拟地址区链表的首地址，遍历链表) 华中科技大学硕士学位论文 写v m _ a r e a s t r u c t 结构的相关项到检查点文件f d ： 获得对应的虚拟地址连续块的起始地址、结束地址和大小