（计算机应用技术专业论文）软件系统自恢复时间策略研究与实现.pdf

硕士论文软件系统自恢复时问策略研究与实现 摘要 软件自恢复( s o f t w a r er e j u v e n a t i o n ) 是针对因内存泄露、数据冗余、未释放的文 件锁、磁盘碎片或循环累积的小错误等引起的软件退化( s o f t w a r ea g i n g ) 问题而提出 的一种容错技术，通过周期性地停止某个应用程序或者系统的运行，修复并重启，以 避免或延缓系统出现严重错误。因自恢复会导致一定的停机损耗，如何确定自恢复时 间间隔，使恢复损耗最小化，成为一个亟待解决的问题。 本文研究利用基于马尔克夫的m r s p n ( m a r k o vr e g e n e r a t i v es t o c h a s t i cp e t r in e t ) 模型计算自恢复时间间隔。研究了已有两类计算方法：基于模型和基于阈值的方法， 其中主要是马尔克夫模型；跟踪系统的运行状况，对系统内存和c p u 占用情况进行 采样，得到资源占用曲线；采用m a n n k e n d a l l 趋势估计法对曲线进行分析，结果表 明该方法能自动检测资源曲线的递减趋势，并编程计算递减快慢；计算模型所需参 数，计算时间间隔。 关键词：软件退化软件自恢复恢复时间间隔 a b s t r a c t s o f t w a r er e j u v e n a t i o ni sap r e v e n t i v em a i n t e n a n c et e c h n i q u ep r o p o s e dt oc o u n t e rt h e p h e n o m e n o no fs o t t w a r ea g i n gw h i c h i sc a u s e db ym e m o r yb l o a t i n ga n dl e a k i n g ， t l r f f e l e a s e df i l e 1 0 c k s ，d a t ac o r r u p t i o n ，s t o r a g es p a c ef r a g m e n t m i o na n da c c u m u l a t i o no f r o u i l d o f fe r r o r s b e c a u s es o f t w a r er e j u v e n a t i o nw i l lb r i n go nd o w n t i m ea n dc o s td u et o d o w n t i m e ，i ti sv e r yi m p o r t a n t t od e c i d ew h e nt or e j u v e n a t e t h ep u r p o s eo ft h i sp a p e ri st or e c k o nt h er e j u v e n a t i o ni n t e r v a lb a s e do nm r s p n ( m a r k o vr c g e n e r a t i v es t o c h a s t i c p e t r in e om o d e l w h a tid oi sf o l l o w i n g f i r s t l y , s t u d y i n gt w om e t h o d su s e dt or e c k o nt h er o u v e n a t i o ni n t e r v a lb a s e d o nm o d e l sp o l i c ya n d b a s e do na l e r tt h r e s h o l dp o l i c y ；s e c o n d l y , t r a c i n gt h er u ns t a t so f t h es y s t e ma n do b t a i n i n g t h ec u r v e so fs y s t e mr e s o u r c e si n c l u d i n gc p ua n dm e m o r yu s i n gw i n 3 2a p i f u n c t i o n s ； t h i r d l y ，r e c k o n i n g t h ed e s c e n d i n gf i e n do ft h ec u r v e sb a s e do nm a n n - k e n d a l l ，a n d p r o g r a m m i n gt oc a l c u l a t et h es p e e d o fd e s c e n d i n g ；f o u r t h l y ，c a l c u l a t i n gt h ep a r a m e t e r so f m r s p nm o d e la n dr e c k o nt h er e j u v e n a t i o ni n t e r v a l n l er e “ts h o w st h a tic a l lg e t 也er e j u v e n a t i o ni n t e r v a lu n d e r t h et e s tc o n d i t i o n s k e y w o r d s ：s o f t w a r ea g i n g s o f t w a r er e j u v e n a t i o nr e j u v e n a t i o ni n t e r v a l 声明尸明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本 学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或 公布过的研究成果，也不包含我为获得任何教育机构的学位或学历而使 用过的材料。与我一同工作的同事对本学位论文做出的贡献均已在论文 中作了明确的说明。 研究生签名：年月日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或 上网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并 授权其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密 论文，按保密的有关规定和程序处理。 研究生签名：年 月日 硕上论文软件系统自恢复时间策略研究与实现 1 绪论 随着i t 工业日新月异的发展，日益增加的信息和技术集成的需求使得人们对 计算机系统的管理和维护提出了新的要求。现今电子化企业的基础建设歧异性越来 越大，运行环境也随之越来越复杂，未来不只会让计算机系统的管理与人事成本越 来越高，甚至可能会演变成复杂到人力无法管理的地步，而且时下很多企业贪求“体 积小、速度快、价格便宜的目的，也让这些问题更加严重。因此，i t 业迫切的需 要计算的系统能自我管理。 自主式计算【4 5 】的灵感来自于人体复杂的自助神经系统，它以同样的方式预测系 统的需求和清除故障在无需人工干预的情况下聪明的运行。所要解决的是日益 复杂的计算环境中所面临的管理与成本问题。自主式计算通过“用技术管理技术 来帮助解决这一问题。 软件自恢复的相关概念 未来的计算机系统是自主式的计算系统，其功能之一是实现系统的自恢复。系 统的运行实际上就是以硬件为基础的一系列软件的运行过程。因此，系统的自恢复 功能还是希望通过对软件的运行过程采取某些措施来实现。 1 1 1 软件的退化现象 最近的很多研究发现：由于软件故障而引起计算系统出错或者崩溃的可能性远远 大于由硬件故障所带来的可能性。而且，随着运行时间的增加，由于越来越多资源请 求及资源消耗、数据的冗余和大量细小错误的堆积，软件出错的概率也在不断增大。 这就是所谓的软件退化现象【2 1 】。这些现象可能会由应用程序、中间件或者操作系统中 的错误引起。客户一服务器模式中服务器端的应用程序由于需要连续的运行，更容易 出现软件退化的现象。随着软件退化现象的发生，软件的运行状态也会越来越差，这 就会导致很多意想不到的结果。导致软件性能下降的原因有很多，如内存膨胀、内存 泄露、没有终止的进程、没有释放的文件锁、数据冗余、磁盘碎片或者是循环错误的 累积。h u a n ge ta 1 在电讯账单处理的应用软件中发现了软件退化的现象，这些软件在 运行一段时间之后会崩溃或者终止掉。a v r i t z e r 和w e y u k e r 在电讯系统中处理交换任务 的软件中同样发现了软件退化的现象，随着运行时间的增加，该现象的作用越来越明 显【1 4 】。其实，除了这些特殊领域的软件，在很多需要通过硬件重启解决问题的软件中， 硕士论文软件系统自恢复时问策略研究与实现 软件退化现象也是普遍存在的。 1 1 2 软件自恢复 为了抵消软件退化现象带来的不良后果，h u a n ge ta 1 于1 9 9 5 年提出了软件自恢复 这一技术。 软件自恢复指的是周期性的停止软件的运行，清理内在状态，如内存垃圾的收集、 清扫操作系统的内核、重新初始化内部的数据结构等等，然后重新运行。最极端的例 子就是硬件的重启。 软件自恢复相对于被动的传统容错技术而言，是在系统崩溃之前采取适当的修复 行为来防止或者延缓错误的发生。软件自恢复是其中的一种特殊方式，它是在某些特 定的时间完成的，这样相对于系统出错后才采取措施的做法，软件自恢复引起的恢复 损耗会少得多。 1 1 3 恢复时间间隔 软件自恢复技术是一个周期性的行为，由于软件在恢复过程中不能提供服务，从 而导致一些时间或者财力方面的损失，因此，相关的一个很重要的问题是决定什么时 候进行恢复，即恢复时间间隔。如何得到恢复时间间隔，使得恢复损耗最小，这也是 本文研究的主要内容。 软件自恢复技术的重要性 由于计算机系统在很多领域的运用越来越广泛，人们希望系统在运行过程中由于 出错而导致的停机损耗越少越好。随着i t 技术的快速发展，硬件在系统运行过程中出 错的几率越来越小。相反，根据研究发现，现代计算机系统中由于软件出错而导致系 统崩溃的概率远远大于硬件出错带来的概率 1 1 , 1 2 , 1 3 】。因此，越来越多的注意力投向了 软件运行过程中的可靠性。 传统的容错技术有很多，比如n v e r s i o np r o g r a m m i n g1 6 j 和r e c o v e r yb l o c k ，但 是由于成倍增加的功能软件的数量，从本质上来说，这些容错机制实现起来的花销 相当昂贵。重新启动( r e a c t i v e ) 也是针对上述错误的典型措施，即在错误发生后， 采取一系列措施。到目前为止，大多数解决方案都是采取人为操作，也可针对特定 程序的利用“智能”程序完成。近期，w a t c h d ，l i b f i 和n d f s r e p l 等独立于平台和 应用程序的模型已被应用到多种程序，它们的功能是当这些程序检测到这类错误 后，能够从短暂的错误中恢复【_ 7 ，8 】。在这种解决方案中，一旦应用程序运行失败，系 2 硕士论文软件系统自恢复时间策略研究与实现 统将启用恢复机制以重新启动该进程。 相对于上面的被动的传统容错技术( 在系统发生错误之后才采取相应措施) 而 言，软件自恢复是一种前摄性的容错技术 1 6 , 1 7 , 1 8 】，它通过某些数学方法对系统资源 的消耗程度进行监控、分析，当消耗到某一阈值时，推断出系统可能发生错误的时 间，在系统崩溃之前自动采取适当的修复行为来防止错误的发生。这样相对于系统 出错后才采取措施的做法，软件自恢复引起的停机时间以及恢复损耗会降低很多。 软件自恢复技术是一种预防和主动方案，对于处理资源泄漏和死锁问题，该技术具 有一定的实用价值。 软件自恢复技术中的一个关键问题在于确定恢复时间间隔。系统或者软件在恢 复的过程中，不能提供任何服务，因此会导致一定的时间或者资金方面的损耗，如 果不能很好的确定恢复时间间隔，由恢复带来的停机损耗可能会比系统因出错导致 的损耗大得多，适得其反。 1 3 国内外现状 最近几年，人们越来越多的关注到软件退化的现象。针对这一现象，y e n n u nh u a n g 在1 9 9 5 年首次提出了软件自恢复这一概念。 在这之前，在计算机领域中，系统恢复虽不是一个新概念，但是，与恢复相关的 报告通常表明系统崩溃总与硬件错误相关。非正式的软件研究机构在软件的恢复方面 也具备充足的数据，也提出了一些基本概念，但当时发表的刊物和书籍中都无法找到 与“软件自恢复”有关的概念。 软件自恢复技术中的一个关键问题是决定什么时候进行恢复，使得恢复损耗最 小。前人针对这个问题，采用了建模的方法和设置阈值的方法进行研究。 建模的方法是指以某些假设为前提，通过对软件或者系统的实际运行过程进行模 拟，借助于数学知识，计算出恢复时间间隔。 计算恢复时间间隔的模型有很多。最先的模型是由y h u a n g 等提出的。他采用连 续时间的马尔科夫链来模拟带有恢复的软件运行过程，通过该模型推导出由系统停机 而造成的预计损耗，并计算出系统抗衰性价比最优的阈值条件。g a r ge ta 采用m r s p n ( m a r k o vr e g e n e r a t i v es t o c h a s t i cp e t r in e t ) 模型来模拟恢复的软件运行过程，并利用 相关的马尔科夫链的理论知识给出了计算恢复时间间隔的方法。这两者是很重要很基 本的模型。 此后的很多模型2 2 郐, 2 7 , 1 9 , 2 6 1 在建模的时候中考虑了的是引起软件真正出错而不可 用的错误，其中模型2 2 ，2 5 2 7 1 假设错误发生的时间成指数分布，而模型1 9 , 2 6 ，2 8 】贝0 是针对 捕捉到的特殊退化现象假设错误发生的时间符合一般分布。论文【2 8 】提出的模型只考虑 硕上论文软件系统自恢复时间策略研究与实现 了软件在运行过程中逐渐减弱的服务效率。后来的研究考虑到系统的负载情况，将系 统中到达以及在队列中等待执行的工作纳入制定恢复时间的策略中，希望软件在系统 负载较少的时候进行恢复【1 3 】。论文【1 6 】在建立模型的时候把上面的因素都考虑到了， 是一个全面、详尽的模型。 论文t 4 1 贝, l j 采用了设置阈值的方法。利用阈值的方法是通过时时跟踪系统或者软件 的运行状况，对衰减参数进行采样，将采样结果与事先设定的阈值相比较，从而决定 是否需要自恢复以及什么时候进行恢复。 1 4 本文主要工作 对恢复的策略进行了分析和总结，并利用m r s p n ( m a r k o vr e g e n e r a t i v e s t o c h a s t i cp e t r in e t ) 模型，在w i n d o w sx p 的平台下，计算本文实验环境中恢复的 时间间隔。所做工作包括以下几个部分： 1 ) 2 ) 3 ) 4 ) 研究了已有的两类计算恢复时间间隔的方法：基于模型和基于阈值的方法， 并着重研究了m r s p n 模型： 跟踪w i n d o w sx p 系统的运行状况，利用w i n 3 2a p i 函数对系统的物理内存、 页文件和c p u 的占用情况进行采样，得到资源占用曲线，并获得系统进程 的运行情况以及模块的使用情况； 采用m a n n k e n d a l l 趋势估计法对资源占用曲线进行分析，结果表明该方法 能自动检测资源曲线的递减趋势，确认软件退化现象的存在，并编程计算 递减的快慢程度； 利用第四章中计算递减快慢程度的方法m r s p n 模型研究所需参数，并将参 数代入模型，计算恢复时间间隔。 4 硕士论文 软件系统自恢复时间策略研究与实现 2 恢复时间间隔计算方法 软件自恢复技术是周期性地停止某个应用程序或者系统的运行，修复并重启，避 免系统出错或者延缓出错的时间。由于恢复的时候软件不能提供服务，会导致一定的 停机损耗，所以其中的一个关键技术确定恢复的时间，即恢复时间间隔。本章节主要 是针对这个问题利用建模和设置阈值的方法进行研究。 2 1 基于建模的方法 2 1 1y h u a n g 的模型 y e n n u nh u a n g 在s o f t w a r er e j u v e n a t i o n ：a n a l y s i s ，m o d u l ea n da p p l i c a t i o n 【冽 一文中指出是否需要执行自恢复取决于三个因素：恢复花费，应用程序的出错频率 和恢复停机花费，并在这一基础上提出了一个分析模型，通过该模型可分别推导出 由系统停机而造成的预计损耗。在已知上述预计值的条件下，可得出系统抗衰性价 比最优的阈值条件。试验证明，如果保持阈值条件不变，那么恢复时间间隔的改变 并不影响是否需要恢复的决定，它仅会对停机损耗有所影响。 图2 1 具备自恢复功能的随机转换图 y e n n u nh u a n g 用几个状态及他们之间的转换来模拟软件的运行过程，见图2 1 。 & ，品，s f ，s r 分别表示软件的四个状态：运行良好、可能出错、运行出错以及 自恢复状态。 当软件开始运行时，处于状态& ，在该阶段软件运行稳定；经过一段时间进入 状态砩。从状态品转换到状态砩平均概率是，2 。夕 ，c ， c ，。相比不具 备自恢复功能的软件，根据式( 2 1 0 ) 计算得到的停机损耗会少得多。下面讨论恢复 阈值，将决定是否有恢复的必要。 从直观的角度看，如果r 3 非常大，意味着恢复的速度相当快，那么恢复就可以 减少应用程序的停机时间，因为系统停留良好状态s 。的时间更多，出错的机率相对 少些。相反，恢复的速度不够快，则系统更多的时间是停留在s r 的状态，导致系统 停机损耗增大。对于其他的几个指标( r l , r 2 ，名) ，也可以做类似的分析。 当恢复的频率r 4 发生变化时，系统的体积时间以及系统停机造成的损失的变化 情况。 停机时间 兰上r 4 d 0 、v n t 岬) = l 歪砸r l r 3 ( 2 1 1 ) l + 二二+ 二二+ 兰+ ! r lr 2r 2弓 对r 4 求导，得到结果， 丢一t i m e c 驴l 去刁南 毛 r 2r 2r s = r l ( 1 + 争b 他1 2 ) 从结果看出，分子和分母都是“的线性函数。而且分母始终为正，所以求导结 果的符号，由表达式ir l ( 1 + 导) 一r 3l 确定，而该表达式中不包含r 4 。这就意味着，当 i 以 r 4 变化的时候，停机时间的变化情况( 或增加或减少) 只由旯、毛、1 2 、r s 的值决定， 与r 4 没有关系。当弓大于毛( 1 + 鲁) 时，求导结果为负，表示随着r 4 增加的时候，停 机时间总是在减少，应当在软件一进入s p 的状态就立即执行自恢复。相反当r s 小 于毛( 1 + 专) 时，求导结果为正，表示随着r 4 的增加，停机时间也跟着增加，系统不 需要恢复。 7 硕士论文软件系统自恢复时间策略研究与实现 任何形式的恢复都包括一定的花销，但是它却能阻止更多更为严重的错误发 生，至少可以延缓出错的时间。 此后，很多人在y e n n u nh u a n g 提出的这一基本模型上，根据软件在实际运行过程 中会碰到的一些情况，对其进行修改和完善，提出更多的模型，并对确定恢复时间间 隔作定量的分析。 2 1 2 改进的y e n n u nh u a n g 模型 该模型是在h u a n ge t a l 提出的模型的基础上作了些修改而得到的【2 3 1 。s o 表示如软 件运行良好的状态；s i 表示软件可能出错的状态；s 2 表示软件出错的状态；s 3 表示的 是软件处于恢复的状态。该模型考虑到系统重启之后，还需要作一些和恢复相同的工 作，所以将h u a n ge t a l 提出的连续时间的马尔科夫链修改为半连续的马尔科夫链，在 该模型中，软件在出错修复完成后同样进入软件自恢复的状态。z 表示从s o 转换到s l 的随机时间间隔，x 表示从s 1 转换至l j s 2 的随机时间间隔，y 表示的是软件出错后完成 修复的时间，是个常量。在该模型中，软件自恢复的时间间隔从软件一进入状态s l 开始计时，用常量t 表示。由于系统出错完成修复之后同样进入恢复的状态，所以， 该模型中软件在m i n ( z + x + y ，z + t ) 时刻开始恢复。 图2 2 带自恢复的系统运行模型之二 以本模型为基础，对计算自恢复时间间隔提出了一种更为实际、有效的办法。以 前需要对系统随时间出错的分布函数进行详细说明，该过程要用到很多可靠的测量方 法，这样的局限性是很大的，因为根据实际测得的数据来确定理论上的分布函数很麻 烦，需要测试得到的数据没有误差，而且参数的计算还得依赖于很多的函数。但是在 该模型下提出的计算方法不依赖于任何一种分布函数，而且能提供不需要参数的估计 方法来计算恢复时间间隔，使得稳定状态的单位时间损耗最小。 硕士论文 软件系统自恢复时间策略研究与实现 2 1 3m r s p n 模型 该模型使用m a r k o vr e g e n e r a t i v es t o c h a s t i cp e t r in e t l 2 s 3 1 1 来模拟软件或系统的 运行过程。 由于带恢复的软件运行过程中恢复的时间间隔是确定的，所以在对这样的随机过 程【2 9 】建模的时候存在一定的困难，一是系统不再是一个马尔科夫链，二是以连续时间 马尔科夫链理论为基础的标准评估方法不再有效。在这种情况下，只能对潜在的非马 尔科夫系统下的随机过程进行研究。带恢复的软件运行过程可以被看作是一个可再生 的马尔科夫链( m r g p ) ，因此可以运用马尔科夫的补充理论【3 0 3 4 l 。 为了分析带有潜藏m r g p 的n o n m a r k o v i a ns t o c h a s t i cp e t r in e t s 3 4 】，必须定义潜在 随机过程中的一些时间点，称之为再生时间点，在这些时刻，软件或系统的运行状况 与以前系统的行为没有任何关系，之后的状况也仅有此时刻决定。分析m a r k o v r e g e n e r a t i v es t o c h a s t i cp e t r in e t ，步骤如下： 1 ) 用一个详细的s p n ( s t o c h a s t i cp e t r in e t ) 3 2 , 3 3 3 5 l 来模拟系统的运行过程，并说明 它是属于m r s p n 类的； 2 ) 获得s p n 的转移图，定义系统运行过程中的再生时间点，从而找出系统中 的从属过程，从属过程从任何可能的状态开始，而且具有无记忆的性质； 3 ) 以找到的从属过程为基础，分析整个过程中稳定状态的行为。 按照上面的步骤，首先用m r s p n 来模拟软件自恢复的过程。 图2 4 软件自恢复的m i z 3 p n 模型 软件开始运行的时候都处于良好状态，这时候出错的概率为0 。随着时间的推移， 软件出现退化的情况，如果不进行恢复，软件将会进入另一种状态。在这种状态下， 软件虽然能够正常运行，但出错的概率却越来越大。一旦出错，经过一段随机时间的 9 硕士论文软件系统自恢复时间策略研究与实现 修复，重启之后回到良好状态重新开始运行。恢复是在从良好状态开始运行后的一段 确定时间之后完成的。在恢复之前，如果软件还没有出错，它要么处在良好的运行状 态，要么处在有可能出错的状态。此时，软件停止运行，恢复并重启。这些过程所用 时间都是一个随机数。同时，m r s p n 模型假设软件在运行良好的状态停留的时间以 及从可能出错到真正出错的时间均满足指数分布，从某种程度上考虑到了软件负载的 因素。 p u p 表示软件运行的稳健状态，转移t f p r o b 表示软件的退化过程。当这一转移发 生的时候，软件就进入可能出错的状态p f p r o b 。转移t d o w n 模拟的是软件出错的过程。 软件在重启的过程( 用t u p 来模拟) 中，其它的所有活动都被停止，用p d o w n 至l j t c l o c k 之间的连线模拟该情况。 t c l o c k 模拟了恢复的时间间隔。当t e l o c k 已经耗尽，并且此时软件还没有进入 t f p r o b 的状态，标记就会转移蛰j p r e j ，开始恢复。在恢复的过程中，系统的其它活动 被停止掉，用p r e j 至l j t f p r o b 和t d o w n 的连线表示。一旦恢复完成，系统就又会被初始 化为只有p u p 和p c l o c k 两个状态，其他的都是空的情况。如果t c l o c k 已经耗完，而且此 时系统仍处于稳健状态，则恢复完成后，t r e j 2 表示重新初始化系统。如果系统已经 进k t p f p r o b 状态，t r e j l 表示完成恢复重新初始化系统。 1 0 0 1 0 ( 1 ) ) 、州1 一- j t c l o c k 0 1 0 0 1 ( 5 ) 图2 5m r s p n 的转移图 在m r s p n 的转移图中，用( p u p ，p f p r o b ，p d o w n ，p c l o c k ，p r e j ) 来表示某一时 刻系统所处在的状态，如果此时标记处在p x ，贝u p x = i ，而其它的为0 。从s p n 的描述 可以看出，仅有五个可能的状态，分别是( 1 0 0 1 0 ) ，( 0 1 0 1 0 ) ，( 1 0 0 0 1 ) ，( 0 0 1l o ) 和( 0 1 0 0 1 ) 。 椭圆形表示上面提到的五个状态，椭圆形之间的弧线表示这两个状态发生转换的 l o 曼 乏美n 硕士论文软件系统白恢复时间策略研究与实现 原因。用a ，乃，乃，五，五分别表示t f p r o b ，t d o w n ， 速率。万为恢复的时间间隔，用t c l o c k 模拟。 得到了恢复系统的m r s p n 模型以及转移图， 间点，找出从属过程。 t r e j1 ，t u p 和t r e j 2 五个转移的平均 接下来定义系统运行过程中再生时 在恢复系统中，潜在的m r g p 包含五个状态， l ，2 ，3 ，4 ，5 ) 。从系统的运行 情况可以看出，一旦进入1 ，3 ，4 ，5 其中的某个状态，系统可能出现的状态仅由该 状态唯一确定。相反，当系统从状态l 进入状态2 之后，下一个可能出现的状态仍然需 要由t c l o e k 来确定，可能是状态4 ，也可能是状态5 。因此，处于再生时间点的状态 为 l ，3 ，4 ，5 ) ， 从属过程便是这几个状态的之间的转换过程。 从属过程分析包括以下三个部分： 一内部的d t m c ( d i s c r e t e t i m em a r k o vc h a i n ) 中状态转移的概率： k i i ( t ) = p r m ( r l ) = j i m ( r 0 ) = i ) ( 2 1 3 ) 其中表示第n 个再生时间点，m ( t ) 表示在时刻t 过程所处的状态。 一两个连续再生时间点之间的状态转移概率： e i i ( t ) = p r ( m ( t ) = j ，q tlm ( r o ) = i ) ( 2 1 4 ) 从属过程中停留在某一状态的平均时间： 口= j ：e i j ( t ) d t ( 2 1 5 ) 在恢复系统中，由式( 2 1 3 ) 、( 2 1 4 ) 、( 2 1 5 ) 可得： k 1 3 ( t ) = e _ 6 u ( t 一万) ( 2 1 6 ) k 。( t ) 表示的是在时间间隔( o ，万) 里，系统从0 时刻处在状态l ，到下一个再生时 间点进入状态4 的概率。由于其中经过了状态2 ，所以要分成两种情况进行讨论： k 1 4 ( t ) = 1 一釜l e 一如。+ 苎l e 一 o t 艿 a 一九a 一如 1 一一垒一e 一如j + 一二兰乙一e 占 t 万 一如 一如 ( 2 1 7 ) k 。，( t ) 表示的是当系统从o 时刻处在状态l 到恢复时间间隔耗尽时系统还未进入 t d o w n l 拘概率。 k 1 5 ( t ) = 去p 一 u ( t _ 回 ( 2 8 ) 在状态3 ，4 ，5 ，各自都只有唯一的转移可能发生。所以，k 。，( t ) ，i = 3 ，4 ，5 表 示的是在t 时刻各自转移发生的概率。 硕士论文软件系统自恢复时问策略研究与实现 k i l ( t ) = l e 一五ti = 3 ，4 ，5 ( 2 1 9 ) e ；i ( t ) 表示的是从i 再生时间点开始到还未进入j 再生时间点之间系统的运行过程。 e t l ( f ) 表示系统在计时开始的时候处在状态1 ，到t 时间仍然处在状态1 的概率。这 里的t 是间隔【0 ，万】里的值，因为到了万时刻，系统必定会进入状态3 ，出现另一个再生 时间点。 e l l ( t ) = e _ t ( 一u ( t 一劝 ( 2 2 0 ) e l ：( ，) 表示的是当系统在0 时刻处在状态1 ，经过t 时间进入状态2 的概率，这里的t 仍然是【o ，万】里的一个值。 e ：( t ) = 兰- l ；t 一2 e 一如一e 一 ( u ( t ) 一u ( t 一万) ) ( 2 2 1 ) e “( f ) ，i = 3 ，4 ，5 表示的是到t 时刻各自转移没有发生的概率。 e i i ( t ) = e 一 i = 3 ，4 ，5 ( 2 2 2 ) 从属过程中停留在每一个状态的平均时间： 口1 l2 上e l l ( t ) d t = 【l e 。- j 】 ( 2 2 3 ) = f e t 2 ( t ) d t = 去一焘 等一等 =一一-二一l1 名2允l 一名2l 旯2名ij a i i2 上ei i ( t ) d t = 二i = 3 ，4 ，5 = 一 = ( 2 2 4 ) ( 2 2 5 ) 接下来分析整个恢复系统的运行情况： 内部的d t m c ( d i s c r e t et i m em a r k o vc h a i n ) 停留在稳定状态的概率： v j = v j l ( j i ，v i = l ( 2 2 6 ) j i 在恢复系统中，利用式( 2 2 6 ) 可得： vi ： ( 2 2 7 )v i 2 丁 ) 1 2 硕士论文软件系统自恢复时间策略研究与实现 v ，= 三击 e j e 一舻 可以计算m r g p 中的每一个稳定状态i 的概率乃，i = l ，2 ，3 ，4 ，5 。 最终的m r g p 中的稳定状态为 v k 口k j 个吉凌百 软件处在状态3 ，4 ，5 时是不可用的，所以软件不可用的概率为： ( 2 2 8 ) ( 2 2 9 ) ( 2 3 0 ) ( 2 3 1 ) 万d o w n = 7 3 + 万4 + 万5 ( 2 3 2 ) 将乃看作是软件停机时间的一个随机值，在时间间隔【o ，t 】里其期望值为： e 【t d 】- 7 d o w n t ( 2 3 3 ) 在式( 2 3 3 ) 中，对于一个给定的时间值t ，参数a ，五，以，五，以均是已知的，只 有盯未知，对式( 2 3 3 ) 求导，并令结果等于零，便可以求出使得停机时间最少的仃 值，即恢复时间间隔。 2 1 4 改进的m r s p n 模型 该模型【2 7 】是在m r s p n 模型的基础上考虑了软件在运行过程中的存在的实际负载 的情况。因此，在原来的m r s p n 模型上增加了两个转换过程t a r r 和t s e r v e r 以及状态 p l o a d ，用于模拟需要提供服务的请求到达和离开的过程。t a r r 表示服务要求到达的情 形( 假设到达的个数按时间成指数分布) ，p l o a d 模拟的是存放到达的服务请求的缓 冲器。该缓冲器能存放的请求的数量最大为k ( 从p l o a d 至l j t a r r 的连线表示了这种假设) ， t s e r v e 模拟的是软件提供服务的情况，也是成指数分布。不管是由于恢复，还是由于 系统出错不得不重启，两条从p r e j 和p d o w n 至l j t s e r v e 的连线模拟了软件不可用的状态。 最后，从p l o a d 到t u p 以及由p l o a d 到t r e j 的两条连线模拟了软件在还没有恢复到良好状 态的过程中所到达的服务请求都被拒绝的情形。 在该模型的基础上，提出另一种恢复的策略。该策略与在某一给定时间间隔中到 去 占 l z 印 一2 ， + ，一2 一 ，二 一吒2 3 一 驴去 硕士论文软件系统自恢复时间策略研究与实现 达的服务请求有关。此时，恢复的时间确定分为了两个部分，在第一个时间间隔 ( t c l o c k 代表的情形) 之后，系统进入了另外一种状态( p r e j l 表示的情形) ，此时， 系统是否需要进行恢复还需要根据缓冲器中请求的数量来决定。如果此时系统的负载 低于某一给定的阈值( 从p l o a d 到t i m 的表示的情形) ，转移t i m 被即刻触发，系统立即 进行恢复。如果此时系统缓冲器中请求的数量高于该阈值，有必要延缓一小段时间之 后才进行恢复，目的是为了能处理更多的请求，减少系统丢失的服务请求数量。但是， 经过一段时间之后( 也就是延迟时间，其最大值用t c l o c k 2 表示) ，系统会不再考虑缓冲 器中服务请求的数量而强行执行自恢复。 图2 6 改进后的自恢复的m r s p n 模型 1 4 硕士论文 软件系统自恢复时间策略研究与实现 图2 7 该模型的状态转换图 根据该状态转换图以及2 1 4 节中介绍的相关理论知识，可以计算出以该模型为基 础的恢复时间间隔。 2 2 基于阈值的方法 这一节介绍利用设置阈值【4 】的方法计算恢复时间间隔的策略。 在该策略中，人为的提供了一个标准，并时时跟踪软件的运行状况，将当前获得 的衰减参数的值与该标准进行比较，判断是否需要自恢复。 图2 8 描述了使用该策略进行恢复的过程。s a l 表示该阈值。一旦参数s ( t ) 第一次到 达阈值s a l ，系统立即进行恢复。 系统是否需要恢复是由衰减参数的变化情况决定的。通过周期性的监测，如果存 在某个时间间隔点k ，满足s ( ( k - 1 ) a t ) s a l ，( 也就是说，在第( k - 1 ) 个时间间隔时，衰减参数还处于阈值之下，但是到第k 个时间间隔的时候，参数就越 过了阈值。) 但是，在第k 个时间间隔时可能发生两种情况： 1 ) s a l s m a x ，此时在进行恢复之前，系统可能已经出错了。因此s a l 与s m a x 之间的间隔距离决定了系统在进行恢复之前出错的概率。因此，在这一策略中，最重 要的是确定s a l 与s m a x 的比值，即= s m a ) ，根据这个比值可以计算出恢复时间 间隔。 1 5 硕士论文 软件系统自恢复时间策略研究与实现 r e j u v e n a t i o n c r a s h r e j u v e n a t i o n sm a x ? 。1 r 多 一一 2 3 本章小结 图2 8 设置阈值的恢复策略 本章介绍了利用建模和设置阈值的方式来计算恢复时间间隔的方法，着重研究了 m r s p n 模型。 利用建模的方法是通过对软件或者系统在实际运行过程中可能出现的各种状况 进行模拟，以某些假设为前提，比如软件退化的程度只由时间决定，或只由负载决定， 或由二者共同决定，利用相关的数学知识计算恢复时间间隔。 利用阈值的方法是通过时时跟踪系统或者软件的运行状况，对衰减参数进行采 样，将采样结果与实现设定的阈值相比较，从而计算恢复时间间隔。 1 6 硕士论文软件系统自恢复时间策略研究与实现 3 资源占用跟踪 本章的目的是利用w i n 3 2a p i 函数对系统运行过程中的资源占用情况进行采 样，获取资源占用情况。 软件自恢复在系统出错之前采取措施，避免系统出错或者是延缓系统出错的时 间。因此，必须对软件的运行情况进行跟踪，对系统的资源占用情况进行数据采样， 如物理内存、页文件的总量和使用情况。 系统的性能和运行的进程也有关系，所以必须对进程和线程进行监控。包括进程 的进程标识符，用户信息，c p u 使用时间和存储器的使用情况。 本文实验验的平台是w i n d o w sx p 系统，采样的数据是系统的资源占用情况， 所以使用的主要是w i n 3 2a p i 函数中的系统函数。 系统服务函数为应用程序提供了访问计算机资源以及底层操作系统特性的手段， 比如访问内存、文件系统、设备、进程和线程。应用程序使用系统服务函数来管理和 监视它所需要的资源。例如，应用程序可使用内存管理函数来分配和释放内存，使用 进程管理和同步函数来启动和调整多个应用程序或在一个应用程序中运行的多个线 程的操作。 3 1 系统内存的占用情况 软件在正常执行的时候，必须对资源的使用进行细致的分配和管理，保持良好的 性能。对于长时间运行的应用程序，如果存在不恰当的资源分配，经过一段时的积累 之后，系统性能严重下降，需要进行恢复。图3 1 是三个系统资源分配不合理的例子1 2 0 j 。 例子( a ) 存在内存泄露的问题。指针p t r 2 所指向的内存区域在程序的循环过程中被 “泄露”掉了。当循环开始的时候，p t r 2 指向了另一块内存区域，之前分配的那一块 内存块没用但是却不能被再利用了。由于内存的泄露，程序最终会因为内存不够而被 迫出错。内存泄露通常出现在某些存在复杂而又繁琐的流程控制的程序设计中，在这 些程序的某些执行路径中，正确的内存存储单元的分配会被丢失掉。 例子( b ) 中描述的是内存潜在的例子。对于有3 0 岁g 字节交换空间的系统，当执行 至l j i = l 时，代码会意想不到地停止，因为，系统为了执行效率高，在i = 0 时每次分配的 3 6 个字节的小的内存分配单元是不会被接合而成为内存碎片，因此，在做2 0 ；1 k 字节的 内存分配的时候，这1 6 ；i g 字节的内存不能被再利用了。这种现象通常在标准的或者用 户自身设计的内存管理程序中出现。严格意义上说，内存潜在只是性能好坏的一个特 征，并不是内存泄露，但是当应用程序耗尽所有的内存，而且不管使用什么方法都无 硕士论文软件系统自恢复时间策略研究与实现 法回收潜在的内存，从而导致程序出错，内存潜在从某种意义上来说也是内存泄露。 例子( c ) 中描述的是内存再利用率不高的情况。仍然假定系统的交换空间为3 0 兆字 节，该程序会在i = 1 6 的时候就退出，并非在i = 3 0 的时候。这是因为在进行1 6 兆字节内 存分配的时候，之前分配的1 5 兆字节的内存不能被再利用了，导致分配失败，因为只 剩下1 5 兆字节的内存了，而退出程序。这三个例子表明在长时间运行的程序中，不合 理的内存分配会导致程序过早的退出或者不正确的结束，尽管此时系统仍然有足够的 物理内存满足程序的内存要求。由于系统内存资源的不合理分配和应用，会使得系统 性能在运行过程中逐步衰退。 图3 1 内存分配不合理的例子 不存在性能下降的软件是不需要恢复的，为了计算恢复时间间隔，编写了 一段存在内存泄漏的代码模拟了软件退化现象。 在该程序运行的前提下，接下来对系统的内存使用情况进行采样。 w i n d o w s 函数g l o b a l m e m o r y s t a t u s 用于检索当前内存使用情况的动态信息 4 1 ： v o i dg l o b a l m e m o r y s t a t u s ( l p m e m o r y s t a t u sp m s 0 ； 当调用g l o b a l m e m o r y s t a t u s i 函数时，必须传递一个m e m o r y s t a t u s 结构的地址 p m s t 。下面显示了m e m o r y s t a t u s 的数据结构。 1 8 硕士论文软件系统自恢复时间策略研究与实现 t y p e d e f s t r u c t m e m o r y s 。i a i u s d w o r dd w l e n g t h ； d w o r dd w m e m o r y l o a d ； s i z e td w t o t a l p h y s ； s i z e td w a v a i l p h y ； s i z e td w t o t a l p a g e f i l e ； s i z e td w a v i a l p a g e f i l e ； s i z e t d w t o t a l v i r t u a l ； s i z e t d w a v a i l v i r t u a l ； ) m e m o r y s t a t u s ，l p m e m o r y s t a t u s ； 在调用g l o b a l m e m o r y s t a t u s 函数之前，必须将d w l e n g t h 成员初始化为用字节表示 的结构大小，即一个m e m o r y s t a t u s 结构的大小。这个初始化操作使得m i c r o s o t t 能够将成员添加给将来的w i n d o w s 版本中的这个结构，而不会破坏现有的应用程序。 当调用g l o b a l m e m o r y s t a t u s 时，它将对该结构的其余成员进行初始化并返回。 下面对该结构中的其他成员作详细的介绍： d w m e m o r y l o a d 成员给出了内存管理系统的大致繁