（计算机应用技术专业论文）基于linux内核的进程检查点技术研究.pdf

哈尔滨j 】j 程大学硕+ 学何论文 摘要 随着计算机技术的不断进步，并行与分布式计算得到了飞速发展，并广 泛应用于科学计算、信息处理和移动通信，特别是高性能计算等领域。随着 系统规模的增长、应用程序复杂度以及运行时间增加等原因，系统出错的概 率大大增加。为保证系统的高可靠性，容错技术被广泛采用并且成为目前计 算机研究领域的一个热点。 软件容错因其具有较强的灵活性及实现费用低的特点，被越来越多的应 用到不同领域。作为一种流行的软件容错机制，检查点与恢复技术的实现思 想是在程序正确运行的过程中定期保存进程状态、生成检查点文件，当系统 出现故障时，将出错进程卷回到最近的检查点处继续执行。检查点与恢复技 术的实现模式有两种：基于用户级的检查点系统和基于内核级的检查点系统。 本文通过分析这两种模式的检查点系统实例说明了两者各自的优缺点。 根据l i n u x 可加载内核模块机制提出一种基于l i n u x 内核的进程检查点与恢复 系统h d c r 的设计与实现方案，利用l i n u x 内核线程实现了检查点设置与恢复 内核模块，将此模块加载至i j l i n u x 内核层以提供底层检查点设置及进程恢复机 制。基于此内核模块在用户层构造了一个检查点函数库，为用户提供相应接 口，用户通过组合使用这些接口可以高效地实现具体检查点与恢复算法。本 文还提出了一种并行环境下进程同步过程实现算法：p a r a l l e l s y n c 算法，确保 检查点状态达到全局一致。 实验结果表明，该检查点系统能够对用户进程进行透明、高效的检查点 采取操作，并能进行无错卷回恢复、支持用户具体的检查点策略。说明系统 具有可靠性、高效性和灵活性。 关键词：容错；检查点与恢复；用户级；系统级；内核模块 哈尔滨t 程入学硕十学位论文 a b s t r a c t w i t ht h e i n c r e a s i n gd e v e l o p m e n to fc o m p u t e rt e c h n o l o g y , p a r a l l e la n d d i s t r i b u t e dc o m p u t i n gh a sa c h i e v e dg r e a ta d v a n c e sa n di su s e dw i d e l yi ns c i e n c e c o m p u t i n g ，i n f o r m a t i o np r o c e s s i n ga n dm o b i l ec o m m u n i c a t i o n ，e s p e c i a l l yi nt h e f i e l do fh i g h p e r f o r m a n c ec o m p u t i n g t h er a t eo fs y s t e mf a u l t si n c r e a s e s c o r r e s p o n d i n g l yb e c a u s eo ft h eg r o w t ho fs y s t e ms c a l e ，t h ec o m p l e x i t ya n d r u n - t i m eo ft h ea p p l i c a t i o na n ds oo n 。a sar e s u l t ，i no r d e rt oe n s u r et h eh i g h r e l i a b i l i t yo ft h es y s t e m ，f a u l tt o l e r a n tt e c h n o l o g yh a sb e e nw i d e l ya d o p t e da n d h a sb e c o m ea h o t s p o ti nt h ef i e l do fc o m p u t e rr e s e a r c h s o f t w a r ef a u l tt o l e r a n c ei si n c r e a s i n g l ya p p l i e di nv a r i o u sa r e a sb e c a u s eo f i t sc h a r a c t e r i s t i c so fs t r o n gf l e x i b i l i t ya n dl o wc o s to fi m p l e m e n t a t i o n a sa p o p u l a rs o f t w a r ef a u l t t o l e r a n tm e c h a n i s m ，t h em a i ni d e ao fc h e c k p o i n ta n d r e c o v e r yt e c h n i q u ei sp e r i o d i c a l l ys a v i n gt h es t a t e so fp r o c e s s e sa n dg e n e r a t i n g c h e c k p o i n tf i l e sd u r i n gf a u l t f r e e ，a f t e ro c c u r r e n c eo ff a u l t ，t h i sm e c h a n i s mr o l l s b a c kt h ee r r o rp r o c e s st ot h er e c e n tc h e c k p o i n ts t a t ea n dr e s t a r tt h ec o m p u t a t i o n p r o c e s s c h e c k p o i n ta n dr e c o v e r yt e c h n i q u ec a nb ei m p l e m e n t e di nt w om o d e s ： u s e r - l e v e ls y s t e ma n dk e r n e l - l e v e ls y s t e m t h r o u g ha n a l y z i n ge x a m p l es y s t e m so ft h et w om o d e s ，t h ea d v a n t a g e sa n d d i s a d v a n t a g e so ft h et w om o d e sa r ed i s c u s s e d b a s e do nt h ea b o v ea n a l y s i s ， a c c o r d i n gt ot h el i n u xl k m ( l o a d a b l ek e r n e lm o d u l e ) m e c h a n i s m ，am e t h o dt o d e s i g na n di m p l e m e n tap r o c e s sc h e c k p o i n ta n dr e c o v e r ys y s t e mh d c r b a s e do n t h el i n u xk e r n e li sp r o p o s e d c h e c k p o i n ta n dr e c o v e r y k e r n e lm o d u l ei s i m p l e m e n t e du s i n gt h el i n u xk e r n e lt h r e a da n dl o a d e di n t ot h el i n u xk e m e l l e v e l t op r o v i d et h eb o t t o mm e c h a n i s mo fc h e c k p o i n ta n dr e c o v e r y b a s e do nt h i s k e r n e lm o d u l e ，ac h e c k p o i n tl i b r a r yi sc o n s t r u c t e di nt h eu s e r - l e v e lt op r o v i d e c o r r e s p o n d i n g i n t e r f a c e sf o ru s e r s ，b y u s i n g s o m es e l e c t e di n t e r f a c e s ，t h e p a r t i c u l a rc h e c k p o i n ta n dr e c o v e r ya l g o r i t h mc a nb ei m p l e m e n t e de f f e c t i v e l y f u r t h e r m o r e ，a na l g o r i t h mn a m e dp a r a l l e l s y n ci sp r o p o s e d ，i tc o u l dw o r ku n d e r 哈尔滨下程大学硕十学位论文 p a r a l l e lc o n d i t i o nt oe n s u r et h ec h e c k p o i n t s s t a t e sa c h i e v i n gag l o b a lc o n s i s t e n t s t a t e t h ee x p e r i m e n td a t ad e m o n s t r a t et h a tt h es y s t e mi sa b l et od ot r a n s p a r e n t a n dh i g he f f i c i e n t l yc h e c k p o i n to p e r a t i o nf o ru s e rp r o c e s s e s ，d or o l lb a c kr e c o v e r y w i t h o u tf a i l u r ea n dt h es y s t e ma l s os u p p o r t ss p e c i f i cc h e c k p o i n ta l g o r i t h m sf o r u s e r s a l lt h e s ed e m o n s t r a t et h a tt h es y s t e mi sah i g hd e p e n d a b l e ，h i g he f f e c t i v e a n df l e x i b l es y s t e m k e yw o r d s ：f a u l tt o l e r a n c e ；c h e c k p o i n ta n dr e c o v e r y ；u s e rl e v e l ；s y s t e ml e v e l ； k e r n e lm o d u l e 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下， 由作者本人独立完成的。有关观点、方法、数据和文献的引用 已在文中指出，并与参考文献相对应。除文中已注明引用的内 容外，本论文不包含任何其他个人或集体已经公开发表的作品 成果。对本文的研究做出重要贡献的个人和集体，均已在文中 以明确方式标明。本人完全意识到本声明的法律结果由本人承 担。 名i 作者( 签字) ：骘u 日期：弘叩年 月b 日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生 在校攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈 尔滨工程大学有权保留并向国家有关部门或机构送交论文的复印 件。本人允许哈尔滨工程大学将论文的部分或全部内容编入有关 数据库进行检索，可采用影印、缩印或扫描等复制手段保存和汇 编本学位论文，可以公布论文的全部内容。同时本人保证毕业后 结合学位论文研究课题再撰写的论文一律注明作者第一署名单位 为哈尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 阻在授予学位后即可口在授予学位1 2 个月后 口解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：修扔导师( 签字) ：j 、- - 辆己 日期：钐砷年乡月b 日加斗年；月归 。 。| 哈尔滨t 程人学硕十学位论文 第1 章绪论 1 1 论文研究背景及意义 随着计算机技术进一步渗入社会生活的各个方面，社会生产和人们生活 对计算机的依赖性日益增加，自然科学研究中的计算任务、工业控制和设计、 军事领域的研究与发展、商业贸易甚至人们的日常生活娱乐都无法脱离计算 机。与此同时产生的问题是计算机的可靠性问题，在某些高科技领域，可靠 性计算既是保证正确计算结果的必要条件，又是节省程序运行时间、提高计 算机资源利用率的手段。而提高计算机可靠性有两个途径：排错和容错。排 错是避免故障的各种技术的统称，由于系统复杂程度以及领域问题复杂程度 的不断增加，排错技术的效果有很大的限度，于是提高计算机可信度的另一 途径一容错技术应运而生。 容错分为硬件容错和软件容错。目前，软件容错的研究还没有达到硬件 容错的深度，在实际应用中也没有达到硬件容错的广度。尽管如此，软件容 错技术的研究还是在一步一步的取得进展并逐步进入了使用阶段。检查点与 恢复( c h e c k p o i n ta n dr e c o v e r y ) 机制是一种典型的软件容错技术，一方面它应 该具有定期备份进程状态的功能( 将那些在进程运行过程中的某一时间点处 保存的进程状态文件称为检查点文件) ，另一方面当操作系统出现故障或外部 差错而导致某些进程终止或计算错误时，它可以加载检查点文件将用户进程 卷回到最近的检查点处从而实现进程状态的恢复【2 】。恢复后的进程可以从此 检查点处继续执行，如图1 1 所示。这样可以避免由于故障而导致的程序从头 重新执行，因而能有效的减少计算损失，提高计算机系统资源利用率。容错 技术也为提高计算机系统的可靠性提供了一个有效手段。 可靠性( r e l i a b i l i t y ) 是衡量计算机系统整体性能的一项重要指标。计算机 哈尔滨t 程大学硕十学何论文 系统的可靠性可以用平均无故障时f n j ( m e a nt i m eb e t w e e nf a i l u r e ，m t b f ) 来 度量，即计算机系统平均能否正常运行多长时间，才发生一次故障。系统的 可靠性越高，平均无故障时间越长。可维护性用平均维修时间( m e a nt i m et o r e c o v e r y ，m t t r ) 来度量，即系统发生故障后维修和重新恢复正常运行平均 花费的时间。系统的可维护性越好，平均维修时间越短，因此计算机系统的 可用性( a v a i l a b i l i t y ) 可用如下公式表示； a v a i l a b f l i t y ：塑! 1 0 0 ( 1 - 1 ) 程序正常运行检查点设置出错 图1 1 检查点设置和卷回恢复技术 把这种容错机制具体化，并且用代码实现就形成检查点系统，检查点系 统主要包括进程状态备份程序和进程状态恢复程序 3 - 6 ，其恢复技术主要采取 的是一种向后恢复策略i ，l 。 检查点系统主要有两种设计模式：用户级( u s e rl e v e l ) 和核心级( k e r n e l l e v e l ) 。基于用户级设计模式实现的系统通常具有较好的可移植性，但是缺 乏通用性、透明性和可扩充性；基于核心级的设计模式在实现后功能上通常 更完善、通用性较强、透明性也好，但是不同系统间的实现形式差异较大， 且缺乏灵活性i s o l 。关于这两种模式的检查点系统的国内外研究现状以及两者 之间的详细比较将在第二章阐述。 从理论上来讲，检查点系统应该属于操作系统核心的容错子系统郴】，但 是由于检查点的实现要求软件和硬件上都有一定的冗余，而且在集群系统的 哈尔滨t 释大学硕十学位论文 广泛应用之前，没有足够的用户需求。所以它一直是各个o s 厂商所忽略的问 题之一。同样，核心级检查点系统的发展也就相应的晚于用户级检查点系统 的发展。随着集群系统的规模扩大以及分布式系统的广泛应用，检查点成为 必不可少的技术环节，而用户级实现的检查点系统缺乏通用性，很大程度上 限制了应用程序的范围，这就带来了核心级检查点机制需求。p o s i x l 0 0 3 1 是i e e e 镱i 定的规范操作系统检查点系统接口的规范，s g i 推出的i r i x 6 4 p 3 1 正是 依照p o s i x 实现了检查点的典范。同时随着开放源代码软件的风行世界，开 始有人自己向开放源码的o s 中添加检查点功能模块，但是如何在操作系统内 核中支持检查点技术本身不是十分成熟的技术，还远远没有达到稳定推广使 用的地步。 此外，论文选择l i n u x 操作系统作为载体是因为l i n u x 在h p c ( 高性能计算) 领域内的巨大优势。具体体现在硬件要求低、软件成本低、并行代码多、开 源工具多、可定制性好以及维护成本低等。安全性高、运行稳定、价格低廉 以及环境要求较低等已成为l i n u x 操作系统的代名词。据统计，2 9 的互联网 服务器都采用了l i n u x 系统。另外，从2 0 0 7 年1 1 月份统计的h p ct o p 5 0 0 数据 中可以看到选择l i n u x 操作系统的份额占全部操作系统种类的8 5 2 0 v 】，由此 更可以看出l i n u x 在h p c 领域的优势。 目前，国内外部分专家、学者都在计算机容错这一领域进行着深入的研 究，也取得了不少成果，推动了此领域的发展1 1 5 1 。但是，容错技术还远远没 有达到稳定推广使用的地步，因此，继续深入研究使计算系统具有更高可靠 性和高效的性能，将会极大推动容错技术的应用和发展。 1 2 论文主要研究内容介绍 本论文课题来源于国家自然科学基金资助项目：移动计算环境的故障恢 复机制研究( 资助编号：n o 6 0 8 7 3 1 3 8 ) 。 本文主要的研究内容是以l i n u x 操作系统为载体，基于检查点技术的理 哈尔滨丁稗人学硕十学位论文 论分析以及国内外成功案例的基础之上，通过对l i n u x 操作系统的深入研究、 通过分析现有检查点系统各自的优缺点，利用l i n u x 可加载内核模块机制 ( l k m ) 提出自己的一种基于l i n u x 内核的检查点系统设计与实现方案。包括 系统结构原型、工作原理、工作流程、几个主要检查点采取操作的算法实现 以及主要的函数接口实现等。在实现一个可加载和移除的检查点与恢复内核 模块来对用户应用程序提供采取检查点或恢复操作底层机制的基础之上，在 用户层构造一个检查点函数库，此函数库基于检查点与恢复内核模块实现， 为用户提供了相应接口。用户通过组合使用这些接口可以高效地实现具体的 检查点与恢复算法。 此外，本文还介绍了此检查点系统在并行与分布式系统中的应用，着重 解决了并行系统中各个节点上的进程由于进程间通信而带来的采取检查时的 不一致问题。提出了一种并行环境下采取检查点时各并行进程之间同步过程 实现方法。 1 3 论文组织结构 论文共分5 章，组织结构安排如下： 第1 章叙述了检查点与恢复技术作为一种流行的软件容错机制的研究背 景以及研究意义，概括介绍了本论文主要研究内容。 第2 章介绍了进程检查点设置与卷回恢复技术的相关知识。包括检查点 设置与卷回恢复技术概述、进程状态保存的相关技术基础、进程检查点与恢 复算法相关知识、检查点技术的研究现状以及一个良好的检查点系统需要注 意的几个问题。 第3 章提出了一种基于l i n u x 内核的进程检查点系统设计方案。结合 l i n u x 进程的概念以及l i n u x 可加载内核模块机制详细介绍了系统设计基本 原理、系统结构图、系统工作流程，并提出了一种并行环境下采取检查点时 各并行进程之间同步过程实现算法。利用此算法可使并行环境下的检查点达 4 哈尔滨1 ：程大学硕十学位论文 到全局一致性状态。 第4 章主要是系统的实现部分，详细介绍了检查点与恢复内核模块的实 现和用户层上检查点函数库的实现，给出了内核模块主要函数以及检查点库 主要接口函数的实现。 第5 章是系统评价部分。从两方面来对系统进行评价：系统功能评价和 系统性能评价。系统功能评价是看该系统是否能够完成预期的检查点采取及 卷回恢复功能以及是否能与用户层上的检查点库相结合来实现用户策略支持 功能。性能评价是与已有的检查点系统作对比，从检查点采取开销和检查点 状态完整性方面进行评价。 最后是文章的结论部分。对本文工作进行了总结，提出文章的不足之处 并对今后进一步的研究工作进行了展望与设想。 哈尔滨丁稃大学硕+ 学位论文 第2 章进程检查点与卷回恢复技术 2 1 检查点设置与卷回恢复技术概述 检查点设置和卷回恢复( c r r ，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 y ) 技术 是常用的后向容错恢复技术f 2 】，它通过时间冗余以达到容错目的。概括说来， c r r 技术包括以下两个方面： ( 1 ) 检查点设置( c h e c k p o i n t i n g ) 。在程序正常运行过程中，由程序员或操 作系统指定，在程序运行的适当时刻设置检查点，保存进程当时的规范状态。 ( 2 ) 卷回恢复( r o l l b a c kr e c o v e r y ) 。故障发生或程序运行出现非预期结果 后，将进程状态设置为由某些检查点组成的一致性全局状态，并从此状态继 续运行。 c r r 技术在实际应用中主要有以下三种功能： ( 1 ) c r r 技术是自动恢复瞬时和间歇故障的有效手段。瞬时性或间歇性 的功能失常往往在重复执行时自动消失，因此，使用c r r 技术可使系统从因 这类故障引起的失败中自动恢复。其次，它是恢复永久故障的重要辅助手段。 永久故障发生后，有两种恢复途径，一是待故障机故障被排除后，在原机上 进行卷回恢复；二是可将故障机上检查点文件传到其他功能正常的机器上， 或者直接通过建立在其它机器上的检查点，在其它机器上进行卷回恢复。无 论是何种途径，都要以基本的检查点设置和卷回恢复技术为基础。 ( 2 ) 利用c r r 技术实现进程迁移。通过在原机设置检查点而在目的机卷 回恢复，可以实现进程迁移。迸程迁移，即在一个计算机上运行的进程，把 它的状态通过网络传输到另一台计算机上，并在这台计算机上恢复该进程的 状态并继续执行，而原来的进程则停止运行。由于进程迁移技术能动态的改 变系统的负载分布，所以它是动态负载平衡以及智能资源管理的基础技术。 6 哈尔滨t 程人学硕十学位论文 ( 3 ) 利用c r r 技术实现系统资源负载平衡。在实现进程迁移技术的基础 之上，可以实现系统的运行时动态自动重构。在发生故障时，利用检查点设 置和卷回恢复技术可以把系统状态卷回到一个规范状态并重新开始执行。与 故障检测相结合，就可以及时的发现错误，在无入工干预的情况下进行相应 处理以隔离故障结点，同时进行系统重构，并利用保存的规范状态恢复应用 程序继续运行。即使没有发生错误，在需要增加或者减少计算资源的时候， 也可以利用进程迁移技术将全部的计算任务在各结点之间进行重新分配，从 而实现自动负载平衡，达到充分利用计算资源的目的。 2 2 进程状态的保存和恢复 对c r r 技术的首要要求是检查点保存的内容应当具有完备性，以保证发 生故障时能正确地卷回恢复。将检查点保存的内容以文件的形式保存在稳固 存储介质上，称此文件为检查点文件。检查点文件应包含进程上下文中决定 程序运行正确性的关键内容，主要包括进程地址空间内容、与进程有关的 c p u 寄存器、操作系统( 包括文件系统) 的状态以及进程间通信状态等。论文 从以下几方面加以详细说明。 ( 1 ) 进程数据段，堆栈段内容。数据段和堆栈段内容在执行过程中可能 会被动态修改，因此必须保存。在此需要指明的是进程的正文段即执行代码 不会随程序的运行而改变，而且多次运行时都处于进程地址空间的同一位置， 所以在恢复时可以直接从程序的可执行文件中获得，因而不用保存。 ( 2 ) 与进程上下文切换有关的项。包括程序计数器p c 、处理机状态字寄 存器p s w 以及程序栈指针s p 等。 ( 3 ) 与进程相关的文件信息。是指程序所打开文件的信息，包括文件描 述符，读写指针，文件大小，访问方式等。 ( 4 ) 与进程相关的信号信息。包括信号栈指针、信号屏蔽码、信号处理 函数句柄以及被挂起的信号等。 哈尔滨1 一样人学硕+ 学何论文 ( 5 ) 进程间通信状态信息。在分布式或并行系统中，一个计算程序可能 要分成多个并行进程来运行，此时进程状态保存需要考虑并行进程间的通信 信息。通信信息主要包括通信发起方和接收方的进程标识以及通信内容。 检查点各部分内容有着相互独立而又相互联系的保存和恢复方法。各部 分内容的保存和恢复基本方法如下【1 6 l ： 1 进程的数据段和用户栈 检查点设置时，未经优化的完全保存模式( f u nc h e c k p o i n t i n g ) 将数据段自 起始地址到新分配的最高地址拷贝到检查点文件中。恢复时，将检查点文件 中数据段内容拷回到地址空间的原来位置。进程用户栈的保存和恢复与此类 似。但是恢复用户栈时，由于当前调用过程亦在用户栈中运行，为防止其返 回地址和局部数据结构被拷回的用户栈内容覆盖进而导致程序运行错误，须 采取措施保证当前用户栈中有用内容不会被覆盖后，才可进行用户栈的拷回。 一般系统采用的是转移法，即将栈指针改为指向数据段中的一个安全的 b u f f e r 。另外一种办法是栈增长法。即在恢复用户栈之前，若发现当前栈顶地 址大于欲拷回栈的栈顶地址，或虽然小于，但非常接近以至相差小于某一阈 值( 假定在系统中用户栈由高地址向低地址方向增长) ，则表明当前调用过程 要用到的栈中数据可能因拷回而被覆盖，此时，反复调用当前越程直至当前 栈项地址小于欲拷回栈的栈顶地址，且其差值大于阈值为止。 2 与进程上下文切换有关的项 检查点设置时，与上下文切换有关项包括程序计数器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 将它们恢复。 3 与信号有关的信息 系统调用s i g s e t j m p s i g l o n g i m p 在保存与恢复上下文切换有关项的同时， 还附带保存和恢复信号量屏蔽码以及信号量栈指针。另外在设置检查点时， 通过系统调用s i g a c t i o n 和s i g p e n d i n g 分别获取信号处理函数旬柄和被挂起的 信号，记录到数据段中的一个信号信息表中，随数据段保存而保存。恢复时， 8 哈尔滨t 程大学硕十学位论文 在数据段拷回后，取出其中的信号信息表，通过相应的系统调用将信号处理 函数旬柄和被挂起的信号逐一恢复。 4 活动文件信息 在数据段中定义文件信息表用于活动文件信息的保存和恢复，用于记录 各活动文件的信息。在程序正常执行过程中，监督o p e n 、r e a d 、w r i t e 、c l o s e 等文件系统调用，并维护文件信息表中相应文件表项。检查点设置时，文件 信息表将作为数据段的一部分被保存。恢复时，在数据段恢复完后，依据文 件信息表中记录的活动文件信息，按原访问方式打开文件，并恢复其文件描 述符和读写指针。 在这里要注意的是用户文件。用户文件内容与进程其它状态有很大的不 同，其它状态往往随着应用程序发生故障而丢失，在恢复时把检查点文件信 息写入进程空间就可以恢复这些状态。而用户文件本身就是保存在外部存储 设备上，它并不随应用程序发生故障而丢失。也就是说，如果不对文件内容 进行特殊处理，当发生故障时，其它进程状态卷回恢复到上一个检查点所保 存的状态，而用户文件内容仍然是发生故障时的状态，从而可能造成卷回恢 复后用户文件内容进程全局状态不一致，进而导致程序运行错误。保存和恢 复用户文件内容的一种最容易想到的方法是直接在检查点中保存用户文件的 全部内容。然而，用户文件大小的随意性可能导致的巨大时空开销使得这种 方法不可行。解决方法是在设置检查点时，保存进程当前活动文件的文件描 述符、读写方式、文件大小、读写指针等活动信息；在卷回恢复时，重新打 开文件，并根据活动信息将相应文件截成原来的大小并将指针指向原来的位 置。 在u n i x l i n u x 系统中有关文件操作的典型系统调用有：o p e n 、c l o s e 、 r e a d 、w r i t e 、l s e e k 、u n l i n k ；文件的读写方式有：只读、只写、读 写。通过分析应用程序中由这些系统调用和读写方式构成的不同文件操作流 程对文件内容的影响，以及可能导致卷回恢复后文件内容与进程全局状态不 一致的各种故障，可以得出这样的结论： 9 哈尔滨t 程人学硕十学位论文 ( 1 ) 以只读方式打开的文件，不需保存文件内容。 ( 2 ) 以只写方式打开的文件，在o p e n 文件操作( 或以文件尾为基址的 l s e e k 操作) 所在的那个检查点间隔内要保存文件内容，或在打开时保存文 件长度。 ( 3 ) 以读写方式打开的文件，在任何情况下都要保存文件内容( 包括打开 文件的那个检查点间隔) 。 ( 4 ) 以任何方式打开的文件，在进行u n l i n k 操作时。文件内容需要保 存。 5 进程间通信状态信息 在并行或分布式系统中涉及到的进程间通信状态信息通常包括通信发起 方的进程标识、通信接收方的进程标识、通信内容等。在保存这些内容的同 时还要保证检查点采取时并行进程处于全局一致状态。这样才能保证以后恢 复操作的正确性。要做到这一点，需要有适当的检查点一恢复算法支持。 2 3 进程检查点与恢复算法 根据检查点算法的使用范围可把目前的检查点算法分为两类：单进程程 序检查点算法和并行程序检查点算法，并且前者为后者的基础1 1 7 j s l 。 单进程检查点算法相对来说比较简单，因为它用于保存非通信程序的状 态，故不必考虑由进程间通信而引起的不一致性问题。当出现故障时只需简 单的加载检查点文件恢复进程状态即可以使进程继续运行；并行程序检查点 算法用于保存和恢复并行或分布式程序的运行状态，它是对单进程程序检查 点算法的进一步发展。并行检查点技术是指除了利用单进程检查点机制定点 保存各个节点进程的状态之外，还需要借助于卷回一恢复协议来维护网络通 信状态的一致性，使得并行应用程序的进程从各自的串行检查点处恢复后， 仍能正确的继续执行下去0 s 】。卷回恢复协议是它的核心部分。 1 0 哈尔滨t 程大学硕十学位论文 2 3 1 单独依赖检查点的卷回恢复算法 单独依赖检查点的卷回恢复算法可分为三类：非协同检查点算法i 射、协 同检查点算法盼2 2 1 和通信诱发检查点算法 2 3 1 。 1 非协同检查点算法 非协同检查点算法也可称之为异步检查点算法，程序的各个进程周期性 的相互独立地保存自己的运行状态和记录所接收的消息。在程序状态恢复过 程中，各个进程之间则需要相互协调、通过复杂的卷回算法各自卷回恢复到 合适的检查点状态，以使得整个程序恢复到一个一致的全局状态。所记录的 进程之间的消息将用于把程序状态恢复到一个一致全局状态。 非协同检查点允许分布式程序进程拥有最大程度的自治性。缺点是：由 于每个进程需要保存若干个时刻的检查点文件，所以空间开销很大：在程序 状态恢复过程中可能会重复卷回，可能会出现“多米诺”效应，从而使程序 一直卷回到初始状态。 2 协同检查点算法 协同检查点算法也称之为同步检查点算法。在程序的状态保存时，它协 调程序各进程使其在合适的时刻作局部检查点，这时各进程的检查点文件组 成的集合就是一个一致的全局状态。协同检查点协议的优点是每个进程只需 要保存最近时刻的检查点文件，空间开销较小，而且程序状态恢复时不会出 现“多米诺 效应。其缺点是应用程序的运行受检查点的操作影响较大。 这类算法包括时钟同步算法、最小协同算法和非阻塞的协同算法等多种 扩展协议。传统的阻塞协同检查点协议如下： ( 1 ) 检查点的发起者广播检查点请求消息； ( 2 ) 各进程接收到请求消息后，停止应用程序的运行，清空通信信道( 保 证不会出现孤儿消息) ，并做本地的尝试检查点，随后发送应答消息给发起者； ( 3 ) 发起者收到所有进程的应答消息后，广播全局检查点确认消息； ( 4 ) 各进程收到确认消息后，清除旧的检查点文件，并把尝试检查点升 级为永久检查点，继续应用程序的运行。 哈尔滨t 程大学硕十学何论文 3 通信诱发检查点算法 这种方法允许进程独立地形成检查点，但是却可以避免“多米诺效应” 的产生。为了达成正确的恢复线，各进程可能需要形成附加的检查点，这些 附加的检查点称为强追检查点。通信诱发检查点算法在应用程序的正常消息 中捎带传递与协议相关的消息，接收进程根据这些捎带信息决定是否需要产 生强迫检查点。这种算法的主要缺点是产生强迫检查点可能导致较高延迟的 附加负载。它和协同检查点算法的主要区别是没有明显的协同消息在进程之 间传递。这种算法又可分为基于模型的检查点算法和基于索引的协同算法。 单独依赖检查点的卷回恢复算法中最有代表性的是协同检查点算法，一 些成型的并行检查点系统多是以这种协议为基础。 2 3 2 基于消息记录的卷回恢复算法 基于消息记录的卷回恢复算法可分为三类：悲观检查点算法i ，御】、乐观检 查点算法i ，胁2 6 和因果记录检查点算法【，2 7 】。 1 悲观检查点算法 悲观的记录算法假设在任何一个不确定性事件之后都可能发生失败，因 此，在每个不确定性事件产生后果之前，都把它存储在稳定介质中。基于悲 观的记录算法系统，任何进程原则上状态均可恢复，该算法对其他没发生错 误的进程影响较小，并易于实现垃圾收集机制。并行程序状态只依赖于最近 一次的检查点。但是，由于悲观的记录方式，该算法附加开销较大，因此， 最好依赖于特殊硬件支持。 2 乐观检查点算法 悲观的记录算法实际上采用了一种同步消息记录的方法，这造成相应事 件的延迟。乐观的算法假设在失败发生时消息记录可以完成，因此，它采用 了一种异步的方式，先把消息存储在内存中，然后再周期性地存入稳定介质， 应用程序无须阻塞等待消息记录的完成。但是，这种方法一旦失败前丢失消 息，就要采用相对较复杂的卷回恢复方法( 可采用同步或异步的恢复方法) 。 1 2 哈尔滨t 程人学硕十学佛论文 这类算法也可能产生多米诺效应【，】。 3 因果记录检查点算法 该算法同时具有悲观和乐观算法的大部分优点，但是却付出了相当的内 存开销和磁盘工作代价，它需要更为复杂的恢复协议支持。该算法将未保存 在稳定介质内的消息存储在其他可获得的内存中，并假设不会同时发生n 个 失败，因此，在正常应用程序消息中将捎带不确定性事件，使其至少保存在 n + 1 个进程位置。当程序失败恢复时，它必须通过复杂的协议探知必要的消 息位于什么位置，该算法实现起来较为复杂。 基于消息记录的卷回恢复算法根据由消息发送者记录还是由接收者记录 消息，又均可分为基于收者的记录算法和基于发者的记录算法。 目前，实现基于消息记录的卷回恢复算法的系统很少，主要因为其相对 于成熟的协同检查点算法实现较为复杂，但是，这类算法在理论上已经非常 完善和成熟，在真实系统中实现其算法可能会获得比协同检查点算法更好的 效果。 2 4 检查点技术研究现状 基于检查点技术的大量基础理论研究，将这些抽象理论代码化，就形成 了检查点系统，目前有两种类型的检查点系统：基于用户级的检查点系统和 基于系统级的检查点系统。 2 4 1 用户级支持的检查点系统 1 lib c k p t 系统 田纳西大学的l i b c k p t 系统是一个典型的用户级检查点软件包1 2 8 1 ，它所有 的功能都是以库函数的形式实现的。为了在用户级实现检查点，l i b c k p t 在部 分系统调用和用户程序之间加入了一个中间层以获取进程初始化以及运行时 传入核心的各种参数信息，在需要作状态检查时，将进程的地址空间信息以 及被中间层获取的参数信息通过一定的格式存储到可靠的存储介质中，而状 1 3 哈尔滨i j 程人学硕十学位论文 态恢复时仍然使用原应用程序的二进制文件启动新的进程，由于l i b c k p t 封 装了l i b c 的m a i n 函数，所以在进程启动的入口处l i b c k p t 会根据参数做出判 断并转向恢复进程的分支，在该分支中使用先前做状态检查时备份的信息重 新初始化进程的地址空间以及各种其它参数。使用l i b c k p t 对应用程序有两 个要求：修改应用的源程序，包括m a i n 函数的替换以及在合适的位置调用检 查点函数；编译时链接l i b c k p t 函数库。 l i b c k p t 的局限性包括： ( 1 ) 无法实现外部检查点。 ( 2 ) 无法恢复动态加载的共享库。 ( 3 ) 没有实现信号的状态检查和状态恢复。 ( 4 ) 空间和时间冗余度增加。因为进程与核心的信息交互需要在l i b c k p t 所建立的中间层留有存根( s t u b ) 供状态检查时使用，这不但增加了数据空间的 冗余，而且一定程度上降低了进程运行的效率，增加了时间冗余度。 它的这些局限性很大程度上限制了用户范围。但是由于它是完全的用户 级实现方式，所以具有较好的可移植性，能方便的在各种操作系统之间作移 植。 2 o o n d e r 系统 c o n d e r 系统是威斯康星大学研制的一个基于用户级的异构型分布式检 查点系统【2 9 】，它使用位于工作池中的空闲资源来实现高吞吐量计算。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 池中查找最合适的空闲机运 行任务，它利用将大型计算任务派至远程空闲机执行的方式，把空闲处理机 1 4 哈尔滨t 程大学硕十学俜论文 的c p u 资源分配给其他用户，从而实现负载平衡。 但是c o n d o r 的检查点技术仅支持单进程任务。此外，和所有的用户级实 现的检查点系统一样，c o n d e r 的检查点功能对应用程序有许多的限制，包括 了文件打开的读写方式、进程间通信、核心多线程、以及对f o r k 、e x e c 、m m a p 等系统调用的使用。 用户级支持的检查点系统具体应用时，需要用户对程序结构、流程非常 清晰，对程序行为也很了解，知道程序容易在哪里出错，知道在哪个程序点 处容易捕获程序状态，用户就在这些地方设置检查点，这样就可以保存应该 保存的数据，因此可以减小检查点文件的大小。以上的这些操作都是在用户 空间完成的。用户级检查点系统的缺点是：在特定的条件下，由于检查点的 设置在时间上的间隔可能会很大( 例如第一个检查点可能在程序开始不远处 设置，而第二个检查点可能在程序快结束的时候设置) ，所以，一旦程序出错 需要卷回恢复的时候应用程序可能需要卷回到离出错处很远的地方，这样就 会造成系统资源的浪费，程序员为了解决这个问题，可能会在程序的适当位 置制造出一些检查点来。这样就导致了额外的运行时间、程序复杂性和程序 员的努力，所以说应该设定最优化的频率来设置检查点。并且由此可见，用 户级的检查点系统不具有透明性。 2 4 2 系统级支持的检查点系统 1 c r a k 系统 哥伦比亚大学网络实验室在2 0 0 1 年发布的c r a k 是在操作系统级以内 核模块的形式实现的检查点系统【3 0 j 。这是第一个在u n i x l i n u x 中实现的完全 透明的检查点系统，由于c r a k 是以内核模块的形式实现的，操作系统中的 进程可以完全透明的进行检查点设置和恢复，既不需要对操作系统进行改动 和重新编译，也不需要对用户应用程序代码进行任何改动和重新编译，且 c r a k 对网络套接字也提供了支持。c r a k 主要实现了以下功能： ( 1 ) 不需要修改内核就可以完全透明地实现检查点卷回恢复和应用程序 1 5 哈尔滨t 程入学硕十学位论文 进程的迁移。 ( 2 ) 除了真正的检查点和恢复操作，没有运行时开销。 ( 3 ) 实现了没有“主结点和“代理 进程的真正的进程迁移。 ( 4 ) 以较低的开销实现了虚拟网络。 ( 5 ) 对网络连接的迁移提供了支持。 c r a k 的研制成功证明了为流行的操作系统如l i n u x 设计一个通用的透 明的检查点包，而且不用对操作系统或用户程序添加补丁是完全可行的，这 是e l 前第一个实现了操作系统级透明的检查点系统。 2 b l c r 系统 b l c r 系统是伯克利国家实验室2 0 0 2 年开发并不断扩充功能的检查点系 统川1 ，与同类l i n u x 系统中其他开放源码实现相比，有系统级支持、丰富的 用户回调机制、关键区域设定机制、支持多线程的优点。对于诸如多进程、 会话组、u i d 、资源信息保存等支持也已经列入开发计划。更重要的是伯克 利实验室与l a m 的合作使得l a m m p i 发布的版本7 o 4 中已经利用b l c r 包含了检查点功能，为m p i 并行程序提供了很完备的检查点支持。b l c r 目 前的支持概况：支持s m p 结构；支持l i n u x t h r e