移動(dòng)計(jì)算系統(tǒng)檢查點(diǎn)遷移策略的性能評(píng)價(jià)

門(mén)朝光，徐振朋，李 香

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

移動(dòng)計(jì)算系統(tǒng)檢查點(diǎn)遷移策略的性能評(píng)價(jià)

門(mén)朝光，徐振朋，李 香

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

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

移動(dòng)計(jì)算;容錯(cuò);檢查點(diǎn);握手遷移

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

1 移動(dòng)計(jì)算系統(tǒng)模型

移動(dòng)計(jì)算系統(tǒng)的系統(tǒng)模型可表示為MCS=〈N，C〉，是由節(jié)點(diǎn)集合N和信道集合C組成，如圖1所示.節(jié)點(diǎn)集合N包括兩種主機(jī)(N=M∪S)，移動(dòng)主機(jī)(MH)集合 M={MH1，MH2，…，MHn}和移動(dòng)支持站(MSS)集合 S={MSS1，MSS2，…，MSSm}.移動(dòng)主機(jī)具有較小的處理能力和存儲(chǔ)空間，移動(dòng)支持站是靜態(tài)節(jié)點(diǎn)，擁有較高的處理能力和可靠的存儲(chǔ)器.通信信道C由兩部分組成(C=W∪W′)，移動(dòng)支持站間高速的有線通信信道W(W=S×S)和移動(dòng)支持站與移動(dòng)主機(jī)間相對(duì)低速的無(wú)線通信信道W′(W′=S×M).MSSi為第i個(gè)移動(dòng)支持站，MHi為第i個(gè)移動(dòng)主機(jī).地理上，由一MSSi覆蓋的一個(gè)通信區(qū)域稱(chēng)作一個(gè)組(CELL)，在組 CELLi中的移動(dòng)支持站MSSi被本組MHs稱(chēng)為本地移動(dòng)支持站.每個(gè)移動(dòng)支持站(MSSi)上存在集合CLi={MHj|MHj∈MSSi，0＜j＜n+1}記錄本組中的移動(dòng)主機(jī)，子集Active－MH－Listi記錄活動(dòng)的移動(dòng)主機(jī)，子集Disconnected－MH－Listi記錄休眠的移動(dòng)主機(jī).一個(gè)移動(dòng)主機(jī)在某一時(shí)刻只屬于一個(gè)組，即滿(mǎn)足條件 MHj∈ CLi? MHj? CLk，?k≠ i.任一 MHj可以直接通過(guò)無(wú)線信道〈MSSi，MHj〉∈W′連接到服務(wù)于該組的本地MSSi上，并且通過(guò)本地的MSSi與其它的MH或MSS通信.

圖1 移動(dòng)計(jì)算系統(tǒng)模型

移動(dòng)計(jì)算系統(tǒng)包含N個(gè)獨(dú)立計(jì)算進(jìn)程P1，P2，…，PN.每個(gè)進(jìn)程周期性地存儲(chǔ)其局部狀態(tài)到穩(wěn)定存儲(chǔ)器中以產(chǎn)生局部檢查點(diǎn).每個(gè)檢查點(diǎn)被分配了唯一的檢查點(diǎn)序號(hào)CSN(checkpoint sequence number).進(jìn)程Pk的第i(i≥0)個(gè)檢查點(diǎn)被分配了序號(hào) i，表示為 Ck，i.任何存在于 Ck，i－1和 Ck，i之間的事件 ek，x被稱(chēng)作“ek，x屬于 Ck，i”，表示為 ek，x∈ Ck，i.故障為“fail-stop”形式，一旦進(jìn)程失效，該進(jìn)程將立即停止執(zhí)行，不會(huì)產(chǎn)生任何惡意的行為.當(dāng)進(jìn)程發(fā)生故障時(shí)，存儲(chǔ)在MH或MSS內(nèi)存中的內(nèi)容可能會(huì)被破壞或丟失，而可靠存儲(chǔ)器中的內(nèi)容可以用來(lái)恢復(fù)主機(jī)進(jìn)程.網(wǎng)絡(luò)連接支持雙向的FIFO通信，且假定消息的傳輸是可靠的.網(wǎng)絡(luò)中消息的傳輸延遲在一定時(shí)間范圍內(nèi)是任意的.

2 移動(dòng)計(jì)算系統(tǒng)檢查點(diǎn)容錯(cuò)策略

移動(dòng)計(jì)算檢查點(diǎn)卷回恢復(fù)策略由3個(gè)基本部分構(gòu)成:進(jìn)程狀態(tài)檢查點(diǎn)創(chuàng)建、移動(dòng)主機(jī)遷移處理與進(jìn)程卷回恢復(fù)［10－12］.

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

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

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

2.2 檢查點(diǎn)遷移處理策略

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

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

2.3 進(jìn)程卷回恢復(fù)方式

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

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

3 性能評(píng)價(jià)

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

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

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

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

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

圖2 檢查點(diǎn)間隔的馬爾科夫鏈表示形式

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

3.2 性能評(píng)價(jià)模型

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

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

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

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

4 實(shí)例與仿真

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

結(jié)合移動(dòng)計(jì)算系統(tǒng)的日志檢查點(diǎn)卷回恢復(fù)策略，圖3為不同檢查點(diǎn)遷移策略和進(jìn)程故障率情況下IN完成時(shí)間差率D的對(duì)比情況.

圖3 不同故障率下3種檢查點(diǎn)遷移策略對(duì)比

如圖3所示，在進(jìn)程故障率γ較低的情況下，懶惰遷移策略具有相對(duì)較好的性能，這是由于懶惰遷移策略在遷移處理時(shí)傳輸?shù)幕謴?fù)信息量較小.當(dāng)進(jìn)程故障率γ較高時(shí)，急切遷移策略則具有相對(duì)較好的性能，這是由于急切遷移策略能更好的保證故障進(jìn)程恢復(fù)速度.折衷遷移策略總能得到相對(duì)折衷的性能.此結(jié)果正好符合了3種檢查點(diǎn)遷移策略的實(shí)際情況，驗(yàn)證了本文性能評(píng)價(jià)方法的有效性.

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

圖4 不同主機(jī)遷移率下3種檢查點(diǎn)遷移策略對(duì)比

通過(guò)大量類(lèi)似的仿真評(píng)估，在消息率λ較高、移動(dòng)主機(jī)遷移率ρ較高和進(jìn)程故障率γ較低的情況下，懶惰遷移處理策略會(huì)具有相對(duì)較好的性能;而在消息率λ較低、移動(dòng)主機(jī)遷移率ρ較高、無(wú)線帶寬較窄和進(jìn)程故障率γ較高的情況下，折衷遷移處理策略則會(huì)具有相對(duì)較好的性能.

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

表1 適用檢查點(diǎn)遷移處理策略表

5 結(jié)論

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

2)利用該性能評(píng)價(jià)模型得出了不同移動(dòng)計(jì)算環(huán)境下相對(duì)適用的檢查點(diǎn)遷移處理策略.

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

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

［3］李慶華，蔣廷耀，張紅君.一種面向移動(dòng)計(jì)算的低代價(jià)透明檢查點(diǎn)恢復(fù)協(xié)議［J］.軟件學(xué)報(bào)， 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.

國(guó)家自然科學(xué)基金資助項(xiàng)目(60873138).

門(mén)朝光(1963—)，男，教授.

(編輯 張 紅)