门朝光，徐振朋，李 香

(哈尔滨工程大学高可信计算技术研究中心，哈尔滨 150001，menchaoguang@hrbeu.edu.cn)

移动计算系统检查点迁移策略的性能评价

门朝光，徐振朋，李 香

(哈尔滨工程大学高可信计算技术研究中心，哈尔滨 150001，menchaoguang@hrbeu.edu.cn)

为了有效评估移动计算系统检查点迁移处理策略的性能，基于移动计算系统自身所具有的特性，给出了移动计算系统中的进程状态模型，并在此基础上提出了一种移动计算系统检查点迁移处理策略性能评价模型.利用该性能评价模型对当前的3种日志检查点迁移策略进行了仿真实验，结果显示该模型与实际情况相吻合，从而验证了此性能评价模型的有效性.该检查点迁移处理策略性能评价模型可用于确定不同移动计算环境下相对适用的检查点迁移处理策略.

移动计算;容错;检查点;握手迁移

检查点迁移处理策略是移动计算系统检查点卷回恢复策略中不可或缺的基本构成要素［1－7］.目前移动主机检查点迁移处理策略性能评价的主要方法是使用简单数学量化或实际计算环境测试方法［8－9］.简单数学量化法往往不能准确地反映检查点迁移策略的性能;实际计算环境中验证容错策略则需要周密复杂的系统规划和设计，不易实现.目前，尚没有一种简单有效的检查点迁移策略性能评价方法，能够实现对移动计算系统中各检查点迁移处理策略的性能进行快速有效的评估.为此，依据移动计算的进程状态模型，本文提出一种移动计算检查点迁移处理策略的性能评价方法.

1 移动计算系统模型

移动计算系统的系统模型可表示为MCS=〈N，C〉，是由节点集合N和信道集合C组成，如图1所示.节点集合N包括两种主机(N=M∪S)，移动主机(MH)集合 M={MH1，MH2，…，MHn}和移动支持站(MSS)集合 S={MSS1，MSS2，…，MSSm}.移动主机具有较小的处理能力和存储空间，移动支持站是静态节点，拥有较高的处理能力和可靠的存储器.通信信道C由两部分组成(C=W∪W′)，移动支持站间高速的有线通信信道W(W=S×S)和移动支持站与移动主机间相对低速的无线通信信道W′(W′=S×M).MSSi为第i个移动支持站，MHi为第i个移动主机.地理上，由一MSSi覆盖的一个通信区域称作一个组(CELL)，在组 CELLi中的移动支持站MSSi被本组MHs称为本地移动支持站.每个移动支持站(MSSi)上存在集合CLi={MHj|MHj∈MSSi，0＜j＜n+1}记录本组中的移动主机，子集Active－MH－Listi记录活动的移动主机，子集Disconnected－MH－Listi记录休眠的移动主机.一个移动主机在某一时刻只属于一个组，即满足条件 MHj∈ CLi⇒ MHj∉ CLk，∀k≠ i.任一 MHj可以直接通过无线信道〈MSSi，MHj〉∈W′连接到服务于该组的本地MSSi上，并且通过本地的MSSi与其它的MH或MSS通信.

图1 移动计算系统模型

移动计算系统包含N个独立计算进程P1，P2，…，PN.每个进程周期性地存储其局部状态到稳定存储器中以产生局部检查点.每个检查点被分配了唯一的检查点序号CSN(checkpoint sequence number).进程Pk的第i(i≥0)个检查点被分配了序号 i，表示为 Ck，i.任何存在于 Ck，i－1和 Ck，i之间的事件 ek，x被称作“ek，x属于 Ck，i”，表示为 ek，x∈ Ck，i.故障为“fail-stop”形式，一旦进程失效，该进程将立即停止执行，不会产生任何恶意的行为.当进程发生故障时，存储在MH或MSS内存中的内容可能会被破坏或丢失，而可靠存储器中的内容可以用来恢复主机进程.网络连接支持双向的FIFO通信，且假定消息的传输是可靠的.网络中消息的传输延迟在一定时间范围内是任意的.

2 移动计算系统检查点容错策略

移动计算检查点卷回恢复策略由3个基本部分构成:进程状态检查点创建、移动主机迁移处理与进程卷回恢复［10－12］.

2.1 进程状态保存策略

由于移动主机存储器容量有限且不可靠，现有容错策略中都利用移动支持站上的可靠存储器存储系统进程状态.两种最基本的进程状态保存方法是基于检查点和基于消息日志的检查点策略.目前的移动计算检查点卷回恢复容错策略都使用基于消息日志的检查点策略.

基于消息日志的检查点容错策略同时使用了检查点和消息日志技术，进程除了在设定时刻创建检查点外，相应的消息事件也要保存到可靠存储介质上.移动主机间不能直接通信，其接收或发送的消息需经过一个或多个移动支持站转发，因此利用移动支持站记录转发的消息不会引入过多的额外开销，且能保证日志记录的同步.记录消息日志的方式可分为悲观、乐观和因果消息日志.

2.2 检查点迁移处理策略

由于目前检查点容错策略都是利用移动支持站的可靠存储器来存储主机进程状态和消息日志，移动主机在不同的移动支持站组间移动时，其检查点和相关消息日志会分散在不同的移动支持站上.一旦移动主机计算进程发生故障，恢复策略必须定位其检查点和相关消息日志所在的移动支持站，即提供检查点迁移处理策略以保证故障主机及时正确地得到其全部恢复信息.

如图1 所示，MH1、MH2、MH3、MH4在共同执行一分布式计算程序.某一时刻，MH2创建一检查点并保存在其本地移动支持站MSS2上.在随后执行过程中，MH2迁移到MSS1组中，其后又迁移到MSS3组中.两次迁移分别发生在组CELL2与CELL1、CELL1与CELL3的交界处.在组CELL3中某时刻MH2发生一计算故障.由于MSS3上未存储MH2最近的检查点和消息日志.所以检查点迁移策略必须保证进程故障主机能正确获得其检查点和相关消息日志.目前3种检查点迁移处理策略为:急切(Eager)迁移策略、懒惰(Lazy)迁移策略和折衷(Trickle)迁移策略.各检查点迁移处理策略会给移动计算系统引入不同程度的开销.

2.3 进程卷回恢复方式

移动主机计算进程发生故障后，进程重启并向本地移动支持站发送卷回恢复请求.当移动主机从本地移动支持站获取到最新检查点后，重载进程检查点.若采用基于消息日志的检查点卷回恢复策略，移动主机故障卷回进程将在移动支持站的协助下重放消息日志，最终恢复到故障前状态后继续运行.恢复可分为同步恢复和异步恢复.

移动计算系统的低无线网络带宽、节点可移动、电池供给有限、移动存储空间有限及其易失等特性，使得整个移动计算系统的故障概率远远高于传统有线分布式计算系统.因此，在容错策略中，选择高效适用的移动主机检查点迁移策略，使相应的移动计算检查点卷回恢复策略性能达到最优，对移动计算系统的可靠性和高效性尤为重要.

3 性能评价

3.1 系统进程的状态模型

在计算进程的运行过程中引入检查点操作后，计算任务的执行过程由一段段的进程检查点间隔组成.进程的第i个检查点间隔由其检查点Ck，i－1和 Ck，i之间的所有事件构成，包含第 i个检查点 Ck，i－1，但不包含第 i+1 个检查点 Ck，i.在一个检查点间隔中，有两种意外的事件可能会发生:计算进程故障(f)和移动主机迁移(h)事件.假定某个主机无迁移事件的情况下，其计算进程无故障执行时间为Y.Y(f，h)为在可能出现进程故障与主机迁移事件的情况下，此进程所需的执行时间.GY(t)为随机变量Y的累计分布函数，则其拉普拉斯变换为

由式(1)可知，若Y′与Y是相互独立同分布的随机变量，则有 φY′(s)= φY(s).

如图2所示，为简化求解进程检查点间隔的执行用时，区别于文献［13］，采用5－状态的离散马尔科夫链表示检查点间隔期间的进程状态.状态1为检查点间隔开始时进程创建检查点的状态;状态2为计算进程正常执行状态，此状态中移动主机能处理接收消息和外部输入输出提交;状态3为移动主机迁移时的处理过程;状态4为移动主机进程发生故障后的卷回处理过程，此过程中移动主机获取最近的检查点信息，并重载检查点;状态5为移动主机计算进程卷回恢复过程，此过程将对该检查点间隔重新处理，重复损失的计算过程，一直恢复到计算进程故障前的正确状态.模型中进程间消息率服从参数为λ的泊松分布，各移动主机计算进程发生故障概率满足参数为γ的泊松分布，并且移动主机连续两次迁移事件时间间隔满足参数为ρ的指数分布.

如果在一个进程检查点间隔执行过程中，没有出现任何进程故障或主机迁移事件，此检查点间隔会成功结束而进入下一个检查点间隔.如果在此检查点间隔中，处在正常运行状态2的移动主机进程出现了迁移事件，则其计算进程会转入状态3.当相应的迁移处理过程结束后，进程会从状态3转入状态2继续运行.如果在正常运行过程中有故障事件发生，则计算进程转入到状态4.当移动主机收集到所需的恢复信息并重载检查点完成后，进程会转入状态5进入恢复过程.在状态5中，计算进程仍有可能发生故障转入到状态4.最终进程会恢复到故障前的时刻转入状态2继续正常运行.在此检查点间隔计算过程成功结束时，计算进程会转入到状态1开始下一个检查点间隔.

图2 检查点间隔的马尔科夫链表示形式

计算进程在状态4和状态5的处理时间是由其故障损失的计算引起的.在移动主机迁移处理过程中，移动支持站暂不会向其转发新的计算消息，只有当主机迁移处理过程完毕后，计算消息才被顺次转发到迁移移动主机.本文的进程状态模型中，在移动主机迁移时，不会出现进程故障事件.为了不失一般性，各计算进程初始时先创建一检查点(即各计算进程都从状态1开始).

3.2 性能评价模型

如图2所示，移动主机MH的计算进程进入到其第N个检查点间隔IN，n为此检查点间隔内进程要处理的消息事件数，在不出现移动主机迁移和进程故障事件情况下该检查点间隔IN需要的执行时间为Tn，则Tn满足参数为λ和n的爱尔朗分布.此间隔内有可能发生移动主机迁移事件，即从进程状态2到状态3的转化;H为移动主机迁移处理过程的时间开销;R为故障计算进程卷回时收集恢复信息并重载检查点所花费的时间开销，即是进程在状态4的停留时间;本文在消息传输时间上的分析基于两移动主机间距离的跳数，并假定相邻移动支持站间的跳数为1.Tn(f，h) 为可能出现移动主机迁移和进程故障情况下完成该检查点间隔IN所需要的时间.

X为自检查点间隔IN开始后计算进程发生故障时刻.Y为自检查点间隔IN开始后移动主机发生迁移事件的时刻.如果Tn≤X且Tn≤Y，则此进程检查点间隔在执行期间没出现任何故障和移动主机迁移事件;如果Tn≤X且Tn＞Y，则在此检查点间隔中移动主机出现了迁移事件，进程迁移处理时间为ρTnH;如果Tn＞X，则表示在此检查点间隔中移动主机出现了故障，此时移动主机需要用时间R来收集相应的系统状态信息并重载检查点，然后从此检查点开始恢复到计算进程故障前状态，这意味着进程故障前的部分计算将会被重演.在卷回恢复完成后，移动主机运行的进程转入到状态 2，继续正常执行.假定在恢复重演过程中执行某一操作的故障概率与正常执行时的故障概率相同，则完成此检查点间隔的时间为R+X+X+(Tn(f，h)－X).由讨论可得检查点间隔IN完成时间Tn(f，h)的分段函数为

进一步整理式(4)可以得到此检查点间隔实际完成时间Tn(f，h)的拉普拉斯变换，即

利用拉普拉斯变换的性质［14］，在可能出现进程故障和移动主机迁移事件的情况下，此检查点间隔实际完成时间Tn(f，h)的数学期望为

4 实例与仿真

在移动计算系统环境中，无线链路带宽为W′=1 M，有线链路带宽为W=20 M，计算消息和控制消息的大小分别为0. 5，0.1 M，λ=0. 008，ρ=0. 005，重载检查点的时间为0.05 s，创建检查点时间的数学期望为1.5 s，采用等消息间隔的检查点方式，每个检查点间隔处理200条消息事件.检查点间隔IN完成时间Tn(f，h)的数学期望可由式(6)得到.为了更好地对比不同检查点迁移策略下检查点间隔IN完成时间的差异，用差率D表示某一检查点迁移策略下IN完成时间与3种策略下IN完成时间均值之比.

结合移动计算系统的日志检查点卷回恢复策略，图3为不同检查点迁移策略和进程故障率情况下IN完成时间差率D的对比情况.

图3 不同故障率下3种检查点迁移策略对比

如图3所示，在进程故障率γ较低的情况下，懒惰迁移策略具有相对较好的性能，这是由于懒惰迁移策略在迁移处理时传输的恢复信息量较小.当进程故障率γ较高时，急切迁移策略则具有相对较好的性能，这是由于急切迁移策略能更好的保证故障进程恢复速度.折衷迁移策略总能得到相对折衷的性能.此结果正好符合了3种检查点迁移策略的实际情况，验证了本文性能评价方法的有效性.

在移动主机进程故障率γ=0.001的情况下，图4为不同检查点迁移策略和移动主机迁移率ρ情况下进程检查点间隔IN的完成时间差率D.如图4所示，在移动主机迁移率.ρ较低的情况下，各检查点迁移策略的性能没有大的差别.当移动主机迁移率ρ较高时，懒惰迁移策略具有相对较好的性能.折衷迁移策略总能得到相对懒惰与急切之间折衷的性能.此结果也正好符合了3种检查点迁移策略的实际情况，验证了本文性能评价方法的有效性.

图4 不同主机迁移率下3种检查点迁移策略对比

通过大量类似的仿真评估，在消息率λ较高、移动主机迁移率ρ较高和进程故障率γ较低的情况下，懒惰迁移处理策略会具有相对较好的性能;而在消息率λ较低、移动主机迁移率ρ较高、无线带宽较窄和进程故障率γ较高的情况下，折衷迁移处理策略则会具有相对较好的性能.

与具体的移动计算系统消息日志检查点卷回恢复策略相结合，利用所提出的检查点迁移策略性能评价方法，本文得到了不同移动计算环境下相对适用的检查点迁移处理策略，如表1所示.

表1 适用检查点迁移处理策略表

5 结论

1)结合具体的日志检查点卷回恢复策略和系统参数，对各检查点迁移处理方式对系统检查点容错性能的影响进行了评估，结果符合3种检查点迁移策略的实际情况，从而验证了该模型的有效性.

2)利用该性能评价模型得出了不同移动计算环境下相对适用的检查点迁移处理策略.

［1］杨金民，张大方，黎文伟.一种可靠高效的回卷恢复实现方法［J］.电子学报， 2006，34(2):237－240.

［2］汪东升，邵明珑.具有O(n)消息复杂度的协调检查点设置算法［J］.软件学报， 2003，14(1)43－48.

［3］李庆华，蒋廷耀，张红君.一种面向移动计算的低代价透明检查点恢复协议［J］.软件学报， 2005，16(1):135－144.

［4］ELNOZAHY E N，ALVISI L，WANG Y M，et al.A survey of rollback-recovery protocols in message-passing systems［J］.ACM Computing Surveys， 2002，34(3):375－408.

［5］LI Guohui，WANG Hongya.A novel min-process checkpointing scheme for mobile computing systems［J］.Journal of Systems Architecture:the EUROMICRO Journal， 2005，51(1):45－61.

［6］CAO G H，SINGHAL M.Checkpointing with mutable checkpoints［J］.Theoretical Computer Science， 2003，290(2):1127－1148.

［7］PARK T，WOO N，YEOM H Y.An efficient optimistic message logging scheme for recoverable mobile computing systems［J］.IEEE Transactions on Mobile Computing， 2002，1(4):265－277.

［8］PRADHAN D K，KRISHNA P，VAIDAY N H.Recoverable mobile environment:design and trade-off analysis［C］//Proceedings of the The Twenty-Sixth Annual International Symposium on Fault-Tolerant Computing.Washington:IEEE Computer Society，1996:16－25.

［9］CHEN I R，GU Baoshan，GEORGE S E，et al.On failure recoverability of client-server applications in mobile wireless environments［J］.IEEE Transactions on Reliability， 2005，54(1):115－122.

［10］LI Guohui，SHU Lihchyun.Design and evaluation of a lowlatency checkpointing scheme for mobile computing systems［J］.The Computer Journal， 2006，49(5):527 －540.

［11］KUMAR L，MISHRA M，JOSHI R C.Low overhead optimal checkpointing for mobile distributed systems［C］//The 19th International Conference on Data Engineering.［S.l.］:［s.n.］，2003:686 －688.

［12］HIRAKAWA T，HIGAKI H.Stable storage for wireless multi-hop access network［J］.IEIC Technical Report， 2006，105(628):359－364.

［13］CHEN Xinyu，LYU M R.Performance and effectiveness analysis of checkpointing in mobile environments［C］//The Proceedings of the 22nd International Symposium on Reliable Distributed Systems.Washington:IEEE Computer Society，2003:131－140.

［14］TANUSHEV M S，ARRATIA R.Central limit theorem for renewal theory for several patterns［J］.Journal of Computational Biology， 1997，4(1):35－44.

The performance evaluation of checkpoint handoff scheme for the mobile computing system

MEN Chao-guang，XU Zhen-peng，LI Xiang

(R＆D Center of High Dependability Computing Technology，Harbin Engineering University，Harbin 150001，China，menchaoguang@hrbeu.edu.cn)

To effectively evaluate the performance of checkpoint handoff scheme for mobile computing system，a model of process state in the mobile system is presented，and then a performance evaluation model for the checkpoint handoff scheme is proposed，according to the characteristics of mobile computing system.The simulation experiments for three existing logging checkpoint recovery schemes have been implemented by the proposed performance evaluation model.The result shows that the performance evaluation model is consistent with practical cases，which proves its validity.By the proposed model of performance evaluation，the proper checkpoint handoff scheme can be determined for a specific mobile computing environment.

mobile computing;fault tolerance;checkpoint;handoff

TP302

A

0367－6234(2010)05－0806－05

2008－09－25.

国家自然科学基金资助项目(60873138).

门朝光(1963—)，男，教授.

(编辑 张 红)