1、第36卷 第4期計(jì)算機(jī)科學(xué)Vo l. 36No. 4基于Linux 內(nèi)核的進(jìn)程檢查點(diǎn)系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)門(mén)朝光 焦 亮 李 香 徐振朋(哈爾濱工程大學(xué)計(jì)算機(jī)學(xué)院高可信計(jì)算技術(shù)研究中心 哈爾濱150001摘 要 作為一種流行的軟件容錯(cuò)機(jī)制, 檢查點(diǎn)與恢復(fù)技術(shù)的實(shí)現(xiàn)模式有兩種:用戶級(jí)和系統(tǒng)級(jí)。首先闡述了兩者的區(qū)別, 然后根據(jù)L inux 可加載內(nèi)核模塊機(jī)制提出了一種基于L inux 內(nèi)核的進(jìn)程檢查點(diǎn)與恢復(fù)實(shí)現(xiàn)方法。利用L inux 內(nèi)核線程實(shí)現(xiàn)了檢查點(diǎn)與恢復(fù)內(nèi)核模塊, 并基于此內(nèi)核模塊在用戶層構(gòu)造了一檢查點(diǎn)函數(shù)庫(kù), 為用戶提供了相應(yīng)接口。用戶通過(guò)組合使用這些接口可以高效地實(shí)現(xiàn)具體檢查點(diǎn)與恢復(fù)算法。關(guān)鍵詞

2、 檢查點(diǎn)與恢復(fù), 用戶級(jí), 系統(tǒng)級(jí), 內(nèi)核模塊, 內(nèi)核線程中圖法分類號(hào) T P302. 8 文獻(xiàn)標(biāo)識(shí)碼 ADesign and Implementation of Process Checkpointing System Based on Linux KernelM EN Chao guang JIA O L iang L I X iang XU Zhen peng(R&D Center of H igh dependab ility Com puting T echnology, H ar bin Engineering University, H arb in 150001, Ch

3、 inaAbstract As a popular softw are fault to lerant mechanism, checkpo int and r eco ver y technique can be implemented by two modes:user level and system lev el. Fir st, the differences betw een the tw o mo des wer e discussed. T hen accor ding to the L inux L K M (L oadable K ernel M o dule mechan

4、ism, a method w as pr oposed to desig n a pr ocess checkpoint and r e co very system based o n the L inux ker nel. Checkpoint and recov ery kernel module w as implemented using the L inux ker nel t hr ead. Based o n this kernel module, a checkpo int libr ary was constructed in the user level to prov

5、 ide co rr esponding interfaces for users. By using some select ed int erfaces, the par ticular checkpoint and r eco ver y alg or ithm can be imple mented effectiv ely.Keywords Checkpoint and r eco ver y, U ser lev el, Sy st em level, K ernel mo dule, Ker nel thread為了保證大型計(jì)算程序高可靠地運(yùn)行, 提高計(jì)算機(jī)資源的利用率, 容錯(cuò)技

6、術(shù)應(yīng)運(yùn)而生。檢查點(diǎn)機(jī)制是一種典型的軟件容錯(cuò)技術(shù), 一方面它具有備份進(jìn)程狀態(tài)、生成檢查點(diǎn)文件的功能; 另一方面當(dāng)操作系統(tǒng)出現(xiàn)故障或因外部差錯(cuò)而導(dǎo)致某些進(jìn)程終止時(shí), 通過(guò)加載檢查點(diǎn)文件, 可以將進(jìn)程卷回到最近的檢查點(diǎn)處以實(shí)現(xiàn)進(jìn)程狀態(tài)的恢復(fù)1 5。所以, 一個(gè)基本的檢查點(diǎn)系統(tǒng)應(yīng)該包括進(jìn)程狀態(tài)保存和進(jìn)程狀態(tài)恢復(fù)功能。檢查點(diǎn)系統(tǒng)有兩種設(shè)計(jì)模式:用戶級(jí)和系統(tǒng)級(jí)6,7。基于用戶級(jí)模式實(shí)現(xiàn)的系統(tǒng)通常具有較好的可移植性, 但是缺乏透明性、通用性, 用戶需要根據(jù)不同的平臺(tái)有針對(duì)性地修改應(yīng)用程序源代碼, 然后重新編譯。如果檢查點(diǎn)函數(shù)以庫(kù)函數(shù)的形式提供, 還需要重新鏈接。修改源代碼容易出錯(cuò)而且很多商業(yè)代碼只擁有二進(jìn)制

7、可執(zhí)行文件, 對(duì)它們重新修改、編譯是不可能的。此外, 根據(jù)U nix/L inux 進(jìn)程概念可知, 用戶進(jìn)程只能通過(guò)系統(tǒng)調(diào)用的方式來(lái)間接訪問(wèn)操作系統(tǒng)內(nèi)核維護(hù)的數(shù)據(jù), 但是無(wú)法訪問(wèn)某些與進(jìn)程狀態(tài)有關(guān)的內(nèi)核數(shù)據(jù)結(jié)構(gòu)。因此用戶級(jí)的檢查點(diǎn)不可能完全地記錄和恢復(fù)一個(gè)進(jìn)程的狀態(tài), 這樣當(dāng)系統(tǒng)出現(xiàn)故障或進(jìn)程出錯(cuò)需要卷回恢復(fù)時(shí)就可能到稿日期:2008 11 20 本文受國(guó)家自然科學(xué)基金(60873138 資助。門(mén)朝光(1963- , 男, 博士, 教授, 博士生導(dǎo)師, CCF 高級(jí)會(huì)員, 主要研究方向?yàn)榉植际较到y(tǒng)與并行系統(tǒng)、可信性計(jì)算、移動(dòng)計(jì)算技術(shù), E mail:men chaoguanghrb eu. e

8、du. cn; 焦 亮(1982- , 男, 碩士研究生, 研究方向?yàn)椴⑿邢到y(tǒng)容錯(cuò)技術(shù); 李 香(1975- , 女, 博士, 主要研究方向?yàn)榭尚庞?jì)算; 徐振朋(1983- , 男, 博士研究生, 研究方向?yàn)榭尚庞?jì)算。會(huì)導(dǎo)致進(jìn)程無(wú)法恢復(fù)。具有代表性的用戶級(jí)檢查點(diǎn)系統(tǒng)有Conder 8和L ibckpt 9。基于系統(tǒng)級(jí)模式實(shí)現(xiàn)的檢查點(diǎn)系統(tǒng)具有全透明性, 檢查點(diǎn)機(jī)制獨(dú)立于應(yīng)用程序10, 11。用戶不必修改程序源代碼, 應(yīng)用程序不必和檢查點(diǎn)函數(shù)庫(kù)一起編譯, 這就減少了程序出錯(cuò)的概率。此外, 在操作系統(tǒng)內(nèi)核空間中, 與進(jìn)程狀態(tài)相關(guān)的任何數(shù)據(jù)結(jié)構(gòu)都是可訪問(wèn)的。這些數(shù)據(jù)結(jié)構(gòu)包括寄存器、內(nèi)存區(qū)、文件描述符、

9、信號(hào)狀態(tài)等等。因此可以實(shí)現(xiàn)對(duì)用戶進(jìn)程狀態(tài)的完全保存。具有代表性的系統(tǒng)級(jí)檢查點(diǎn)系統(tǒng)有BL CR 12和CRA K 13。在分析參考了以上幾種系統(tǒng)的實(shí)現(xiàn)后, 本文根據(jù)L inux 可加載內(nèi)核模塊(L KM 機(jī)制提出了一種基于L inux 內(nèi)核的進(jìn)程檢查點(diǎn)技術(shù)實(shí)現(xiàn)方法。在內(nèi)核層利用L inux 線程實(shí)現(xiàn)一個(gè)可動(dòng)態(tài)加載的檢查點(diǎn)與恢復(fù)模塊, 此模塊作為內(nèi)核線程來(lái)運(yùn)行, 實(shí)現(xiàn)基本的檢查點(diǎn)與恢復(fù)功能。在用戶層基于該內(nèi)核模塊構(gòu)造了一個(gè)檢查點(diǎn)函數(shù)庫(kù), 提供給用戶直觀便利和豐富的檢查點(diǎn)接口, 便于用戶通過(guò)組合使用這些接口來(lái)實(shí)現(xiàn)具體的檢查點(diǎn)與恢復(fù)算法。 1 系統(tǒng)設(shè)計(jì)1. 1 基本設(shè)計(jì)思路此系統(tǒng)的核心部分是位于L i

10、nux 內(nèi)核層的可動(dòng)態(tài)加載和移除的內(nèi)核模塊。利用此模塊, 我們不必對(duì)L inux 內(nèi)核源代碼進(jìn)行修改, 克服了修改內(nèi)核源代碼所帶來(lái)的調(diào)試、編譯以及維護(hù)困難。此模塊加載到內(nèi)核以后, 便與內(nèi)核一起以相同的優(yōu)先級(jí)運(yùn)行, 并與內(nèi)核協(xié)作完成進(jìn)程檢查點(diǎn)設(shè)置和卷回恢復(fù)功能。此內(nèi)核模塊可設(shè)置的檢查點(diǎn)包括進(jìn)程基本狀態(tài)信息檢查點(diǎn)、內(nèi)存檢查點(diǎn)和文件檢查點(diǎn)。上述的L inux 內(nèi)核模塊實(shí)現(xiàn)了系統(tǒng)的基本功能部分, 僅僅利用此模塊就可以對(duì)用戶進(jìn)程進(jìn)行檢查點(diǎn)設(shè)置和恢復(fù)操作。為了使系統(tǒng)具有靈活性和良好的可擴(kuò)充性, 我們?cè)谟脩魧訕?gòu)造檢查點(diǎn)函數(shù)庫(kù)。此函數(shù)庫(kù)是基于內(nèi)核模塊實(shí)現(xiàn)的, 即通過(guò)對(duì)內(nèi)核模塊的函數(shù)調(diào)用來(lái)構(gòu)造庫(kù)函數(shù), 目的是豐

11、富和擴(kuò)充內(nèi)核模塊功能, 給用戶提供直觀便利和豐富的檢查點(diǎn)接口, 使用戶能夠通過(guò)組合使用這些接口來(lái)實(shí)現(xiàn)具體的檢查點(diǎn)與恢復(fù)算法, 進(jìn)行算法性能評(píng)估, 從而選擇合適的策略來(lái)降低檢查點(diǎn)開(kāi)銷、優(yōu)化檢查點(diǎn)功能。如果現(xiàn)有的接口不能滿足用戶需求, 我們還可以及時(shí)對(duì)庫(kù)函數(shù)進(jìn)行擴(kuò)充來(lái)滿足用戶的需要。通過(guò)L inux 內(nèi)核中的pr oc 文件系統(tǒng)、內(nèi)核模塊與用戶進(jìn)程進(jìn)行信息交互。pr oc 文件系統(tǒng)具有靈活、方便的訪問(wèn)接口:以普通的文件讀寫(xiě)方式即可訪問(wèn)到任何一個(gè)權(quán)限許可范圍內(nèi)的進(jìn)程上下文信息。在proc 文件系統(tǒng)中, 每個(gè)進(jìn)程都擁有一個(gè)目錄, 該目錄以進(jìn)程標(biāo)識(shí)符PID 命名, 目錄下有操作系統(tǒng)內(nèi)核為本進(jìn)程維護(hù)的許多

12、狀態(tài)信息, 如進(jìn)程內(nèi)存使用狀態(tài)、內(nèi)存內(nèi)容、虛存的邏輯段信息、打開(kāi)的文件、命令行參數(shù)、進(jìn)程環(huán)境信息等。pr oc 文件系統(tǒng)中不同的文件包含有不同的內(nèi)核信息, 比較重要的有:記錄cpu 信息的cpuinfo 文件; 記錄內(nèi)核鎖信息的lo cks 文件; 記錄內(nèi)存信息的meminfo 文件; 全面統(tǒng)計(jì)狀態(tài)信息的stat 文件; 記錄系統(tǒng)識(shí)別的分區(qū)表信息的parti t ions 文件, 等等。內(nèi)核模塊通過(guò)對(duì)pr oc 文件系統(tǒng)中與用戶進(jìn)程相關(guān)的文件進(jìn)行操作可以記錄用戶進(jìn)程的狀態(tài)信息。1. 2 系統(tǒng)原型圖及系統(tǒng)工作原理根據(jù)以上的設(shè)計(jì)思路, 我們構(gòu)造出了基于L inux 內(nèi)核級(jí)的進(jìn)程檢查點(diǎn)系統(tǒng)結(jié)構(gòu)原型,

13、 如圖1所示。塊還提供一個(gè)簡(jiǎn)單的接口供用戶使用, 用戶可動(dòng)態(tài)地對(duì)進(jìn)程設(shè)置檢查點(diǎn)或者重啟進(jìn)程。根據(jù)圖1所示, 經(jīng)過(guò)步驟 ! , 可以實(shí)現(xiàn)基本的檢查點(diǎn)功能。用戶程序運(yùn)行時(shí), 產(chǎn)生一個(gè)進(jìn)程標(biāo)識(shí)符P ID, 相應(yīng)地在pr oc 文件系統(tǒng)中產(chǎn)生一個(gè)以該進(jìn)程號(hào)命名的文件目錄, 該目錄下包含進(jìn)程的各種信息, 如進(jìn)程的當(dāng)前工作目錄、進(jìn)程定義的環(huán)境變量、進(jìn)程打開(kāi)的文件描述符、進(jìn)程的地址空間映射文件等, 檢查點(diǎn)與恢復(fù)內(nèi)核模塊可以通過(guò)讀取、匯總這些信息來(lái)保存進(jìn)程狀態(tài), 生成檢查點(diǎn)文件。經(jīng)過(guò)步驟 ! , 可實(shí)現(xiàn)在用戶具體策略支持下的程序檢查點(diǎn)與恢復(fù)功能。這里所說(shuō)的策略通常指用戶新提出的檢查點(diǎn)與恢復(fù)算法, 或是對(duì)現(xiàn)有算

14、法的改進(jìn), 應(yīng)用此檢查點(diǎn)系統(tǒng)平臺(tái)來(lái)實(shí)現(xiàn)并測(cè)試算法性能。用戶可以組合使用檢查點(diǎn)庫(kù)中的函數(shù)來(lái)實(shí)現(xiàn)算法, 執(zhí)行的時(shí)候?qū)⒂脩舫绦蚣虞d進(jìn)來(lái)與算法結(jié)合在一起運(yùn)行, 然后與步驟 ! 一樣, 內(nèi)核模塊對(duì)用戶進(jìn)程設(shè)置檢查點(diǎn)。無(wú)論是經(jīng)過(guò)步驟 ! 還是經(jīng)過(guò)步驟 ! 來(lái)對(duì)用戶進(jìn)程設(shè)置檢查點(diǎn), 對(duì)于用戶來(lái)說(shuō), 這些操作都是透明的, 既不需要修改用戶程序, 也不需要對(duì)用戶程序和檢查點(diǎn)庫(kù)一起進(jìn)行編譯鏈接。2 系統(tǒng)工作流程2. 1 檢查點(diǎn)設(shè)置過(guò)程內(nèi)核線程進(jìn)行如下操作來(lái)對(duì)一個(gè)用戶進(jìn)程采取檢查點(diǎn):(1 阻塞用戶進(jìn)程運(yùn)行;(2 跳轉(zhuǎn)到用戶進(jìn)程地址空間;(3 保存用戶進(jìn)程映像:保存數(shù)據(jù)段, 包括3個(gè)區(qū)域:初始化數(shù)據(jù)區(qū)、未初始化數(shù)據(jù)區(qū)

15、、堆; 保存相關(guān)內(nèi)存段。(4 保存進(jìn)程用戶棧:保存棧指針; 保存棧空間。(5 保存與進(jìn)程上下文切換有關(guān)的項(xiàng)(包括程序計(jì)數(shù)器P C 、處理機(jī)狀態(tài)字寄存器PSW 等 ;(6 保存用戶進(jìn)程打開(kāi)的文件描述符;(7 保存信號(hào)狀態(tài)(包括即將被用戶進(jìn)程接收的信號(hào) 和由用戶進(jìn)程定義的信號(hào)處理函數(shù);(8 啟動(dòng)用戶進(jìn)程運(yùn)行。在用戶進(jìn)程映像的保存中, 進(jìn)程正文段(即代碼段 通常不需要保存, 程序啟動(dòng)時(shí)裝入程序會(huì)對(duì)它進(jìn)行恢復(fù)。正文大小一般是不變的, 通常在地址空間的低端。創(chuàng)建靜態(tài)鏈接的L inux 進(jìn)程時(shí), 操作系統(tǒng)將整個(gè)正文段裝入虛地址空間。通常是從地址0開(kāi)始的, L inux 要求正文段必須以#只讀方式裝入, 因

16、此在運(yùn)行過(guò)程中, 正文段不會(huì)做任何修改。此外, 如果用戶進(jìn)程運(yùn)行結(jié)束或者通過(guò)pr oc 文件系統(tǒng)接圖1 檢查點(diǎn)系統(tǒng)結(jié)構(gòu)圖收到適當(dāng)?shù)拿? 內(nèi)核線程停止監(jiān)控用戶進(jìn)程。2. 2 恢復(fù)、重啟用戶進(jìn)程內(nèi)核線程進(jìn)行以下操作來(lái)對(duì)用戶進(jìn)程進(jìn)行后向卷回恢復(fù):(1 阻塞用戶進(jìn)程運(yùn)行;(2 恢復(fù)進(jìn)程數(shù)據(jù)段(進(jìn)程正文段隨著程序的裝入自動(dòng)恢復(fù) ;(3 恢復(fù)非棧的一般的段;(4 恢復(fù)進(jìn)程用戶棧段;(5 恢復(fù)與進(jìn)程上下文切換有關(guān)的項(xiàng);對(duì)一個(gè)局部節(jié)點(diǎn)上的用戶進(jìn)程設(shè)置檢查點(diǎn)時(shí), 進(jìn)程標(biāo)識(shí)符PID 和進(jìn)程所在節(jié)點(diǎn)的處理器ID 通過(guò)proc 文件系統(tǒng)接口傳遞給內(nèi)核模塊。內(nèi)核線程對(duì)用戶進(jìn)程采取檢查點(diǎn)時(shí), 它根據(jù)PID 找到相應(yīng)的進(jìn)

17、程, 重構(gòu)進(jìn)程上下文:進(jìn)程打開(kāi)了什么文件, 進(jìn)程占有或釋放了多少內(nèi)存區(qū)域等等。由于內(nèi)核線程最初就對(duì)進(jìn)程相關(guān)的地址空間段寫(xiě)保護(hù), 因此當(dāng)應(yīng)用程序試圖向這些頁(yè)面讀寫(xiě)數(shù)據(jù)時(shí), 這些操作就被檢測(cè)到并被記錄下來(lái)作為檢查點(diǎn)文件內(nèi)容的一部分。通過(guò)proc 文件系統(tǒng), 此模(6 根據(jù)信號(hào)信息表恢復(fù)與信號(hào)有關(guān)的信息; (7 恢復(fù)與進(jìn)程相關(guān)的文件信息;(8 重新啟動(dòng)進(jìn)程運(yùn)行。恢復(fù)過(guò)程需要根據(jù)保存的檢查點(diǎn)文件來(lái)進(jìn)行。這個(gè)文件可能包含根據(jù)檢查點(diǎn)算法得到的許多段, 每一部分包含著與進(jìn)程狀態(tài)相關(guān)的信息。例如在增量檢查點(diǎn)中, 第一段是進(jìn)程的初始化狀態(tài), 它是一個(gè)全檢查點(diǎn), 接下來(lái)的段包含從前一個(gè)檢查點(diǎn)處開(kāi)始的增量變化。如果

18、只恢復(fù)第一段則相當(dāng)于從頭開(kāi)始啟動(dòng)進(jìn)程。int p r ocess _r estar t (char *name, p id _t p id :根據(jù)name 所指定的檢查點(diǎn)文件模擬一個(gè)進(jìn)程, 并恢復(fù)其運(yùn)行。(3 增量檢查點(diǎn)函數(shù)int set _ck p t _incremental(p id _t p id :利用頁(yè)面保護(hù)技術(shù)來(lái)識(shí)別哪些頁(yè)面應(yīng)該包括在增量檢查點(diǎn)文件中, 在設(shè)置一個(gè)檢查點(diǎn)之后, 觸發(fā)mp r otect( 系統(tǒng)調(diào)用, 將全部頁(yè)面的數(shù)據(jù)空間設(shè)置為只讀, 當(dāng)對(duì)一個(gè)保護(hù)頁(yè)面進(jìn)行寫(xiě)操作時(shí), 系統(tǒng)就會(huì)捕捉到一個(gè)SEG V 信號(hào), 這時(shí)將此頁(yè)面的讀寫(xiě)保護(hù)設(shè)置為讀 寫(xiě), 并且此頁(yè)面被標(biāo)記為d i

19、r ty , 當(dāng)設(shè)置下一個(gè)檢查點(diǎn)時(shí), 只包含#dir ty 頁(yè)面。(4 檢查點(diǎn)壓縮函數(shù)int ck p t _comp r ess(p id _t p id :采用標(biāo)準(zhǔn)的壓縮算法實(shí)現(xiàn)此函數(shù), 但是只有在壓縮速率大于磁盤(pán)寫(xiě)數(shù)據(jù)速率, 并且檢查點(diǎn)被明顯壓縮時(shí)才能有效降低系統(tǒng)開(kāi)銷。此函數(shù)通常只在并行計(jì)算中用到。(5 進(jìn)程內(nèi)存空間相關(guān)操作函數(shù)int memory _include _by tes(caddr _t addr , unsigned int len :在檢查點(diǎn)中包含起始地址為addr, 長(zhǎng)度為len 的內(nèi)存段。int memory _ex clude _by tes(caddr _t ad

20、dr , unsigned int len :在檢查點(diǎn)中排除起始地址為addr, 長(zhǎng)度為len 的內(nèi)存段。3 主要函數(shù)設(shè)計(jì)3. 1 內(nèi)核模塊主要函數(shù)設(shè)計(jì)(1 進(jìn)程控制函數(shù)stop _p r ocess(p id _t p id :參數(shù)p id 為內(nèi)核線程通過(guò)系統(tǒng)調(diào)用getp id ( 函數(shù)得到的當(dāng)前用戶進(jìn)程標(biāo)識(shí)號(hào), 此函數(shù)功能是阻塞當(dāng)前用戶進(jìn)程的運(yùn)行。unstop _p r oces s(p id _t p id :參數(shù)p id 同上面的p id 值, 此函數(shù)功能是當(dāng)進(jìn)程檢查點(diǎn)設(shè)置完成或進(jìn)程卷回恢復(fù)完成后, 重新啟動(dòng)進(jìn)程。(2 進(jìn)程狀態(tài)信息保存函數(shù)int ck p t _stor e (co

21、nst char *f ilename, p id _t p id , int f lags :參數(shù)f ilename 代表保存檢查點(diǎn)映像文件名, p id 代表用戶進(jìn)程標(biāo)識(shí)號(hào), f lags 的值由兩個(gè)可選項(xiàng)組成:ckp t _code _f ile 和ck p t _s har e _libr ar y 。若選擇前一項(xiàng)則存儲(chǔ)進(jìn)程二進(jìn)制文件中的代碼段部分, 否則不存儲(chǔ), 在一般情況下不選擇此項(xiàng); 若選擇后一項(xiàng)則存儲(chǔ)共享庫(kù), 否則不存儲(chǔ)。(3 進(jìn)程狀態(tài)恢復(fù)函數(shù)int r ollback _restor e(cons t char *f ilename, p id _t p id :參數(shù)f il

22、ename 代表檢查點(diǎn)映像文件名, p id 代表卷回恢復(fù)的用戶進(jìn)程標(biāo)識(shí)號(hào)。(4 進(jìn)程消息記錄函數(shù)int mess age _stor e(int msg _f r om _p id, int ms g _to _p id, char buf SI ZE :參數(shù)ms g _f r om _p id 代表發(fā)送消息的進(jìn)程, msg _to _p id 代表接收消息的進(jìn)程, 字符數(shù)組buf 是存儲(chǔ)消息內(nèi)容的內(nèi)存緩沖區(qū)。(5 進(jìn)程消息恢復(fù)函數(shù)int message _r estor e (s truct M essage*4 系統(tǒng)性能評(píng)價(jià)試驗(yàn)環(huán)境為:A M D A thlo n(tm Dual Co

23、re CPU 4400+, 2. 31G Hz, 1G 內(nèi)存, 120G 硬盤(pán)。應(yīng)用程序采用矩陣冪運(yùn)算, 以在終端輸入命令行的形式設(shè)置檢查點(diǎn)及卷回恢復(fù)。首先我們不使用任何策略, 僅使用內(nèi)核模塊提供的功能對(duì)應(yīng)用進(jìn)程采取檢查點(diǎn)及卷回恢復(fù), 試驗(yàn)數(shù)據(jù)如表1所列。表1 僅用內(nèi)核模塊功能對(duì)進(jìn)程操作矩陣冪運(yùn)算冪數(shù)10002000采取檢查點(diǎn)耗費(fèi)時(shí)間(ms 527. 4542. 1檢查點(diǎn)大小(KB 963996卷回恢復(fù)時(shí)間(ms 95. 296. 3由表1中的數(shù)據(jù)可以看到系統(tǒng)可以完整的保存、恢復(fù)用戶進(jìn)程狀態(tài), 并且操作是全透明的。然后我們?nèi)谌氩呗灾С謥?lái)對(duì)應(yīng)用進(jìn)程采取檢查點(diǎn)及卷回恢復(fù), 采用增量檢查點(diǎn)策略, 對(duì)

24、應(yīng)用進(jìn)程進(jìn)行兩次檢查點(diǎn)操作(CK1和CK 2 , 兩次操作之間的間隔設(shè)為3500ms 。試驗(yàn)數(shù)據(jù)如表2所列。表2 增量檢查點(diǎn)策略支持下的數(shù)據(jù)試驗(yàn)數(shù)據(jù)10002000CK1CK2CK1CK2采取檢查點(diǎn)耗費(fèi)時(shí)間(ms 526. 147. 2540. 745. 2檢查點(diǎn)大小(KB 9606999263卷回恢復(fù)時(shí)間(ms 93. 694. 797. 195. 2mess age, p id _tp id :參數(shù)message 是一個(gè)指向消息結(jié)構(gòu)體的指針變量, p id 是要恢復(fù)進(jìn)程標(biāo)識(shí)符, 程序執(zhí)行時(shí)根據(jù)p id 從消息結(jié)構(gòu)體數(shù)組中找到進(jìn)程相關(guān)的消息進(jìn)行恢復(fù)。3. 2 檢查點(diǎn)庫(kù)主要函數(shù)設(shè)計(jì)檢查點(diǎn)庫(kù)將檢

25、查點(diǎn)與恢復(fù)內(nèi)核模塊所提供的系統(tǒng)服務(wù)結(jié)合起來(lái), 并在此基礎(chǔ)上進(jìn)行豐富、擴(kuò)充而形成用戶能夠直接使用的豐富的檢查點(diǎn)接口, 包括不同層次上對(duì)用戶進(jìn)程資源的狀態(tài)檢查和狀態(tài)恢復(fù)A PI 、性能優(yōu)化和策略支持A PI 以及一些輔助性的A PI 。下面介紹幾個(gè)主要的A PI 函數(shù):(1 用戶進(jìn)程狀態(tài)信息保存接口函數(shù)int p r ocess _ck p t (p id _t p id , char*name, str uct O p tionop tion :參數(shù)p id 是用戶進(jìn)程標(biāo)識(shí)號(hào), name 是保存檢查點(diǎn)文件的文件名, 參數(shù)op tion 是結(jié)構(gòu)體指針變量, 通過(guò)設(shè)置它的成員變量值, 可以根據(jù)不同的

26、算法進(jìn)行不同的檢查點(diǎn)操作。(2 用戶進(jìn)程狀態(tài)恢復(fù)接口函數(shù)由表2中的數(shù)據(jù)可知, 對(duì)進(jìn)程第二次采取檢查點(diǎn)(CK 2 所耗費(fèi)的時(shí)間以及生成的檢查點(diǎn)文件的大小與第一次(CK 1 相比明顯下降, 這也正符合增量檢查點(diǎn)的算法特點(diǎn)。由于系統(tǒng)設(shè)計(jì)遵循機(jī)制與策略分離的思想, 在內(nèi)核層實(shí)(下轉(zhuǎn)第214頁(yè) 3Ridvan S , Kemal T , Novruz A. A new approach on search for similar documents w ith multiple categories u sing fu zzy clus te ring. Ex pert Systems with App

27、lication s, 2008(34 :2545 255445M anber U, S mit M , Gopal B. W ebGlimps e:combinin g brow sing and search ing %Proceedings of the US ENIX 1997. 1997, 1Su n A, Lim E P. Performance measurement framew ork for hiera rchical text class ification. J ou rnal of the American Society for Information Scienc

28、e an d T echnology, 2003, 54(11 :1014 1028圖3 可信排名效果67Yolanda G, Donovan A. T ow ards content trust of w eb res our ces. J ou rnal of w eb sem antics, 2007(11 :337 358Kris tin R E. Behind the W eb site:An in side look at the p rodu c tion of Web based textual government in formation. Governm ent Info

29、rmation Quarterly, 2004(21 :337 358結(jié)束語(yǔ) 本文通過(guò)Web 挖掘的數(shù)據(jù)域的可信評(píng)測(cè), 給出了一個(gè)Web 挖掘可信域評(píng)測(cè)系統(tǒng)原型。利用Web 域?qū)I(yè)分類, 評(píng)測(cè)域的專業(yè)度, 并利用W eb 內(nèi)容可信判定現(xiàn)有的結(jié)果和用戶的主觀評(píng)測(cè)反饋結(jié)果評(píng)測(cè)域的內(nèi)容可信度, 從而達(dá)到評(píng)測(cè)一個(gè)域挖掘的結(jié)果的可信度, 從而獲得Web 挖掘的可信數(shù)據(jù)源, 影響最終結(jié)果, 以求在顯示中將可信結(jié)果排列在前。在實(shí)現(xiàn)方法上, 設(shè)計(jì)了信任域預(yù)處理, 使之與挖掘引擎緊密結(jié)合, 共同完成W eb 上的數(shù)據(jù)挖掘。本文下一步工作將進(jìn)一步研究現(xiàn)有的信任評(píng)測(cè)和實(shí)現(xiàn)結(jié)果排序, 以求更換推斷的可信結(jié)果。8Lae

30、nder A H , Berthier R N, Altigran S. DEByE date extraction by example. Data &Know ledge Engineerin g, 2002, 40(2 :121 1549Lin S H, H o J M. Discovering informative con tent blocks from W eb documents %Proceedings of th e Eighth ACM International Confer ence on Know ledge Discovery and Data M ini

31、ng. ACM Press, 2002:588 59310Alb erto D , An tonio G , Pablo G . Us er centred versus system參考文獻(xiàn)1Zhou X, Li Y, et al. U sing Information Filtering in W eb Data M ining Process %2007IEEE/W IC/ACM International C onfe r ence on W eb Intelligen ce. 2007:163 1692M ichael C , Hs inchu n C . A machin e le

32、arning approach to w eb page filterin g usin g conten t an d structu re analysi. Decis ion Su p port Sys tems, 2008(44 :482 494centred evalu ation of a personalization sy stem. Information Pro cessin g and M anagement, 2008(44 :1293 130711http:/lu cen e. apache. org/nutch/index. html12高克寧, 王波, 等. WW

33、 W 網(wǎng)站分類體系包裝器WCSW J . 東北大學(xué)學(xué)報(bào):自然科學(xué)版, 2007, 21(1 :44 4813王偉, 張東啟. 基于Bayes 網(wǎng)絡(luò)的內(nèi)容信任R. 上海:同濟(jì)大學(xué)嵌入式系統(tǒng)與服務(wù)計(jì)算教育部重點(diǎn)實(shí)驗(yàn)室, 2008(上接第194頁(yè)現(xiàn)基本功能的基礎(chǔ)之上, 在用戶層實(shí)現(xiàn)策略支持。這樣就使系統(tǒng)具有良好的可擴(kuò)充性、通用性、靈活性以及可維護(hù)性。此外, 通過(guò)pr oc 文件系統(tǒng), 本檢查點(diǎn)系統(tǒng)提供了一個(gè)簡(jiǎn)單的接口供用戶以命令行的形式對(duì)進(jìn)程進(jìn)行動(dòng)態(tài)操作, 方便靈活。采取檢查點(diǎn)時(shí)使用命令行:flag=checkpoint, 需要恢復(fù)、重啟進(jìn)程時(shí), 使用命令行:flag =reco very , 程序

34、將加載檢查點(diǎn)文件, 回滾到最近的檢查點(diǎn)狀態(tài)重新執(zhí)行。結(jié)束語(yǔ) 本文簡(jiǎn)要介紹了用戶級(jí)進(jìn)程檢查點(diǎn)系統(tǒng)與系統(tǒng)級(jí)進(jìn)程檢查點(diǎn)系統(tǒng)各自的優(yōu)缺點(diǎn), 并在此基礎(chǔ)上利用L inux 內(nèi)核模塊設(shè)計(jì)實(shí)現(xiàn)了基于L inux 內(nèi)核的進(jìn)程檢查點(diǎn)系統(tǒng)。介紹了此系統(tǒng)的設(shè)計(jì)思路、工作原理以及工作流程, 并且給出了幾個(gè)主要函數(shù)的原型及各自的功能實(shí)現(xiàn), 最后對(duì)系統(tǒng)的性能進(jìn)行整體評(píng)價(jià), 此檢查點(diǎn)與恢復(fù)系統(tǒng)結(jié)構(gòu)設(shè)計(jì)具有靈活性、通用性、良好的可擴(kuò)充性以及可維護(hù)性優(yōu)點(diǎn)。5678910參考文獻(xiàn)1J ose C S, Petrini F, Davis K, et al. Cu rrent Practice an d a Direction Fo

35、rw ard in C heckpoint/Restart Implementation for Fault T oleran ce %Proceedings of th e 19th IEEE International Parallel and Dis trib uted Processing S ym posium, 2005. IPDPS &05. April 2005:19E lnozahy M , Alvisi L, W ang Y M. A Sur vey of Rollb ack Reco very Protocols in M essage Pas sing S ys

36、tems. ACM Computing S urveys , 2002, 34(3 :375 408汪東升, 沈美明, 鄭緯民, 等. 一種基于檢查點(diǎn)的卷回恢復(fù)與進(jìn)程遷移系統(tǒng)J. 軟件學(xué)報(bào), 1999, 10(1 :68 73魏曉輝, 鞠九濱. 分布式系統(tǒng)中的檢查點(diǎn)算法J . 計(jì)算機(jī)學(xué)報(bào),1121213341998, 21(4 :367 375Sancho J C, Petrin i F, Joh nson G, et al. On the Feasibility of In cremental Checkpointing for Scientific Computing %Proceedings of the 18th In ternation al Parallel &Distributed Proces sing Sym posium, 2004. IPDPS &04. April 2005:58Lu s M S , Joao G S . System level versus U ser Defined Ch eck pointing %Proceedin gs Seventeenth IEEE Symposiu m on Relia ble Distribu t