（计算机应用技术专业论文）基于winnt进程检查点技术研究与实现.pdf

摘要 进程检查点机制是在进程正常运行的适当时刻设置检查点，将进程状态保存 到稳定存储器中。如果在随后的运行过程中发生故障，从存储器中读出保存的进 程状态，将进程卷回恢复，继续运行，从而避免从头开始执行，减少计算损失。 随着w i n n t 操作系统的不断普及，基于该操作系统下的应用也越来越广泛。 w i n n t 软件的容错性越来越受到重视。w i n n t 是不公开内核的操作系统，许多研 究通过实现用户级进程检查点系统，在不修改系统内核的前提下来提高w i n n t 软件的容错性。 本文首先对进程检查点技术以及目前国内外研究的现状进行综述。通过分析 现有用户级进程检查点系统，总结了实现进程检查点系统的难点和需要解决的问 题。接着介绍了实现检查点系统的关键技术及其原理：d l l 的注入，a p i 函数的 截获，活动文件的保存和恢复等。 本文着重介绍了用户级进程检查点系统n t c k p t 的设计与实现。该系统由两部 分组成：d l l 注入模块i n j e c t d l l 和检查点库t - f a u l t d l l 。i n j e c t d l l 模块实现了 在执行文件中透明的插入检查点库。检查点库t - f a u l t d l l 是系统的核心，实现 a p i 函数截获和包裹，进程状态的获取、保存与恢复。 进程回卷恢复时，n t c k p t 系统采用了完全一致恢复进程用户地址空间的方 法，与现有系统中的非一致恢复相比不仅可以消除原有方法在恢复进程状态时存 在的隐患还可以减少系统截获和包裹的a p i 调用，简化进程状态的恢复。 检查点时间间隔选取是影响检查点系统性能的个方面。本文利用时间序列 分析方法为进程状态大小情况建立模型，预测进程检查点开销较小的时刻放置检 查点，动态确定检查点的时间间隔。实验表明使用该方法可以帮助用户设置合适 的检查点间隔，有效的减小检查点的开销。 关键宇：软件容错；检查点设置与回卷恢复；检查点开销；检查点间隔 茎王! ：坚垄翟垫查盛堇垄塑耋主塞鎏 a c h e c k p o i n tf a c i l i t ye n a b l e st h ei n t e r m e d i a t es t a t eo far u n n i n gp r o c e s st ob es a v e dt o s t a b l es t o r a g e l i e naf a i l u r eo c c u r s ，u s e r sc a r lr e s u m ee x e c u t i o no ft h ep r o c e s sf r o mt h e c h e c k p o i n tf i l e t h i sp r e v e n t st h el o s so fd a t ag e n e r a t e db yl o n g - r u n n i n gp r o c e s s e sd u et o p r o g r a m o rs y s t e mf a i l u r e s w i t ht h ew i n n tu s e d w i d e l y , t h e r ea r em o r ea n dm o r ea p p l i c a t i o n sb a s e do ni t p e o p l e a t t a c hm u c h i m p o r t a n c e t of a u l t - t o l e r a n c eo ft h ea p p l i c a t i o n s a sw i n n ti sn o ta n o p e no s ，i t i sh a r dt om o d i f yi t sk e r n e l 。s om a n yr e s e a r c ho r g a n i z a t i o n sh a v ed e v e l o p e du s e r l e v e l c h e c k p o i n ts y s t e m st oi m p r o v e t h ef a u l t - t o l e r a n c eo ft h ea p p l i c a t i o no ni t a tt h eb e g i n n i n g , t h i sp a p e r g e n e r a l l yr e v i e w st h ec h e c k p o i n tt e c h n o l o g y , t h e na n a l y z e s a n dp o i n t so u tt h el i m i t a t i o na b o u tt h e e x i s t i n gc h e c k p o i n ts y s t e m ，t h e n c o n c l u d e st h e d i f f i c u l t y a n dt h e p r o b l e m s n e e dt o r e s o l v e s e c o n d l y , t h i s t h e s i si n t r o d u c e st h e k e y t e c h n o l o g yo fc h e c k p o i n ts y s t e m ，s u c ha si n j e c t i n gd l l , i n t e r c e p t i n ga n dw r a p p i n ga p i ， c h e c k p o i n t i n g a n dr e s u m i n gt h es t a t eo ft h eo p e n e df i l ee t c f o l l o w i n g ，t h i sp a p e rm a k e sad e t a i l e da n a l y s i so ft h ed e s i g na n di m p l e m e n to ft h e c h e c k p o i n ts y s t e mb a s e do nw i n n t n a m e d n t c k p t i ti sc o m p o s e do ft w om o d u l e s o n ei s i n j e c t d l l t h eo t h e ri st - f a u l t d l l i n j e c t d l lm o d u l ec a ni n j o c tad l li n t oa ne x ef i l e t r a n s p a r e n t l y t - f a u l t d l l i st h ek e r n e lo fn t c k p t i ti m p l e m e n t si n t e r c e p t i n ga n d w r a p p i n g a p i ，s a v i n ga n dr e s u m i n g t h es t a t eo fp r o c e s se t c t - f a u l t d l li n t r o d u c e saw a yt or e s t o r e a d d r e s ss p a c eo f p r o c e s sc o n s i s t e n t l y u s i n g t h i sw a y c a l la v o i dh i d d e nt r o u b l eo ft h ee x i s t i n g m e t h o db u ta l s os i m p l i f yt h er e s u m eo ft h ep r o c e s s a tl a s t t h i sp a p e ra d o p t sam e t h o du s i n gt i m es e r i e sa n a l y s i s 的m o d e la n df o r e c a s tt h e s t a t es i z eo f p r o c e s s ，w h i c hh e l p st os e l e c ta p p r o p r i a t e i n t e r v a lo f c h e c k p o i n td y n a m i c a l l ya n d r e d u c e st h eo v e r h e a d k e yw o r d s ：s o f t w a r ef 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 a n dr o l l b a c kr e c o v e r y ；c h e c k p o i n t o v e r h e a d ；c h e c k p o i n t i n t e r v a l i i 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其 他个人或集体己经发表或撰写的成果作品。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果 由本人承担。 作者签名： 娑枷 日期：加年五月劢日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位 论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 淳住 日期：乒帅妒年口2 月如e t 日期：如毕年弓月亏。日 第1 章序言 1 1 进程检查点介绍 软件容错系统一般采用冗余来满足系统高可靠性的要求，冗余可以划分为时 间冗余和空间冗余两类。时间冗余是指出现故障时通过将控制卷回到一个无错的 执行点，通过采用同种方法或不同方法再试的手段得到正确结果；空间冗余通常 指由多个相同组件并行执行，通过将各自执行结果比较或者表决的方法来检测错 误或者得到正确结果。空间冗余代价大，成本高，主要应用于特殊领域。时间冗 余不仅开销小，而且行之有效，文献提出8 0 到9 0 的软件错误都可通过时间 冗余的方法来解决。时间冗余方法中最常用的是进程检查点( c h e c k p o i n t i n g ) 方 法。 进程检查点机制是在进程正常运行时周期性的设置检查点，把进程在运行时 的正确状态保存到稳定存储器中。如果在随后运行过程中发生故障，那么将进程 进行卷回恢复，从稳定存储器中读出前一个检查点时的正确状态，从该点继续执 行。这样就避免了由于故障而导致的程序从头重新执行，因而有效的减少了计算 损失。设置检查点的时刻称之为检查点时刻；保存进程状态的文件称之为检查点 文件。 通过设置检查点能过保存和恢复程序的运行状态，因此它在许多领域都有重 要的应用 2 - 4 ： 1 进程迁移 目前大多数操作系统不能提供进程迁移功能，利用检查点可以保存进程在某 台机器的运行状态，然后在其他机器上恢复进程的运行以实现进程迁移。进程迁 移可以使得机群负载平衡，从而提高计算速度和机群的利用率。 2 容错 分布式系统的故障率随系统机器数的增加而增加，长时间运行的作业若在每 次出现机器故障都从头开始执行，该作业将很难被执行完毕。因此，利用检查点 实现多机系统容错成为人们日益关心的热点。 3 卷回调试 在程序调试过程中，利用检查点保存程序在多个时刻的运行状态。当错误发 生时，把程序卷回到保存的某一时刻的状态重新向下运行，以再次产生相同的错 误来查找错误发生条件的调试方法称为卷回调试。分布式程序包含较多的不确定 成份，当发现运行错误重新运行程序查找错误原因时，同样的错误很可能很难再 次出现。利用卷回调试在很大程度上提高错误再次发生的概率。 1 2 进程检查点系统的研究现状 进程检查点可以分别在操作系统级、用户级或者应用程序级实现，但各自有 其优缺点。操作系统级实现的进程检查点【5j 对用户程序透明，容易得到进程的内 核数据结构，但需要修改系统内核，因此对于基于封闭操作系统的迸程检查点难 以实现，并且其可配置性和移植性不高，检查点开销很大。 用户级的进程检查点 6 - 1 1 】，将检查点功能编译为一个库链接到应用程序，可 以实现对应用程序透明，易于配置且开销较小，但其实现机制与操作系统平台密 切相关，无法实现在不同系统平台之间迁移。 应用程序级【1 2 】的进程检查点，优点是能够实现平台无关，可在不同的操作系 统间移植；缺点是只限于几种有限的编程语言，目前仅有基于j a v a 虚拟机的应 用程序级检查点。 由于用户级的进程检查点具有对应用程序透明，易于配置、开销较小且实用 等特点，因此大部分检查点系统都选择在用户级实现。而u n i x 和w i n n t 操作系 统都是非常普及的操作系统，因此，大部分进程检查点系统都是基于u n i x 或 w i n n t 实现的。 1 2 1 基于u n i x 进程检查点系统 u n i x 操作系统下的进程检查点技术已经相对成熟，典型的检查点系统有 l i b c k p t ”j ，c o n d o r 1 4 1 等。实现方法大致如下：保存进程状态：首先，把必要的进 程核一t h , 区内容保存到进程的用户区之中，利用s e t j m p 系统调用保存进程的p c 和 s p 指针等内容；然后，保存进程所打开的文件方式及指针偏移；最后利用进程此 时的数据段、堆栈段和代码段信息组合成一个可执行的检查点文件。当恢复程序 运行状态时，只需要执行程序的检查点文件。检查点文件被执行时，首先将程序 恢复到检查点时刻的运行状态，然后利用l o n g j m p 系统调用恢复进程的p c 和s p 指针使进程继续向下运行。 1 l i b c k p t 1 1 3 】 l i b c k p t 是一个基于u n i x 操作系统的进程检查点库，实现了对进程状态的保 存与恢复。在提高检查点系统性能方面，l i b c k p t 采用了增量算法、复制拷贝算法 以及用户指导检查点算法减少检查点保存量，提高检查点系统的性能。缺点是： 使用该库时，程序员需要改变源代码并且重新编译( r e c o m p i l e ) 应用程序。对于 没有源代码的程序不能使用该检查点库。 2 c o n d o r 1 4 l c o n d o r 系统是基于u n i x 的分布式批处理系统。该系统利用检查点机制保存 进程状态，实现进程在工作机群中的迁移，达到了机群中任务调度的目的。该系 统完全在操作系统外部实现了对程序状态的保存与恢复，因此具有良好的可移植 2 性。其次，它们实现了检查点对用户程序的完全透明性，即不需要修改用户程序 的源代码。但其局限性有两个方面： ( 1 ) 不允许用户程序使用与进程派生、进程通信有关的系统调用，因此不能 直接用于保存和恢复分布式程序的运行状态； ( 2 ) 用户程序必须与检查点库静态链接( r e 1 i n k ) ，拥有程序可执行代码的 用户才能使用检查点功能。 1 2 2基于w i n n t 进程检查点系统 随着w l n n t 操作系统的不断普及，基于该操作系统下的应用也越来越广泛。 w i n n t 软件的容错性越来越受到重视，在用户级研究w i n n t 进程检查点方法已 经取得了很多成果。归纳起来，基于w i n n t 用户级进程检查点的实现途径是：实 现一个进程检查点动态链接库，将库注入目标程序【1 5 】。库中通过截获和包裹系统 a p i l l 6 1 ，掌握应用程序对系统a p i 的调用情况。检查点库负责为目标程序周期性 的设置检查点。检查点时，获得进程地址空间数据【1 。7 】并保存进程状态到固定的存 储器中。当目标程序出现故障时，检查点库读取检查点文件，恢复进程状态，使 程序从上次检查点的状态继续往下运行。 1 a t r a n s p a r e n tc h e c k p o i n tf a c i l i t yo n n t 1 9 】 i n t e l c o r p o r a t i o n 的j o h n n ys r o u j i 在9 8 年发表的文章at r a n s p a r e n t c h e c k p o i n tf a c i l i t yo nn t 介绍了一个基于w i n d o w s n t 的软件容错系统的实现策 略。该文实现了对将检查点库与应用程序透明链接。该系统通过重新定向w i n 3 2 a p i 系统调用实现了对进程数据段，线程上下文、堆栈的保存和恢复。该系统存 在如下局限性： ( 1 ) 程序卷回恢复时，未实现活动文件状态的恢复。利用该系统进行程序卷 回恢复时，并不相应的恢复活动文件的状态。活动文件指的是程序在执行过程中 访问的文件。若程序在运行中执行过写入、删除、改名等改变活动文件状态的操 作时，那么卷回执行的程序便在变化了的文件环境中继续运行，从而产生错误的 运行结果。因此，该系统实现的检查点策路只能允许其用户程序对文件进行只读 操作。 ( 2 ) 做检查点时，线程挂起的不确定性可能导致卷回进程失败。在做检查点 时，该系统的检查点方法采用检查点线程挂起用户线程的策略，用户线程可能在 执行内核代码时被挂起，也可能在执行用户级代码时被挂起。用户线程被检查点 线程挂起时，如果用户线程在内核代码执行被挂起时，可能引起回卷恢复失败。 2 n t - s w i f t 【1 0 】 贝尔实现室的n t - s w i f l 系统实现了n t 进程的检查点设置与恢复。该项目利 用了n t 中的调试机制，以调试模式启动应用进程，在设置检查点时，挂起所有 3 的应用线程并将进程状态保存起来。n t - s w i f t 的实现对于应用进程是透明的。该 系统存在以下不足： ( 1 ) 没有对应用线程的旬柄进行映射，因此依赖于重复创建线程直到返回的 句柄与原来一致，这样增大了系统的开销。 ( 2 ) 未实现程序卷回对相应的恢复活动文件的状态。 ( 3 ) 做检查点时，如果线程挂起在内核态将导致卷回进程失败。 3 w i n c k p t 1 1 8 】 清华大学研发的w i n c k p t 系统，同样也实现了基于w i n n t 的检查点系统。该 系统通过实旋新旧句柄的映射解决了n t - s w i f t 系统中的线程句柄的问题。该系统 对活动文件状态的保存和恢复采用了w o b 方法【1 ”。其基本思想是每相邻两个检 查点之间的任何文件修改作为一个原子操作，要么所有的操作在设置下个检查 点前全部提交( 若进程运行正常的话) ；要么取消所有的操作( 若发生故障) ，对 活动文件的修改在系统提供的缓冲区中进行，在设置下一个检查点前才将磁盘上 的文件内容作真正更新，同时清空此缓冲区。该系统仍有如下局限性： ( 1 ) 保存和恢复进行时，没有对线程本地存储变量( t l s ) 进行处理。 ( 2 ) 文章中对线程挂起的不确定性提出了一种解决方案：设置一个标志来标 示应用程序线程是运行在用户代码段还是在内核代码段。但是这种方法没有完全 解决问题。其原因是没有实现程序线程和检查点线程的同步。 1 3 本文的主要工作 随着p c 机使用范围的不断扩大，w i n n t 系统已经成为一个日益流行的桌面平 台，尤其是在中低端市场，运行u n i x 系统的高级工作站逐渐被价格低廉、使用方 便且符合行业开放性标准的运行w i n n t 的p c 机所取代。与此同时，基于w i n n t 操作系统的机群系统也开始出现。典型的由美国i l l i n o i s 大学研制的h p v m 及由 r i c e 大学开发的b r a z o s l 2 0 l 。由于w i n n t 操作系统在集群系统中的运用，随故障 负载和隶属关系的影响，彼时不再可用，即具有变化特性。特别是随着系统规模 的不断扩大，其在计算过程中发生故障的几率会以指数级增长，对于大规模科学 工程计算任务来说，任务的计算时间比较长，一旦发生上述异常，可视为故障， 会导致并行计算的彻底失败，此前的大量计算不再可用，尤其是与u n i x 系统相比 较，w j n n t 系统是一个相对不太健壮的操作系统。因此研究w i n n t 系统的容错 性越来越受到重视。 为提高w i n n t 系统的鲁棒性，一般有两种方法提高系统可靠性。一是在硬 件配置上或操作系统内部采取容错措施，如硬件冗余、文件备份等。对于大型系 统而言这种方法是高效且实用的；但对于中低端市场而言，这种措施的代价过于 昂贵。第二种方法是在应用层完全用软件实现。即在不修改操作系统的前提下， 4 通过提供库文件或高可用性运行环境来实现，其中的重要措施就是进程检查点设 置与回卷恢复( c h e c k p o i n t i n g a n dr o l l b a c kr e c o v e r y c r r ) 。 本文的主要工作两部分： 1 w i n n t 用户级进程检查点系统n t c k p t 的设计与实现 。由于w i n n t 是一个封闭的操作系统，系统级的检查点不能实现，基于它的用 户级进程检查点有实现的可能。本文通过研究有关w i n n t 进程机制，综合现有研 究成果设计并开发了一个基于w i n n t 用户级进程检查点系统原型n t c k p t 。该系 统由两模块组成： ( 1 ) 注入动态链接库模块i n j e c t d l l 。n t c k p t 使用该模块对应用程序进行预 处理，在不需修改应用程序源代码，不对应用程序进行重新编译或连接的前提下， 透明将检查点库插入到可执行文件中。在实际应用中，通常难以得到应用程序的 源代码，该功能使得n t c k p t 的应用范围得到较大的扩展。 ( 2 ) 检查点动态链接库t - f a u l t d l l 。该库是系统的主要模块，实现a p i 函数截获和包裹，进程状态的获取、保存与恢复。通过对w i n n t 进程机制的研究， 本文提出了将进程状态的保存和恢复分为内核对象和用户地址空间两部分实现的 思想。tf a u l t d l l 采用了完全一致恢复进程地址空间的方法。该方法与原有方 法相比不仅可以消除原有方法在恢复进程状态时存在的隐患还可以减少系统截获 和包裹的a p i 调用，简化恢复过程。 2 对系统性能的改进 本文实现了利用时间序列分析方法动态确定检查点间隔，该方法可以帮助用 户自动设置合适的检查点间隔，有效的减小检查点的开销。检查点的开销跟检查 点时刻进程状态大小有直接关系。对于在运行过程进程状态大小不断变化的程 序，该方法结合历史检查点的开销记录估计下一个检查点区间。通过包裹提交和 释放内存的a p i 调用，掌握进程状态大小序列，用时间序列分析方法对其建立 数学模型，预测检查点区间内几个时刻进程状态大小情况，帮助计算各个时刻检 查点开销率，选取开销率最小的时刻放置检查点。本文中的方法将进程状态大小 的建模和预测限制时间下限，当未到达该下限时，不管进程状态大小是否发生变 化都不进行建模和预测，比原有动态间隔设置方法减小了建模和预测的开销，总 体上降低了检查点的平均开销率。 利用v c + + 开发语言，在w i n n t 平台上实现了n t c k p t 系统的原型。并用 数个基准程序( b e n c h m a r k ) 对原型系统进行了性能测试。 1 4 论文结构 本文共分为六章，第一章介绍了进程检查点的概念、应用以及进程检查点系 统的研究现状。第二章对检查点的实现方式、算法、影响检查点系统性能的因素 及评价指标进行了概述。第三章详细介绍了现有检查点系统实现的关键技术：d l l 的注入，a p i 的截获等。接着在第四章中介绍了用户级进程检查点系统n t c k p t 的设计，着重介绍了系统组成和检查点库的设计思想。第五章中介绍了检查点库 的具体实现细节并对系统进行了性能测试。在第六章中研究并实现了利用时间序 列分析方法动态确定检查点间隔的方法。最后是全文的总结和下一步工作的展望。 6 第2 章进程检查点技术概述 2 1 进程检查点的实现方式分类 进程检查点可以分别在操作系统级、用户级或者应用程序级实现，但各自有 其优缺点。操作系统级实现的进程检查点对用户程序透明，容易得到进程的内核 数据结构，但需要修改系统内核，因此对于基于封闭操作系统的进程检查点难以 实现，并且其可配置性和移植性不高，检查点开销很大。 用户级的进程检查点，将检查点功能编译为一个库链接到应用程序，可以实 现对应用程序透明，易于配置且开销较小，但其实现机制与操作系统平台密切相 关，无法实现在不同系统平台之间迁移。 应用程序级的进程检查点，优点是能够实现平台无关，可在不同的操作系统 间移植；缺点是只限于几种有限的编程语言，目前仅有基于j a 、，a 虚拟机的应用 程序级检查点。 另外，也可通过编译器实现检查点的功能【”】。这种加入了检查点功能的编译 器编译应用程序时，加入特殊代码，通过这些代码来确定检查点的时间及其内容。 这种技术的优点在于编译器可以确定哪些数据需要保存，因此检查点时刻只保存 需要保存的数据，有效的减小检查点开销。但是这种技术实现难度大，并且在程 序编译的过程中，需要编程者的参与确定检查点时间和内容，对用户程序没有很 好的透明性。 2 2 进程检查点算法分类 根据检查点算法的使用范围可把目前的检查点算法分为两类：单进程程序检 查点算法和并行程序的检查点算法，并且前者为后者的基础。 单进程程序检查点算法用于保存非通信程序的状态，出现故障时通过检查点 文件恢复进程状态使其继续运行。 并行程序检查点算法用于保存和恢复分布式程序的运行状态，它是对单进程 程序检查点算法的进一步发展。并行检查点技术是指除了利用单进程检查点机制 定点保存各个节点进程的状态之外，还需要借助于卷回一恢复协议来维护网络通信 状态的一致性，使得并行应用程序的进程从各自的串行检查点处恢复后，仍能正 确的继续执行下去。卷回恢复协议是它的核心部分。 卷回一恢复协议的设计目的是为了保证应用程序在失败发生的时候，通过一些 恢复操作，找到恢复线，从该恢复线处继续正常运行下去。它的思想主要有两个 7 方面：一是如何制止不一致全局状态的产生，二是当不一致全局性状态发生时， 如何消除它所引起的错误。卷回恢复协议【2 2 l 主要分为两大类：基于检查点的卷 回一恢复协议( c h e c k p o i n t b a s e dr o l l b a c k r e c o v e r y ) 和基于记录的卷回一恢复协议 ( l o g b a s e dr o l l b a c k - r e c o v e r y ) 。 基于检查点的卷回一恢复协议主要依赖于各个节点所做的检查点文件来恢复 系统状态，协议的核心思想就是如何制止不一致的全局检查点的产生。主要算法 有非协商检查点( u n c o o r d i n a t e dc h e c k p o i n t i n g ) 2 3j 和协商检查点( c o o r d i n a t e d c h e c k p l o i n t i n g ) 2 4 ) 【2 5 1 以及通信诱导的检查( c o m m u n i c a t i o n i n d u c e dc h e c k p o i n t i n g ) i z 6 。其中最有代表性的是协商检查点，现有的基于p v m 的并行检查点系统 c o c h e c k c 2 7 】与c u m u l v s t 2 8 】都是采用该协议类型实现。 基于记录的卷回一恢复协议不仅使用了检查点，而且记录并行进程间相互传递 的消息。协议分为乐观的记录方式( o p t i m i s t i cl o g g i n g ) 2 9 1 , 悲观的记录方式 ( p e s s i m i s t i cl o g g i n g ) 1 3 0 l 和因果的记录方式( c a s u a ll o g g i n g ) 【3 1 1 。 单进程检查点算法和并行检查点算法的研究各有侧重。单进程检查点算法研 究着重于实现技术研究和检查点算法性能的改进。并行检查点算法则侧重于研究 并行进程检查点算法中的通信协议以及如何减小保存和恢复进程问通信所带来的 开销。 2 3 进程检查点的开销及评价指标 检查点的开销包括时间开销和空间开销两个方面。空间开销是指存放检查点 文件而占有的存储空间。进程检查点文件的大小与所需保存进程状态大小将近， 一般为几百k 至几十m 字节。时间开销就是获取进程状态并将进程状态保存到 固定存储器所耗费的时间以及进程出现故障时恢复时间。恢复时间是指进程由失 败到恢复正常运行所需要的时间。这段时间包括：错误监测时间；从进程的一个 检查点文件恢复失败进程的所需的时间。对于并行程序还包括恢复进程和其他进 程重新建立通信关系的时间。在实时系统中，往往要求在一定的时间内快速恢复； 对于一般应用，用户对恢复时间的要求不高。 评价检查点算法的主要指标：检查点开销r 1 3 2 j ： 彳希 r “1 ：三二= 三一1 ( 2 1 ) 、tt 其中t 是无故障时进程运行所需时间，于是加入检查点后进程运行所需时间。 这个指标表明加入检查点库对用户进程的影响。检查点开销r 作为评价检查点系 统的性能指标。 2 4 影响性能的因素及改进方法 影响检查点性能的因素有如下四个方面f 3 3 】： 1 检查点时间间隔( c h e c k p o i n t i n t e r v a l ) 选择不同的运行参数会直接影响到检查点库的运行性能。其中最为重要的参 数是检查点间隔，即连续两次检查点开始的间隔时间。间隔越长自然应用程序付 出额外的代价越少，但是一旦进程失败，损失的计算就越多。所以有必要对系统 的平均失败率做分析，以确定检查点系统的最优化运行参数，文献1 3 4 】对此做了详 细研究。 2 磁盘存储速度和检查点文件大小 由于需要检查点文件存储在诸如磁盘等稳定的存储介质上，所以检查点文件 大小和存储速度是影响检查点机制的重要因素。 3 网络带宽与延迟 对于并行的检查点库，由于卷回恢复协议中往往需要传送额外的消息，因此 网络通信的速度也影响着检查点的性能。如果需要将检查点文件异地保存，或者 存在类似n f s 的网络文件系统上，网络的传输速度对并行检查点库性能的影响就 更大了。 4 程序行为 不同程序有其不同的特性，检查点库性能很大一部分都由程序的特性决定。 检查点算法主要是通过两种策略来减小算法的开销：一是减小检查点时刻所 需保存的进程状态信息；二是提高检查点操作与程序运行的并行性。目前，通过 第一种方法减小检查点开销的算法有增量算法【35 1 ，用户参与的方法 36 1 ，编译器辅 助的内存排除算法，数据压缩方法【3 7 】等。通过第二种方法减小检查点开销的算法 有主存算法，写复制算法等。 2 5 实现检查点系统的难点和关键问题 现有的检查点系统已经取得了许多成果，不同的检查点系统各有其优点以及 不足。总体上来看，实现检查点系统的难点和关键问题如下： 1 检查点系统须对用户程序保持透明 现有的许多检查点系统存在的局限性是应用程序在使用检查点功能之前需要 与检查点库进行静态链接，这就意味着只有拥有应用程序源代码的用户才能使用 检查点的功能。因此，为扩大检查点库的使用范围就必须能够在不修改源代码的 前提下给应用程序加入检查点功能，即将检查点库透明的插入应用程序的可执行 文件。保持检查点系统对用户程序的透明。 2 程序卷回恢复时需相应恢复活动文件的状态 9 现有的部分检查点系统进行程序卷回到上一个检查点时刻重新运行时，没有 考虑相应地恢复活动文件的状态。如果卷回执行的程序在变化了的活动文件中重 新运行，将会产生错误的运行结果。因此，实现检查点系统的卷回恢复时需相应 恢复活动文件的状态。 3 保存和恢复线程本地存储变量 线程本地存储变量是线程对象的一个重要属性，它将数据与执行的特定线程 联系起来。因此，检查点系统也需实现对线程本地存储变量的保存和恢复。 4 对于多线程程序设置检查点的支持j 现有的部分检查点系统针对多线程程序设置检查点时，利用检查点线程将用 户线程挂起后再保存进程状态。这种方法可能使用户线程挂起在内核态，而此时 保存的进程状态不能正确恢复进程。因此，针对多线程的程序设置检查点时，必 须保证将用户线程挂起在用户态再保存进程状态。 1 0 第3 章w i n n t 用户级进程检查点的关键技术 随着w i n n t 操作系统的不断普及，基于该操作系统下的应用也越来越广泛。 w i n n t 软件的容错性越来越受到重视，在用户级研究w i n n t 进程检查点方法已 经取得了很多成果。归纳起来用户级w i n n t 进程检查点的实现基本途径是：实 现具备检查点功能的动态链接库，再将库注入到目标程序。注入的检查点库通过 截获和包裹系统a p i ，掌握应用程序对系统a p i 的调用情况。检查点库负责为目 标程序周期性的设置检查点。检查点时，获得并保存进程状态作为检查点文件保 存到固定的存储器中。当目标程序出现故障时，检查点库读取检查点文件，恢复 进程状态，使程序从上次检查点的状态继续往下运行。 本章详细研究了d l l 的注入技术，a p i 的包裹技术，通过它们可以为用户程 序透明的加入检查点功能；详细介绍了活动文件的保存和恢复方法。 3 1d l l 的注入 在w i n n t 中有多种方法能够将一个d l l 插入另一个进程的地址空问中。 m i c r o s o f t 公司开发的d e t o u r s 1 6 l 是一个在x 8 6 平台上截获任意w i n 3 2 函数调用的 工具库。该库使用其中的两种方法分别为尚未运行的程序或者已经存在的进程插 入d l l 。检查点系统n t c k p t 中使用了d e t o u r s 中的实现工具。 下面是d e t o u r s 实现d l l 插入的原理。 1 通过修改程序的二进制文件来插入d l l 这种方法可为任何尚未运行的程序插入d l l 。为需插入的d l l 赋予一个单 独的名字并改变应用程序e x e 模块的输入表。这是一种很好的方法，只不过要非 常熟悉e x e 和d l l 文件的格式，m i c r o s o f t 公司开发的d e t o u r s 工具库就通过这种 方法将d l l 插入目标程序中。 图3 1 为w i n 3 2 的p e 二进制文件的基本结构。w i n 3 2 二进制文件的p e 格式 是c o f f ( 普通对象文件格式) 的一种扩展。一个w i n 3 2 二进制文件包括一个对 d o s 兼容的文件头，一个p e 头，一个包含了程序代码的t e x t 节，一个数据节保 存了初始化数据，一个导入d l l 和函数的输入列表，一个导出函数的输出列表， 以及调试符号。除了两个文件头以外，文件的每个节都是可选的。二进制文件可 以不包含它们。 为了修改一个w i n 3 2 二进制文件，d e t o u r s 在输出表和调试符号之间生成了 一个新的d e t o u r s 节。注意调试符号必须永远处于w i n 3 2 二进制文件的最后面。 h e a do f f n e e n do ff i l e d o sh e a d e r p e ( w c o f f ) h e a d e r t e x ts e c t i o n p r o g r a mc o d e d a t as e c t i o n i n i t i a l i z e dd a t a i d a t as e c t i o n i m p o r tt a b l e e d a t as e e t i o n e x p o r tt a b l e d e b u g s y m b o l s 图3 1w ；n 3 2p e 可执行文件的结构 这个d e t o u r s 节保存了一个截获文件头记录和原始的p e 头。如果修改了输入表， d e t o u r s 会生成一个新的输入表，并将它添加到拷贝的p e 头上后，然后修改原始 的p e 头，让它指向新的输入表。 最后，d e t o u r s 会将一些其他信息写到d e t o u r s 节的后面并将调试信息附加到 文件的晟后面。d e t o u r s 可以将二进制文件恢复到被它修改以前的状况，因为它可 以恢复在d e t o u r s 节中保存的原始的p e 文件头，并删除d e t o u r s 节。图3 2 为被 d e t o u r s 修改过的w i n 3 2 二进制文件的格式。 生成一个新的输入表有两个目的。第一，它保留了原始的输入表，程序可以 恢复到修改前的状况。第二，新输入表可以保存被更名的输入d l l 和函数或者新 插入的d l l 和函数。 2 使用c r e a t e r e m o t e t h r e a d 插入d l l d e t o u r s 为实现在已经开始运行的进程插入d l l ，使用了c r e a t e r e m o t e t h r e a d 函数进行d l l 插入。w i n d o w s 为了防止一个进程破坏另一个进程的运行，大多 数函数只允许对自己的进程进行操作。其中c r e a t e r e m o t e t h r e a d 函数，能够容易 的在另一个进程中创建线程。利用在目标进程中新创建的线程调用l o a d l i b r a r y 函数来加载想要插入的d l l 。该方法的基本操作步骤： ( 1 1 使用v i r t u a l a l l o c e x 函数，在目标进程的地址空间中分配内存。 ( 2 ) 使用w r i t e p r o c e s s m e m o r y 函数，将d l l 的路径拷贝到第一步中分配的内 存中。 ( 3 ) 使用g e t p r o c a d d r e s s 函数，获取l o a d l i b r a r y a 或l o a d l i b r a r y w 函数的 实地址( 在k e r n e l 3 2 ，d l l 中) 。 h e a do f f n e e a do ff i l c d o sh e a d e r p e ( w c o f f ) h e a d e r t e x ts e c l 。i o n p r o g r a mc o d e d a t as e c t i o n i n i t i a l i z e dd a t a i d a t as e c t i o n i m p o r tt a b l e e d a t as e c t i o n e x p o r tt a b l e d e t o u r ss e c t i o n d e t o u rh e a d e r o r g i n a lp eh e a d e r n e w i m p o r tt a b l e u s e ro a v l o a d s d e b u gs y m b o l s 图3 2 一个被d e t o u r s 修改过的= 进制文件的格式 ( 4 ) 使用c r e a t e r e m o t e t h r e a d 函数，在目标进程中创建一个线程，它调用正 确的l o a d l i b r a r y 函数，为它传递第一步中分配的内存地址。 这时d l l 已被插入到目标进程中，同时d l l 的d l l m a i n 收到 d l lp r o c e s sa t t a c h 通知，并执行需要的代码。 3 2a p i 函数截获 内核对象的状态是进程状态重要的部分。w i n n t 将内核对象的数据结构保 存在内核空间中，而内核空间不能由用户线程直接访问，如果需对内核对象进行 访问和操作，必须通过系统提供的a p i 调用。因此保存系统内核对象状态的一个 可行的方法是截获对内核对象进行访问和操作的a p i 。从截获的a p 中可以获知 操作内核对象的a p i 调用、参数、返回值等，将他们都保存到检查点文件中。当 程序出现故障进行恢复时，将重新执行保存的有关a p i 调用，创建及操作内核对 象来恢复其状态。 d e t o u r s 提供了在x 8 6 平台上截获任意w i n 3 2 函数调用的功能。中断代码可 以在运行时动态加载。d e t o u r s 使用一个无条件转移指令来替换目标函数的最初几 条指令，将控制流转移到一个用户提供的截获函数。而目标函数中的一些指令被 保存在一个被称为“t r a m p o l i n e ”的函数中，这些指令包括目标函数中被替换的代 码以及一个转移到目标函数的无条件分支。而截获函数可以替换目标函数，或者 茎王! i 2 _ ：垄堡垒查盛垫垄互壅皇塞鎏 通过执行“t r a m p o l i n e ”的时候将目标函数作为子程序来调用的办法来扩展功能。 当程序执行到达目标函数的时候，会直接跳转到一个用户支持的截获函数。 截获函数来执行适当的预处理。截获函数可以直接返回到原来的函数，或者它可 以调用“t r a m p o l i n e ”函数，后者可以按照截获以前的方式来调用目标函数。当目 标函数执行完以后，它将控制返回到截获函数。而截获函数将执行恰当的收尾工 作并将控制返回到源函数调用处。图3 3 显示了被截获和未被