門朝光，徐振朋，李 香

(哈爾濱工程大學高可信計算技術研究中心，哈爾濱 150001，menchaoguang@hrbeu.edu.cn)

移動計算系統(tǒng)檢查點遷移策略的性能評價

門朝光，徐振朋，李 香

(哈爾濱工程大學高可信計算技術研究中心，哈爾濱 150001，menchaoguang@hrbeu.edu.cn)

為了有效評估移動計算系統(tǒng)檢查點遷移處理策略的性能，基于移動計算系統(tǒng)自身所具有的特性，給出了移動計算系統(tǒng)中的進程狀態(tài)模型，并在此基礎上提出了一種移動計算系統(tǒng)檢查點遷移處理策略性能評價模型.利用該性能評價模型對當前的3種日志檢查點遷移策略進行了仿真實驗，結果顯示該模型與實際情況相吻合，從而驗證了此性能評價模型的有效性.該檢查點遷移處理策略性能評價模型可用于確定不同移動計算環(huán)境下相對適用的檢查點遷移處理策略.

移動計算;容錯;檢查點;握手遷移

檢查點遷移處理策略是移動計算系統(tǒng)檢查點卷回恢復策略中不可或缺的基本構成要素［1－7］.目前移動主機檢查點遷移處理策略性能評價的主要方法是使用簡單數(shù)學量化或?qū)嶋H計算環(huán)境測試方法［8－9］.簡單數(shù)學量化法往往不能準確地反映檢查點遷移策略的性能;實際計算環(huán)境中驗證容錯策略則需要周密復雜的系統(tǒng)規(guī)劃和設計，不易實現(xiàn).目前，尚沒有一種簡單有效的檢查點遷移策略性能評價方法，能夠?qū)崿F(xiàn)對移動計算系統(tǒng)中各檢查點遷移處理策略的性能進行快速有效的評估.為此，依據(jù)移動計算的進程狀態(tài)模型，本文提出一種移動計算檢查點遷移處理策略的性能評價方法.

1 移動計算系統(tǒng)模型

移動計算系統(tǒng)的系統(tǒng)模型可表示為MCS=〈N，C〉，是由節(jié)點集合N和信道集合C組成，如圖1所示.節(jié)點集合N包括兩種主機(N=M∪S)，移動主機(MH)集合 M={MH1，MH2，…，MHn}和移動支持站(MSS)集合 S={MSS1，MSS2，…，MSSm}.移動主機具有較小的處理能力和存儲空間，移動支持站是靜態(tài)節(jié)點，擁有較高的處理能力和可靠的存儲器.通信信道C由兩部分組成(C=W∪W′)，移動支持站間高速的有線通信信道W(W=S×S)和移動支持站與移動主機間相對低速的無線通信信道W′(W′=S×M).MSSi為第i個移動支持站，MHi為第i個移動主機.地理上，由一MSSi覆蓋的一個通信區(qū)域稱作一個組(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 移動計算系統(tǒng)模型

移動計算系統(tǒng)包含N個獨立計算進程P1，P2，…，PN.每個進程周期性地存儲其局部狀態(tài)到穩(wěn)定存儲器中以產(chǎn)生局部檢查點.每個檢查點被分配了唯一的檢查點序號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”形式，一旦進程失效，該進程將立即停止執(zhí)行，不會產(chǎn)生任何惡意的行為.當進程發(fā)生故障時，存儲在MH或MSS內(nèi)存中的內(nèi)容可能會被破壞或丟失，而可靠存儲器中的內(nèi)容可以用來恢復主機進程.網(wǎng)絡連接支持雙向的FIFO通信，且假定消息的傳輸是可靠的.網(wǎng)絡中消息的傳輸延遲在一定時間范圍內(nèi)是任意的.

2 移動計算系統(tǒng)檢查點容錯策略

移動計算檢查點卷回恢復策略由3個基本部分構成:進程狀態(tài)檢查點創(chuàng)建、移動主機遷移處理與進程卷回恢復［10－12］.

2.1 進程狀態(tài)保存策略

由于移動主機存儲器容量有限且不可靠，現(xiàn)有容錯策略中都利用移動支持站上的可靠存儲器存儲系統(tǒng)進程狀態(tài).兩種最基本的進程狀態(tài)保存方法是基于檢查點和基于消息日志的檢查點策略.目前的移動計算檢查點卷回恢復容錯策略都使用基于消息日志的檢查點策略.

基于消息日志的檢查點容錯策略同時使用了檢查點和消息日志技術，進程除了在設定時刻創(chuàng)建檢查點外，相應的消息事件也要保存到可靠存儲介質(zhì)上.移動主機間不能直接通信，其接收或發(fā)送的消息需經(jīng)過一個或多個移動支持站轉發(fā)，因此利用移動支持站記錄轉發(fā)的消息不會引入過多的額外開銷，且能保證日志記錄的同步.記錄消息日志的方式可分為悲觀、樂觀和因果消息日志.

2.2 檢查點遷移處理策略

由于目前檢查點容錯策略都是利用移動支持站的可靠存儲器來存儲主機進程狀態(tài)和消息日志，移動主機在不同的移動支持站組間移動時，其檢查點和相關消息日志會分散在不同的移動支持站上.一旦移動主機計算進程發(fā)生故障，恢復策略必須定位其檢查點和相關消息日志所在的移動支持站，即提供檢查點遷移處理策略以保證故障主機及時正確地得到其全部恢復信息.

如圖1 所示，MH1、MH2、MH3、MH4在共同執(zhí)行一分布式計算程序.某一時刻，MH2創(chuàng)建一檢查點并保存在其本地移動支持站MSS2上.在隨后執(zhí)行過程中，MH2遷移到MSS1組中，其后又遷移到MSS3組中.兩次遷移分別發(fā)生在組CELL2與CELL1、CELL1與CELL3的交界處.在組CELL3中某時刻MH2發(fā)生一計算故障.由于MSS3上未存儲MH2最近的檢查點和消息日志.所以檢查點遷移策略必須保證進程故障主機能正確獲得其檢查點和相關消息日志.目前3種檢查點遷移處理策略為:急切(Eager)遷移策略、懶惰(Lazy)遷移策略和折衷(Trickle)遷移策略.各檢查點遷移處理策略會給移動計算系統(tǒng)引入不同程度的開銷.

2.3 進程卷回恢復方式

移動主機計算進程發(fā)生故障后，進程重啟并向本地移動支持站發(fā)送卷回恢復請求.當移動主機從本地移動支持站獲取到最新檢查點后，重載進程檢查點.若采用基于消息日志的檢查點卷回恢復策略，移動主機故障卷回進程將在移動支持站的協(xié)助下重放消息日志，最終恢復到故障前狀態(tài)后繼續(xù)運行.恢復可分為同步恢復和異步恢復.

移動計算系統(tǒng)的低無線網(wǎng)絡帶寬、節(jié)點可移動、電池供給有限、移動存儲空間有限及其易失等特性，使得整個移動計算系統(tǒng)的故障概率遠遠高于傳統(tǒng)有線分布式計算系統(tǒng).因此，在容錯策略中，選擇高效適用的移動主機檢查點遷移策略，使相應的移動計算檢查點卷回恢復策略性能達到最優(yōu)，對移動計算系統(tǒng)的可靠性和高效性尤為重要.

3 性能評價

3.1 系統(tǒng)進程的狀態(tài)模型

在計算進程的運行過程中引入檢查點操作后，計算任務的執(zhí)行過程由一段段的進程檢查點間隔組成.進程的第i個檢查點間隔由其檢查點Ck，i－1和 Ck，i之間的所有事件構成，包含第 i個檢查點 Ck，i－1，但不包含第 i+1 個檢查點 Ck，i.在一個檢查點間隔中，有兩種意外的事件可能會發(fā)生:計算進程故障(f)和移動主機遷移(h)事件.假定某個主機無遷移事件的情況下，其計算進程無故障執(zhí)行時間為Y.Y(f，h)為在可能出現(xiàn)進程故障與主機遷移事件的情況下，此進程所需的執(zhí)行時間.GY(t)為隨機變量Y的累計分布函數(shù)，則其拉普拉斯變換為

由式(1)可知，若Y′與Y是相互獨立同分布的隨機變量，則有 φY′(s)= φY(s).

如圖2所示，為簡化求解進程檢查點間隔的執(zhí)行用時，區(qū)別于文獻［13］，采用5－狀態(tài)的離散馬爾科夫鏈表示檢查點間隔期間的進程狀態(tài).狀態(tài)1為檢查點間隔開始時進程創(chuàng)建檢查點的狀態(tài);狀態(tài)2為計算進程正常執(zhí)行狀態(tài)，此狀態(tài)中移動主機能處理接收消息和外部輸入輸出提交;狀態(tài)3為移動主機遷移時的處理過程;狀態(tài)4為移動主機進程發(fā)生故障后的卷回處理過程，此過程中移動主機獲取最近的檢查點信息，并重載檢查點;狀態(tài)5為移動主機計算進程卷回恢復過程，此過程將對該檢查點間隔重新處理，重復損失的計算過程，一直恢復到計算進程故障前的正確狀態(tài).模型中進程間消息率服從參數(shù)為λ的泊松分布，各移動主機計算進程發(fā)生故障概率滿足參數(shù)為γ的泊松分布，并且移動主機連續(xù)兩次遷移事件時間間隔滿足參數(shù)為ρ的指數(shù)分布.

如果在一個進程檢查點間隔執(zhí)行過程中，沒有出現(xiàn)任何進程故障或主機遷移事件，此檢查點間隔會成功結束而進入下一個檢查點間隔.如果在此檢查點間隔中，處在正常運行狀態(tài)2的移動主機進程出現(xiàn)了遷移事件，則其計算進程會轉入狀態(tài)3.當相應的遷移處理過程結束后，進程會從狀態(tài)3轉入狀態(tài)2繼續(xù)運行.如果在正常運行過程中有故障事件發(fā)生，則計算進程轉入到狀態(tài)4.當移動主機收集到所需的恢復信息并重載檢查點完成后，進程會轉入狀態(tài)5進入恢復過程.在狀態(tài)5中，計算進程仍有可能發(fā)生故障轉入到狀態(tài)4.最終進程會恢復到故障前的時刻轉入狀態(tài)2繼續(xù)正常運行.在此檢查點間隔計算過程成功結束時，計算進程會轉入到狀態(tài)1開始下一個檢查點間隔.

圖2 檢查點間隔的馬爾科夫鏈表示形式

計算進程在狀態(tài)4和狀態(tài)5的處理時間是由其故障損失的計算引起的.在移動主機遷移處理過程中，移動支持站暫不會向其轉發(fā)新的計算消息，只有當主機遷移處理過程完畢后，計算消息才被順次轉發(fā)到遷移移動主機.本文的進程狀態(tài)模型中，在移動主機遷移時，不會出現(xiàn)進程故障事件.為了不失一般性，各計算進程初始時先創(chuàng)建一檢查點(即各計算進程都從狀態(tài)1開始).

3.2 性能評價模型

如圖2所示，移動主機MH的計算進程進入到其第N個檢查點間隔IN，n為此檢查點間隔內(nèi)進程要處理的消息事件數(shù)，在不出現(xiàn)移動主機遷移和進程故障事件情況下該檢查點間隔IN需要的執(zhí)行時間為Tn，則Tn滿足參數(shù)為λ和n的愛爾朗分布.此間隔內(nèi)有可能發(fā)生移動主機遷移事件，即從進程狀態(tài)2到狀態(tài)3的轉化;H為移動主機遷移處理過程的時間開銷;R為故障計算進程卷回時收集恢復信息并重載檢查點所花費的時間開銷，即是進程在狀態(tài)4的停留時間;本文在消息傳輸時間上的分析基于兩移動主機間距離的跳數(shù)，并假定相鄰移動支持站間的跳數(shù)為1.Tn(f，h) 為可能出現(xiàn)移動主機遷移和進程故障情況下完成該檢查點間隔IN所需要的時間.

X為自檢查點間隔IN開始后計算進程發(fā)生故障時刻.Y為自檢查點間隔IN開始后移動主機發(fā)生遷移事件的時刻.如果Tn≤X且Tn≤Y，則此進程檢查點間隔在執(zhí)行期間沒出現(xiàn)任何故障和移動主機遷移事件;如果Tn≤X且Tn＞Y，則在此檢查點間隔中移動主機出現(xiàn)了遷移事件，進程遷移處理時間為ρTnH;如果Tn＞X，則表示在此檢查點間隔中移動主機出現(xiàn)了故障，此時移動主機需要用時間R來收集相應的系統(tǒng)狀態(tài)信息并重載檢查點，然后從此檢查點開始恢復到計算進程故障前狀態(tài)，這意味著進程故障前的部分計算將會被重演.在卷回恢復完成后，移動主機運行的進程轉入到狀態(tài) 2，繼續(xù)正常執(zhí)行.假定在恢復重演過程中執(zhí)行某一操作的故障概率與正常執(zhí)行時的故障概率相同，則完成此檢查點間隔的時間為R+X+X+(Tn(f，h)－X).由討論可得檢查點間隔IN完成時間Tn(f，h)的分段函數(shù)為

進一步整理式(4)可以得到此檢查點間隔實際完成時間Tn(f，h)的拉普拉斯變換，即

利用拉普拉斯變換的性質(zhì)［14］，在可能出現(xiàn)進程故障和移動主機遷移事件的情況下，此檢查點間隔實際完成時間Tn(f，h)的數(shù)學期望為

4 實例與仿真

在移動計算系統(tǒng)環(huán)境中，無線鏈路帶寬為W′=1 M，有線鏈路帶寬為W=20 M，計算消息和控制消息的大小分別為0. 5，0.1 M，λ=0. 008，ρ=0. 005，重載檢查點的時間為0.05 s，創(chuàng)建檢查點時間的數(shù)學期望為1.5 s，采用等消息間隔的檢查點方式，每個檢查點間隔處理200條消息事件.檢查點間隔IN完成時間Tn(f，h)的數(shù)學期望可由式(6)得到.為了更好地對比不同檢查點遷移策略下檢查點間隔IN完成時間的差異，用差率D表示某一檢查點遷移策略下IN完成時間與3種策略下IN完成時間均值之比.

結合移動計算系統(tǒng)的日志檢查點卷回恢復策略，圖3為不同檢查點遷移策略和進程故障率情況下IN完成時間差率D的對比情況.

圖3 不同故障率下3種檢查點遷移策略對比

如圖3所示，在進程故障率γ較低的情況下，懶惰遷移策略具有相對較好的性能，這是由于懶惰遷移策略在遷移處理時傳輸?shù)幕謴托畔⒘枯^小.當進程故障率γ較高時，急切遷移策略則具有相對較好的性能，這是由于急切遷移策略能更好的保證故障進程恢復速度.折衷遷移策略總能得到相對折衷的性能.此結果正好符合了3種檢查點遷移策略的實際情況，驗證了本文性能評價方法的有效性.

在移動主機進程故障率γ=0.001的情況下，圖4為不同檢查點遷移策略和移動主機遷移率ρ情況下進程檢查點間隔IN的完成時間差率D.如圖4所示，在移動主機遷移率.ρ較低的情況下，各檢查點遷移策略的性能沒有大的差別.當移動主機遷移率ρ較高時，懶惰遷移策略具有相對較好的性能.折衷遷移策略總能得到相對懶惰與急切之間折衷的性能.此結果也正好符合了3種檢查點遷移策略的實際情況，驗證了本文性能評價方法的有效性.

圖4 不同主機遷移率下3種檢查點遷移策略對比

通過大量類似的仿真評估，在消息率λ較高、移動主機遷移率ρ較高和進程故障率γ較低的情況下，懶惰遷移處理策略會具有相對較好的性能;而在消息率λ較低、移動主機遷移率ρ較高、無線帶寬較窄和進程故障率γ較高的情況下，折衷遷移處理策略則會具有相對較好的性能.

與具體的移動計算系統(tǒng)消息日志檢查點卷回恢復策略相結合，利用所提出的檢查點遷移策略性能評價方法，本文得到了不同移動計算環(huán)境下相對適用的檢查點遷移處理策略，如表1所示.

表1 適用檢查點遷移處理策略表

5 結論

1)結合具體的日志檢查點卷回恢復策略和系統(tǒng)參數(shù)，對各檢查點遷移處理方式對系統(tǒng)檢查點容錯性能的影響進行了評估，結果符合3種檢查點遷移策略的實際情況，從而驗證了該模型的有效性.

2)利用該性能評價模型得出了不同移動計算環(huán)境下相對適用的檢查點遷移處理策略.

［1］楊金民，張大方，黎文偉.一種可靠高效的回卷恢復實現(xiàn)方法［J］.電子學報， 2006，34(2):237－240.

［2］汪東升，邵明瓏.具有O(n)消息復雜度的協(xié)調(diào)檢查點設置算法［J］.軟件學報， 2003，14(1)43－48.

［3］李慶華，蔣廷耀，張紅君.一種面向移動計算的低代價透明檢查點恢復協(xié)議［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—)，男，教授.

(編輯 張 紅)