采用增量檢查點(diǎn)技術(shù)改進(jìn) Condor檢查點(diǎn)機(jī)制的研究

張光輝,王麗娟,陳 姍

(河南農(nóng)業(yè)大學(xué)信息與管理科學(xué)學(xué)院,河南鄭州 450002)

檢查點(diǎn)技術(shù)是實(shí)現(xiàn)分布∕并行系統(tǒng)容錯(cuò)的重要手段,同時(shí)也是實(shí)現(xiàn)進(jìn)程遷移、作業(yè)切換和系統(tǒng)模擬的基礎(chǔ)[1～3].運(yùn)用檢查點(diǎn)技術(shù),在程序正常運(yùn)行時(shí)將程序的狀態(tài)信息寫(xiě)入到持久性存儲(chǔ)設(shè)備上.當(dāng)程序因?yàn)楫惓６罎⑿枰匦聠?dòng)時(shí),就可以從最近保存的檢查點(diǎn)文件中恢復(fù)到程序保存檢查點(diǎn)時(shí)程序運(yùn)行的狀態(tài),這樣,就可以接著以前的進(jìn)度繼續(xù)執(zhí)行,從而降低了程序崩潰所帶來(lái)的損失[4,5].設(shè)置檢查點(diǎn)的開(kāi)銷是影響系統(tǒng)性能的一個(gè)主要因素.如果一個(gè)應(yīng)用程序在運(yùn)行的整個(gè)周期內(nèi)每隔一段時(shí)間就進(jìn)行一次檢查點(diǎn)操作,但這個(gè)程序直至運(yùn)行完成也沒(méi)有出現(xiàn)故障(沒(méi)有使用檢查點(diǎn)進(jìn)行重啟),這種情況下檢查點(diǎn)操作就是完全多余的,不但加長(zhǎng)了程序運(yùn)行的時(shí)間,而且浪費(fèi)了系統(tǒng)的計(jì)算資源.因此,設(shè)法降低檢查點(diǎn)操作的開(kāi)銷,對(duì)于充分利用整個(gè)系統(tǒng)的計(jì)算資源是很有必要的.文章首先介紹了機(jī)群作業(yè)系統(tǒng) Condor,然后分析了Condor系統(tǒng)里面檢查點(diǎn)機(jī)制的實(shí)現(xiàn)原理.在此基礎(chǔ)上,針對(duì)此系統(tǒng)里面檢查點(diǎn)機(jī)制的不足,提出了改進(jìn)方案.

1 Condor的工作原理

Condor是由美國(guó)威斯康星大學(xué)研究開(kāi)發(fā)的一個(gè)全新的計(jì)算密集型作業(yè)的資源管理系統(tǒng).該系統(tǒng)能有效地監(jiān)視網(wǎng)絡(luò)下的資源,并聚集空閑資源形成一個(gè)大吞吐量的計(jì)算環(huán)境[6].Condor系統(tǒng)里面的計(jì)算機(jī)分為 3類,中央管理主機(jī)、提交作業(yè)的主機(jī)和運(yùn)行作業(yè)的主機(jī).

圖1 Condor系統(tǒng)的工作流程Fig.1 Work flow of Condor system

用戶通過(guò)代理(schedd)提交作業(yè).schedd進(jìn)程把提交的作業(yè)在本地作業(yè)隊(duì)列中進(jìn)行維護(hù)管理,然后開(kāi)始尋找滿足作業(yè)要求并且愿意執(zhí)行這個(gè)作業(yè)的計(jì)算資源.schedd進(jìn)程會(huì)把作業(yè)對(duì)所需計(jì)算資源的類型描述發(fā)送給中央管理主機(jī)上運(yùn)行的 collector進(jìn)程,同時(shí),愿意運(yùn)行作業(yè)的主機(jī)會(huì)通過(guò) startd進(jìn)程向 collector發(fā)送自己的機(jī)器環(huán)境描述的信息.運(yùn)行在中央管理主機(jī)上的 negotiator進(jìn)程會(huì)把用戶的需求與系統(tǒng)里面的計(jì)算資源相匹配,一旦發(fā)現(xiàn)匹配的組合,就會(huì)通知雙方.schedd進(jìn)程在找到滿足作業(yè)執(zhí)行要求的計(jì)算資源后,會(huì)主動(dòng)聯(lián)系這個(gè)計(jì)算資源上的 startd進(jìn)程,以確認(rèn)此計(jì)算資源確實(shí)可用.要真正的運(yùn)行用戶提交的作業(yè),雙方都必須產(chǎn)生一個(gè)新的進(jìn)程.在提交作業(yè)的主機(jī)上,schedd進(jìn)程創(chuàng)建 shadow進(jìn)程,在將要運(yùn)行作業(yè)的主機(jī)上,startd進(jìn)程會(huì)創(chuàng)建 starter進(jìn)程.starter進(jìn)程用來(lái)為作業(yè)提供一個(gè)運(yùn)行環(huán)境.shadow進(jìn)程負(fù)責(zé)傳輸starter進(jìn)程所需的作業(yè)信息和所有的數(shù)據(jù)文件,并且為用戶作業(yè)的遠(yuǎn)程系統(tǒng)調(diào)用服務(wù),允許作業(yè)透明的訪問(wèn)位于提交主機(jī)上的數(shù)據(jù)文件.作業(yè)執(zhí)行完或者被放棄執(zhí)行時(shí),starter進(jìn)程取消用戶作業(yè)創(chuàng)建的所有子進(jìn)程,向作業(yè)提交主機(jī)發(fā)送消息,該進(jìn)程退出[6].

2 Condor檢查點(diǎn)機(jī)制

檢查點(diǎn)是一個(gè)用于進(jìn)程卷回恢復(fù)的技術(shù):一個(gè)正在運(yùn)行程序的狀態(tài)被周期性的寫(xiě)回到持久性存儲(chǔ)媒介上,當(dāng)程序因?yàn)楫惓６罎r(shí),程序可以從最近 1次保存的檢查點(diǎn)處重啟.

檢查點(diǎn)機(jī)制使得 Condor系統(tǒng)的調(diào)度模塊可以自由的使用搶占式調(diào)度策略[7,8].如果調(diào)度模塊決定收回已經(jīng)分配給 1個(gè)作業(yè)的計(jì)算資源(例如,計(jì)算機(jī)的主人回來(lái)了,需要使用這臺(tái)計(jì)算機(jī)),它可以對(duì)此作業(yè)進(jìn)行一次保存檢查點(diǎn)操作,然后終止作業(yè)的運(yùn)行,這樣不但沒(méi)有影響到用戶使用自己的計(jì)算機(jī),而且由于我們使用檢查點(diǎn)保存了作業(yè)最后的狀態(tài),這樣,當(dāng)調(diào)度模塊重新為這個(gè)作業(yè)分配 1臺(tái)新的機(jī)器繼續(xù)運(yùn)行時(shí),這個(gè)作業(yè)就可以從最近保存的檢查點(diǎn)文件重啟.

Condor系統(tǒng)是通過(guò)信號(hào)處理模塊來(lái)實(shí)現(xiàn)檢查點(diǎn)機(jī)制的.當(dāng) Condor向正在運(yùn)行的進(jìn)程發(fā)送 1個(gè)進(jìn)行檢查點(diǎn)操作的信號(hào)后,Condor安裝的信號(hào)處理模塊就會(huì)開(kāi)始執(zhí)行,它會(huì)把進(jìn)程的狀態(tài)寫(xiě)到 1個(gè)文件里面或者通過(guò)網(wǎng)絡(luò)寫(xiě)到另外 1臺(tái)計(jì)算機(jī)上.這些狀態(tài)信息包括:

1)進(jìn)程的數(shù)據(jù)段和堆棧段

2)加載的動(dòng)態(tài)可執(zhí)行庫(kù)的信息

3)進(jìn)程打開(kāi)的所有文件的信息,包括文件名、打開(kāi)方式和文件當(dāng)前的位移

4)寄存器里面的數(shù)據(jù)

5)進(jìn)程所設(shè)置的信號(hào)信息

應(yīng)用程序要使用 Condor提供的檢查點(diǎn)機(jī)制,必須首先使用 Condor-compile命令與 Condor系統(tǒng)的庫(kù)文件進(jìn)行鏈接.圖 2給出了一個(gè)與 Condor庫(kù)文件鏈接后的應(yīng)用程序在正常執(zhí)行時(shí)的虛擬地址空間的布局.應(yīng)用程序員寫(xiě)的模塊與 Condor的模塊共同存放在程序的指令段.已經(jīng)初始化的全局?jǐn)?shù)據(jù)、未初始化的全局?jǐn)?shù)據(jù)和使用 sbrk系統(tǒng)調(diào)用動(dòng)態(tài)分配的數(shù)據(jù)存在于程序的數(shù)據(jù)段.堆棧段存放著內(nèi)核為每個(gè)進(jìn)程都會(huì)分配的 1塊數(shù)據(jù)結(jié)構(gòu)和目前因?yàn)楹瘮?shù)調(diào)用而產(chǎn)生的活動(dòng)堆棧.因?yàn)?Condor必須在用戶的代碼執(zhí)行前做一些初始化,所以在活動(dòng)堆棧的最底部是 Condor的 MAIN模塊.MAIN模塊執(zhí)行完初始化工作后,會(huì)調(diào)用用戶程序的入口函數(shù)main[9].

Condor使用 SIGTSTP信號(hào)來(lái)通知應(yīng)用程序進(jìn)行檢查點(diǎn)操作.MAIN模塊里面的初始化代碼會(huì)為此信號(hào)安裝 1個(gè)信號(hào)處理函數(shù).圖 3是應(yīng)用程序進(jìn)行檢查點(diǎn)操作時(shí)地址空間的布局.SIGTSTP信號(hào)處理函數(shù)通過(guò)使用 setjmp將與程序有關(guān)的寄存器狀態(tài)(堆棧指針寄存器 sp、程序計(jì)數(shù)器 pc等)保存在jmp-buf結(jié)構(gòu)中.然后,此函數(shù)會(huì)把上面提到的保存檢查點(diǎn)時(shí)需要保存的所有狀態(tài)信息寫(xiě)到檢查點(diǎn)文件里面.當(dāng) Condor使用檢查點(diǎn)文件重啟程序的時(shí)候,會(huì)恢復(fù)數(shù)據(jù)段、堆棧段、打開(kāi)文件狀態(tài)等狀態(tài)信息,同時(shí)會(huì)使用 longjmp從 jmp-buf結(jié)構(gòu)里面恢復(fù)保存檢查點(diǎn)操作時(shí)寄存器里面的信息,做過(guò)這些操作后,程序就可以從保存檢查點(diǎn)的位置繼續(xù)執(zhí)行.

3 Condor檢查點(diǎn)機(jī)制的不足與改進(jìn)方案

Condor系統(tǒng)中實(shí)現(xiàn)的檢查點(diǎn)機(jī)制,對(duì)進(jìn)程做的每 1次檢查點(diǎn)操作,都會(huì)把上面提到的進(jìn)程的所有狀態(tài)信息保存下來(lái).這樣做使得檢查點(diǎn)操作的時(shí)間開(kāi)銷太大,影響系統(tǒng)整體的效率[10～12].當(dāng)執(zhí)行檢查點(diǎn)操作的時(shí)候,只有相對(duì)于上 1次檢查點(diǎn)操作之后改變了的部分才需要保存,而相對(duì)于上 1次檢查點(diǎn)操作后不變的部分可以從上 1次保存的檢查點(diǎn)中恢復(fù).這就是增量檢查點(diǎn)技術(shù)[1],使用此技術(shù)可以減少每次保存的檢查點(diǎn)文件的大小,進(jìn)而降低進(jìn)行檢查點(diǎn)操作時(shí)的額外開(kāi)銷.

在 Condor的實(shí)現(xiàn)中,因?yàn)槊看螜z查點(diǎn)操作得到的檢查點(diǎn)文件都包含進(jìn)程重啟的時(shí)候所需的全部信息,因此,只需要保存 1個(gè)最新的檢查點(diǎn)文件(每次得到 1個(gè)檢查點(diǎn)后,舊的檢查點(diǎn)文件就可以刪除掉).相反,當(dāng)使用增量檢查點(diǎn)技術(shù)來(lái)進(jìn)行檢查點(diǎn)操作時(shí),舊的檢查點(diǎn)文件是不可以刪除的,因?yàn)檫M(jìn)程的狀態(tài)信息分布在多個(gè)檢查點(diǎn)文件中[1].針對(duì)于 Condor系統(tǒng)檢查點(diǎn)機(jī)制存在的不足,使用增量檢查點(diǎn)技術(shù)對(duì)其進(jìn)行優(yōu)化,提出下面的具體改進(jìn)方案:使用頁(yè)面保護(hù)技術(shù)確定哪些頁(yè)面需要保存.也就是說(shuō),在 1次檢查點(diǎn)操作完成之后,使用mprotect()系統(tǒng)調(diào)用來(lái)將進(jìn)程的頁(yè)面設(shè)置為只讀.這樣,當(dāng)進(jìn)程對(duì)這些設(shè)置為只讀的頁(yè)面進(jìn)行寫(xiě)操作時(shí),就會(huì)觸發(fā)一個(gè) SEGV信號(hào).為這個(gè)信號(hào)安裝信號(hào)處理函數(shù),這個(gè)函數(shù)的功能是將這個(gè)只讀頁(yè)面改為可以讀寫(xiě)的頁(yè)面,并且標(biāo)記此頁(yè)面.這樣,當(dāng)下 1次進(jìn)行檢查點(diǎn)操作的時(shí)候,只有這些被標(biāo)記的頁(yè)面需要寫(xiě)到檢查點(diǎn)文件中[13,14].

通過(guò) 1個(gè)具體實(shí)例,來(lái)比較一下使用上面的優(yōu)化方案后帶來(lái)的效率上的改進(jìn).考慮 1個(gè)矩陣運(yùn)算里面經(jīng)常會(huì)遇到的矩陣相乘的例子.例如,有 2個(gè)1 536×1 536的矩陣 A和B進(jìn)行相乘運(yùn)算,結(jié)果是一個(gè) 1 536×1 536的矩陣 C.在這個(gè)程序中數(shù)據(jù)段的空間主要是 A,B和 C這 3個(gè)矩陣所占用的空間.因此,忽略其它變量所占用的空間,并且分別在矩陣 C的第 256,512,768,1 024和 1 280列的值得到后進(jìn)行保存檢查點(diǎn)操作.由于在整個(gè)運(yùn)算過(guò)程中,矩陣 A和 B的值一直不變,并且矩陣 C的列在求出后也不會(huì)在變化,所以得到表 1所示的數(shù)據(jù)(表中檢查點(diǎn)文件大小的單位是以 1列作為標(biāo)準(zhǔn)單位,其中 1列所占用的空間是 1 536個(gè)矩陣元素所占用的空間;檢查點(diǎn)操作時(shí)刻是結(jié)果矩陣 C的第 n列被計(jì)算得到的時(shí)刻).

表1 檢查點(diǎn)文件大小對(duì)比Table1 Comparison of checkpoint file size

從表 1的數(shù)據(jù)可以發(fā)現(xiàn),當(dāng)?shù)?1次保存檢查點(diǎn)的時(shí)候,改進(jìn)前與改進(jìn)后的檢查點(diǎn)大小一樣,都是4 068.隨后,當(dāng)分別在 512,768,1 024和1 280列的值計(jì)算得到后保存檢查點(diǎn)的時(shí)候,使用改進(jìn)后的檢查點(diǎn)策略只需要保存與上 1次保存時(shí)發(fā)生了變化的數(shù)據(jù),也就是說(shuō)改進(jìn)后每次只需要保存的數(shù)據(jù)大小為 256.而沒(méi)有采取改進(jìn)方案時(shí),需要保存的數(shù)據(jù)大小仍然是 4 608.由此,可以看到,使用改進(jìn)后的檢查點(diǎn)策略,可以很大程度上提高檢查點(diǎn)操作的效率.

圖4 檢查點(diǎn)文件大小的比較Fig.4 Comparison of checkpoint file size

5 結(jié)論

檢查點(diǎn)技術(shù)是容錯(cuò)計(jì)算機(jī)系統(tǒng)進(jìn)行故障恢復(fù)的重要手段.本文在對(duì) Condor檢查點(diǎn)原理進(jìn)行詳細(xì)分析的基礎(chǔ)上,針對(duì)其在進(jìn)行檢查點(diǎn)操作時(shí)存在的不足,提出了使用增量檢查點(diǎn)技術(shù)對(duì)其進(jìn)行優(yōu)化的改進(jìn)方案,通過(guò)矩陣運(yùn)算的實(shí)例可以證明,使用此改進(jìn)方案來(lái)優(yōu)化 Condor系統(tǒng)的檢查點(diǎn)機(jī)制,可大大提高系統(tǒng)檢查點(diǎn)操作的效率.

[1] 王春露,汪東升.Unix進(jìn)程檢查點(diǎn)設(shè)置關(guān)鍵技術(shù)[J].計(jì)算機(jī)工程與應(yīng)用,2002,38(1):90-94.

[2] CAO G H,MUKESH S.Checkpointing with mutable checkpoints[J].Theoretical Computer Science,2003,290:1127-1148.

[3] 門(mén)朝光,焦 亮,李 香,等.基于 Linux內(nèi)核的進(jìn)程檢查點(diǎn)系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)科學(xué),2009,36(4):192-195.

[4] FOSIER I,KESSELMAN C.網(wǎng)格計(jì)算[M].北京:機(jī)械工業(yè)出版社,2005.

[5] 楊 超,張偉哲,張宏莉.基于檢查點(diǎn)算法的網(wǎng)格計(jì)算容錯(cuò)機(jī)制研究[J].微電子學(xué)與計(jì)算機(jī),2006,23(9):82-84.

[6] 余麗瓊,周振宇,郭紹忠,等.Condor系統(tǒng)在大吞吐量計(jì)算中的應(yīng)用[J].信息工程大學(xué)學(xué)報(bào),2004,5(1):77-79.

[7] 田 甜,祝永志.一種改進(jìn)的同步檢查點(diǎn)設(shè)置算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2009,19(8):124-126.

[8] 周恩強(qiáng),盧宇彤,沈志宇.一個(gè)適合大規(guī)模集群并行計(jì)算的檢查點(diǎn)系統(tǒng)[J].計(jì)算機(jī)研究與發(fā)展,2005,42(6):987-992.

[9] RONALD J.Leach,Setting checkpoints in legacy code to improve fault-tolerance[J].The Journal of Systems and Software,2008,81:920-928

[10]周小成,孫凝暉,霍志剛,等.一種降低并行程序檢查點(diǎn)開(kāi)銷的方法[J].計(jì)算機(jī)工程,2007,33(12):84-86.

[11]張至柔.網(wǎng)格計(jì)算服務(wù)系統(tǒng)檢查點(diǎn)算法研究[J].計(jì)算機(jī)工程與設(shè)計(jì),2008,29(14):3596-3599.

[12]HIMADRI S P,AROBINDA G.Finding a suitable checkpoint and recovery protocol for a distributed application[J].Journal of Parallel and Distributed Computing,2006,66:732-749.

[13]隋翠翠,晏海華.一種基于高性能集群計(jì)算系統(tǒng)的檢查點(diǎn)策略[J].微電子學(xué)與計(jì)算機(jī),2008,25(10):162-165.

[14]魯曉佩,廖湘科,盧宇彤.面向恢復(fù)的集群計(jì)算技術(shù)[J].計(jì)算機(jī)工程,2009,35(14):52-57.