基于動態(tài)分組的兩級檢查點算法*

劉國良 陳蜀宇 徐光俠 常光輝

(重慶大學(xué)計算機學(xué)院,重慶 400044)

檢查點設(shè)置及回卷恢復(fù)技術(shù)是實現(xiàn)容錯計算、提高系統(tǒng)可靠性的一種有效途徑[1-3].其基本思想是:當(dāng)系統(tǒng)在正常運行時,每隔一段時間把系統(tǒng)狀態(tài)保存到可靠存儲介質(zhì)(稱作檢查點)上;當(dāng)系統(tǒng)出現(xiàn)故障時,系統(tǒng)回卷到檢查點狀態(tài),把計算損失減少到檢查點時刻至故障發(fā)生時所做的計算,避免了程序從頭開始執(zhí)行[1,4-5].

目前,檢查點算法主要有兩種:協(xié)調(diào)檢查點和獨立檢查點算法[6-9].在獨立檢查點算法中,進(jìn)程具有極大的自主性來決定記錄檢查點的時機,因此在正常計算階段所需開銷較小.然而當(dāng)故障發(fā)生時,容易導(dǎo)致多米諾效應(yīng)[10-11];進(jìn)程需要記錄多個檢查點,導(dǎo)致不必要的空間開銷.協(xié)調(diào)檢查點算法要求每次獲得的檢查點都是全局一致檢查點,每個進(jìn)程只需記錄一個檢查點,不會發(fā)生多米諾效應(yīng),但在正常計算階段仍需要較高的同步開銷[12-14].

就包含多個節(jié)點的應(yīng)用而言,節(jié)點間交換信息的頻率是不一樣的,甚至相差很大[4-5],因此需要一種機制來適應(yīng)這種要求.

文獻(xiàn)[1]中采用混合檢查點的方式:簇內(nèi)采用協(xié)調(diào)檢查點算法、簇間采用通信誘導(dǎo)算法,其優(yōu)點是簇內(nèi)檢查點的獲取可以并行進(jìn)行,缺點是發(fā)生故障后,簇間容易導(dǎo)致信息風(fēng)暴.文獻(xiàn)[2-3]中通過發(fā)送節(jié)點來保證獲得一致檢查點,但未考慮節(jié)點間的通信頻率、通信延遲、通信帶寬等動態(tài)指標(biāo),在回卷階段產(chǎn)生較大開銷.

針對分布式應(yīng)用的特點,文中提出了一種基于動態(tài)分組的兩級檢查點算法,根據(jù)節(jié)點間通信的頻率、通信延遲、通信帶寬及分組中節(jié)點數(shù)等指標(biāo)來實現(xiàn)動態(tài)分組,實現(xiàn)分組的高內(nèi)聚低耦合.由于組內(nèi)通信延遲小、節(jié)點數(shù)不多,因此文中采用協(xié)調(diào)檢查點算法.組間通常是由高延遲、低帶寬的網(wǎng)絡(luò)相互連接,并且組間的通信頻率較低,文中提出的系統(tǒng)級檢查點算法充分考慮了這個特點;每個分組是否獲得檢查點,與其它分組無關(guān),各個分組可以獨立地、以并行方式獲得系統(tǒng)級檢查點;通過發(fā)送分組來確保分組間不會產(chǎn)生孤兒消息,每次獲得的系統(tǒng)級檢查點均是全局一致檢查點,避免了多米諾效應(yīng)的發(fā)生.

1 系統(tǒng)模型

1.1 系統(tǒng)體系結(jié)構(gòu)

文中提出的檢查點算法的應(yīng)用對象是一些開放的分布式系統(tǒng),采用與文獻(xiàn)[1]中相似的系統(tǒng)體系結(jié)構(gòu),如圖1所示.

圖1 系統(tǒng)體系結(jié)構(gòu)Fig.1 System architecture

系統(tǒng)中多個分組通過網(wǎng)絡(luò)相互連接,各個分組是動態(tài)劃分的,劃分的依據(jù)是節(jié)點間的信息交互頻率、通信延遲時間等指標(biāo)(具體根據(jù)應(yīng)用需要確定).每個分組內(nèi)包含若干個節(jié)點,且至少有一個節(jié)點.1.

2 算法體系結(jié)構(gòu)

將兩級檢查點算法應(yīng)用于系統(tǒng)中,其體系結(jié)構(gòu)如圖2所示.

圖2 算法體系結(jié)構(gòu)Fig.2 Algorithm architecture

由圖 2可知,多個組級檢查點算法連接到一個系統(tǒng)級檢查點算法上.分組內(nèi)的節(jié)點是通過低延遲、高帶寬的網(wǎng)絡(luò)連接在一起,并且其數(shù)量一般來說也不是很多,因此,適合采用協(xié)調(diào)檢查點算法.

組間一般是通過高延遲、低帶寬的網(wǎng)絡(luò)連接在一起,不適合采用協(xié)調(diào)檢查點算法.另外,對于大規(guī)模分布式應(yīng)用而言,其分組數(shù)數(shù)以千計,并且各個分組中節(jié)點的負(fù)載、操作系統(tǒng)的調(diào)度策略等均可能對檢查點同步產(chǎn)生不可避免的影響,為此文中提出了系統(tǒng)級檢查點算法.

2 檢查點算法

2.1 動態(tài)分組策略

分組策略的選擇需要綜合考慮節(jié)點間消息交互的頻率、網(wǎng)絡(luò)帶寬、延遲及節(jié)點數(shù)等指標(biāo),使信息交互和檢查點算法的時空開銷間達(dá)到效能最大化.假設(shè)這幾個指標(biāo)的閾值分別為 θf、θb、θd和θn.若兩個節(jié)點間的通信頻率大于θf、通信帶寬大于θb、延遲小于θd且分組G中節(jié)點數(shù)小于θn,則將這兩個節(jié)點劃分到一個分組G中.若分組 G中節(jié)點數(shù)大于 θn,則這兩個節(jié)點歸為一個新的分組.

當(dāng)然,具體分組策略是和應(yīng)用本身相關(guān)的,這里只是舉了一個例子,節(jié)點間消息交互的頻率、網(wǎng)絡(luò)帶寬、延遲及節(jié)點數(shù)等指標(biāo)之間的組合策略有很多種,需要根據(jù)實際需要進(jìn)行決策.

2.2 組級檢查點算法

每個分組內(nèi)該采用哪種檢查點算法,與分組策略有關(guān).由于分組中的節(jié)點是通過高性能網(wǎng)絡(luò)(低延遲、高帶寬)連接,并且節(jié)點較少,因此采用協(xié)調(diào)檢查點算法能夠獲得很好的效果.

假設(shè)分組中節(jié)點數(shù)為 m,采用文獻(xiàn)[15]中的協(xié)調(diào)檢查點算法,則需要 2m個控制消息,時間復(fù)雜度為O(m).

2.3 系統(tǒng)級檢查點算法

當(dāng)多個分組中的進(jìn)程參與一個分布式應(yīng)用時,需要調(diào)用系統(tǒng)級檢查點算法.定義一個分布式并行應(yīng)用程序為P,P={G1,G2,…,Gn},n是該并行應(yīng)用程序中包含的分組數(shù).把啟動算法的分組稱為啟動分組,其它分組稱為應(yīng)用分組.啟動分組中的某個進(jìn)程按照一定的規(guī)則啟動算法.任何分組都可能成為啟動分組,這種設(shè)計更符合分布式應(yīng)用特征.

為了敘述的一致性,文中給出如下符號定義:

F為發(fā)送消息標(biāo)志,表示在一個檢查點后是否已發(fā)送了消息,值為 1表示相應(yīng)分組已將應(yīng)用消息發(fā)送到其它分組,值為 0表示未發(fā)送消息;Fi表示分組Gi(i=1,2,…,n)的發(fā)送消息標(biāo)志.

CN為檢查點序號,每執(zhí)行一次系統(tǒng)級檢查點算法,其值加1;CNi表示分組Gi(i=1,2,…,n)的檢查點序號.

St為一致分組狀態(tài),是分組級的全局一致狀態(tài),即分組中各個進(jìn)程狀態(tài)的集合;Sti表示分組Gi(i=1,2,…,n)的一致分組狀態(tài).

SN為發(fā)送消息序號,用來唯一標(biāo)識分組所發(fā)送的消息,每發(fā)送一條消息,其值加1;SNi表示分組Gi(i=1,2,…,n)發(fā)送的消息序號.

Ci,x為分組Gi(i=1,2,…,n)的第x個檢查點.

MC為控制消息,啟動系統(tǒng)級檢查點算法時使用.

M表示分組間發(fā)送的應(yīng)用消息;Mi表示分組Gi發(fā)送的應(yīng)用消息.

算法中用于協(xié)調(diào)分組行為的各種消息稱為控制消息,分組之間為實現(xiàn)計算目標(biāo)而進(jìn)行通信的消息稱為應(yīng)用消息.

2.3.1 相關(guān)定理

定理1 對給定的任意分組Gi(i=1,2,…,n),在任意時刻T′,如果發(fā)送消息標(biāo)志滿足Fi=0,則在T′時刻,Gi已發(fā)送的所有消息都不是孤兒消息.

證明 根據(jù)文中算法,假設(shè)Ci,x為分組Gi的任意檢查點,則 T′時刻要么在獲得檢查點Ci,x-1和 Ci,x時刻之間,要么與獲得檢查點 Ci,x時刻重疊,要么在獲得檢查點Ci,x和 Ci,x+1時刻之間,如圖3所示.

圖3 T′時刻的位置示意圖Fig.3 Schematic diagram of position of time T′

(1)假設(shè)T′時刻位于獲得檢查點Ci,x-1和Ci,x時刻之間,若發(fā)送標(biāo)志 Fi=0,則根據(jù)算法可知,在獲得檢查點Ci,x-1時刻到 T′時刻這段時間內(nèi),分組Gi沒有發(fā)送任何消息,因而不存在孤兒消息.

(2)假設(shè)T′時刻與獲得檢查點Ci,x時刻重疊,若發(fā)送標(biāo)志Fi=0,則根據(jù)算法可知,在 T′時刻首先獲得檢查點Ci,x,再將標(biāo)志Fi置0.即記錄了分組Gi在獲得檢查點 Ci,x-1和 Ci,x期間發(fā)送的所有消息,因而不存在孤兒消息.

(3)假設(shè)T′時刻位于獲得檢查點Ci,x和Ci,x+1時刻之間,若發(fā)送標(biāo)志 Fi=0,則根據(jù)算法可知,在獲得檢查點Ci,x時刻到T′時刻這段時間內(nèi),分組Gi沒有發(fā)送任何消息,因而不存在孤兒消息.

綜上所述,定理得證.

定理2 假如分組Gk(k=1,2,……,n)向分組Gi發(fā)送應(yīng)用消息〈Mk,CNk,SNk〉,且分組Gk的檢查點序號CNk與Gi的檢查點序號CNi滿足CNk＞CNi,則Gk發(fā)送的應(yīng)用消息Mk不會變成孤兒消息.

證明 當(dāng)分組Gi收到應(yīng)用消息〈Mk,CNk,SNk〉后,比較檢查點序號CNk與CNi,若CNk＞CNi,表明算法的第x次執(zhí)行已經(jīng)開始了,Ci會很快收到啟動分組的控制消息〈MC,CNk〉.分組Gi并不等待控制消息〈MC,CNk〉,而是根據(jù)自身的發(fā)送標(biāo)志Fi來判斷是否獲得檢查點,然后處理收到的應(yīng)用消息 Mk,意味著接收的應(yīng)用消息 Mk沒有被接收分組 Gi記錄,根據(jù)孤兒消息定義知道,應(yīng)用消息 Mk不會變成孤兒消息.證畢.

定理3 假如分組Gk向分組Gi發(fā)送應(yīng)用消息〈Mk,CNk,SNk〉,且分組Gk的檢查點序號CNk與分組Gi的檢查點序號CNi滿足CNk=CNi=x,則分組Gk發(fā)送的應(yīng)用消息Mk不會變成孤兒消息.

證明略.

定理4 假如分組Gk向分組Gi發(fā)送應(yīng)用消息〈Mk,CNk,SNk〉,且分組Gk的檢查點序號CNk與分組Gi的檢查點序號CNi滿足CNk＜CNi,則分組Gk發(fā)送的應(yīng)用消息Mk不會變成孤兒消息.

證明略.

2.3.2 算法描述

系統(tǒng)級檢查點算法是一個單階段非阻塞算法,即算法允許分組直接獲得永久檢查點,不需要獲得臨時檢查點,因而相比傳統(tǒng)的兩階段提交算法,大大提高了執(zhí)行速度.另外,系統(tǒng)級檢查點算法能夠保證每次獲得的檢查點都是系統(tǒng)級全局一致檢查點,因而大大減少了獲得的檢查點數(shù)量.系統(tǒng)級檢查點算法的描述如下:

證明 對啟動分組Gk(k=1,2,…,n)而言有2種情況:如果其發(fā)送消息標(biāo)志Fk=1,即滿足if條件,那么該分組首先獲得檢查點,然后把標(biāo)志 Fk置為 0,因此,只要檢查點獲得成功,標(biāo)志 Fk必為 0,根據(jù)定理1可知,分組Gk已發(fā)送的所有消息都不是孤兒消息.如果不滿足if條件,即進(jìn)入else段代碼,此時,發(fā)送標(biāo)志Fk必為0,根據(jù)定理 1,分組 Gk已發(fā)送的所有消息都不是孤兒消息.

對應(yīng)用分組Gi(i=1,2,…,n)而言有3種情況.

(1)假如應(yīng)用分組Gi(i=1,2,…,n)收到啟動分組Gk(k=1,2,…,n)發(fā)送的控制消息〈MC,CNk〉,則滿足第一個if條件,有:①假如其發(fā)送消息標(biāo)志Fi=1,即滿足 if條件,那么該分組首先獲得檢查點,然后把標(biāo)志 Fi置為 0,因此,只要檢查點獲得成功,標(biāo)志Fi必為 0,根據(jù)定理 1,分組Gi已發(fā)送的所有消息都不是孤兒消息.②假如不滿足if條件,即進(jìn)入else段代碼,此時,發(fā)送標(biāo)志 Fi必為0,根據(jù)定理1,分組Gi已發(fā)送的所有消息都不是孤兒消息.

(2)假如應(yīng)用分組Gi(i=1,2,…,n)沒有收到啟動分組Gk(k=1,2,…,n)發(fā)送的控制消息〈MC, CNk〉,但收到了其它分組Gj(j=1,2,…,n)(包括分組Gk)發(fā)送的應(yīng)用消息〈Mj,CNj,SNj〉,即滿足else if條件,有兩種情況:①如果CNi＜CNj,則進(jìn)入if語句,根據(jù)定理 2,進(jìn)程 Pj發(fā)送的任何應(yīng)用消息〈Mj, CNj,SNj〉均不會變成孤兒消息,即應(yīng)用分組Gi在接收控制消息〈MC,CNk〉之前接收的任何分組的任意應(yīng)用消息〈Mj,CNj,SNj〉均不會變成孤兒消息.②如果CNi≥CNj,則進(jìn)入else語句,必滿足定理3、定理4,分組Gj發(fā)送的任何應(yīng)用消息〈Mj,CNj,SNj〉均不會變成孤兒消息.

(3)如果既不滿足情況(1)也不滿足情況(2),則程序進(jìn)入最后一個else語句,即分組Gi正常執(zhí)行,不會獲得檢查點,當(dāng)然也沒有孤兒消息.

綜上所述,對任意的分組Gi(i=1,2,…,n),在檢查點處,均沒有孤兒消息存在,所以,通過該算法獲得的檢查點集一定是系統(tǒng)級全局一致檢查點.證畢.

2.3.3 啟動周期

算法啟動周期T的選擇需要綜合考慮,如果太短,就會導(dǎo)致算法頻繁啟動,增加額外負(fù)載;如果太長,系統(tǒng)發(fā)生故障后,會導(dǎo)致丟失的計算量較大.另外,啟動周期的選擇還需要有利于回卷恢復(fù)算法的實現(xiàn).設(shè)系統(tǒng)中任意兩個分組Gi和Gj間傳送消息需要的時間為ti,j(i≠j),兩個分組間傳送消息需要的最大時間為tmax={ti,j,i≠j},則文中算法啟動周期T取略大于tmax.選擇該啟動周期是為了盡量減少記錄中途消息的數(shù)量(處理中途消息的常用方法是消息日志方法).由于T＞tmax,所以一個分組Gi只需要在它的最近檢查點 Ci,x保存檢查點間隔(Ci,x-1,Ci,x)內(nèi)所發(fā)送的消息,如圖 4所示.圖 4中,考慮兩個分組Gi和Gj,由于T＞tmax,對分組Gi來說,在檢查點間隔(Ci,x-2,Ci,x-1)內(nèi)發(fā)送的任意消息M都會在分組Gj的最近檢查點Cj,x獲得之前到達(dá)分組Gj.現(xiàn)假設(shè)分組Gi發(fā)生故障,兩個分組在恢復(fù)算法的作用下回卷到它們的最近檢查點{Ci,x,Cj,x}并重新計算,由于消息M在分組Gj的檢查點Cj,x之前已經(jīng)被接收,即 M不會變成中途消息,所以不需要進(jìn)行重傳.因此在發(fā)送分組Gi的最近檢查點Ci,x處就不需要保存日志信息.相反,圖 4中的消息 M1及M2均可能變成中途消息,因此需要在發(fā)送分組 Gi的最近檢查點Ci,x處保存日志信息,在恢復(fù)時進(jìn)行重傳,防止中途消息丟失.

圖4 中途消息Fig.4 In-transitmessage

2.3.4 時間復(fù)雜度

在以往的同步算法中,通常利用“消息驅(qū)趕”的方式獲得全局一致狀態(tài).這種方式實現(xiàn)簡單,不足之處在于數(shù)量級為O(n2)的清空消息CLS_MSG將給系統(tǒng)帶來很大的通信量.當(dāng)n較大時,這種同步控制消息量以平方的量級增長,在時間和空間上都是不能接受的.

在本文算法中,只有啟動分組通過控制消息MC與應(yīng)用分組進(jìn)行交互,如果分組數(shù)為 n,則只需要n-1個控制消息,遠(yuǎn)低于已有算法;其它應(yīng)用分組只是根據(jù)自己的發(fā)送標(biāo)識F判斷是否獲得檢查點,不需要其它分組的任何額外消息.因此文中算法的時間復(fù)雜度為O(n),遠(yuǎn)低于傳統(tǒng)算法的時間復(fù)雜度O(n2),有效地提高了系統(tǒng)的效率和擴(kuò)展性.

3 性能評估

為了評估文中算法的性能,采用文中算法與文獻(xiàn)[1,15-16]中算法進(jìn)行比較,主要考察算法是否阻塞及同步控制消息的費用.

設(shè)csend為從一個進(jìn)程發(fā)送一條消息到另一個進(jìn)程的費用,cbroad為從一個進(jìn)程廣播一條消息到所有進(jìn)程的費用,Nmin為需要獲得檢查點的進(jìn)程數(shù),r為系統(tǒng)中的進(jìn)程數(shù),q為分組數(shù),y為分組中節(jié)點數(shù).幾種算法的性能比較結(jié)果如表1所示.

表1 幾種算法的性能比較Table 1 Comparison of performance of several algorithms

從表 1中可知,文獻(xiàn)[1,15]中算法是阻塞算法,因此只有當(dāng)進(jìn)程獲得了永久檢查點后才能進(jìn)行正常計算.在控制消息費用方面,文獻(xiàn)[16]中采用的是兩階段提交方式,首先一個進(jìn)程發(fā)送2個控制消息來獲得臨時檢查點,系統(tǒng)負(fù)載為2Nmincsend,在第二階段臨時檢查點轉(zhuǎn)變?yōu)橛谰脵z查點,消息負(fù)載為min(Nmincsend,cbroad),因此總費用為2Nmincsend+ min(Nmincsend,cbroad).文中算法是組級算法加系統(tǒng)級算法,組級算法采用文獻(xiàn)[15]中算法,消息費用為(y/r)(2cbroad+rcsend);系統(tǒng)級采用文中提出的單階段算法,直接獲得永久檢查點,只需要廣播一條請求消息,費用為(q/r)cbroad,因此總費用為

其中cbroad=rcsend.系統(tǒng)至少包含兩個分組,一般情況下q+y≤r,算法在最壞情況下,控制消息費用為2cbroad.

當(dāng)進(jìn)程數(shù)較多時,算法是否適用主要歸結(jié)為進(jìn)程數(shù)與控制消息數(shù)的關(guān)系,即進(jìn)程數(shù)較多時,算法的負(fù)載應(yīng)該比較低.文獻(xiàn)[1]和文獻(xiàn)[15]中算法具有相同的負(fù)載,假設(shè)平均獲得的檢查點進(jìn)程數(shù)為總進(jìn)程數(shù)的 80%,則文中算法在最壞情況下的負(fù)載為2cbroad.采用文中算法與文獻(xiàn)[1,16]中算法進(jìn)行比較,進(jìn)程數(shù)與控制消息數(shù)的關(guān)系如圖5所示.

圖5 幾種算法的進(jìn)程數(shù)與控制消息數(shù)的關(guān)系Fig.5 Process numbers ofseveral algorithms versus numbers of controlmessages

從圖 5中可以看出,隨著進(jìn)程數(shù)的增加,3種算法需要的協(xié)調(diào)控制消息均是按線性規(guī)律增長.設(shè)系統(tǒng)中進(jìn)程數(shù)為 r,則文獻(xiàn)[1]中算法需要 3r條控制消息,文獻(xiàn)[16]中算法大約需要 2.4r條控制消息,文中檢查點算法所需控制消息少于文獻(xiàn)[1,16]中算法,在最壞情況下,僅需2r條控制消息.

為了驗證文中算法的有效性,采用多個節(jié)點進(jìn)行測試,每個節(jié)點CPU采用Intel賽揚450、CPU頻率2.2GHz、二級緩存512kB、主板芯片組IntelG41+ ICH7、內(nèi)存2GB.所有節(jié)點經(jīng)由1Mb/s網(wǎng)絡(luò)連接(網(wǎng)卡采用Intel8139,交換機采用H3CS5120,在端口作速率匹配),操作系統(tǒng)為Windows XP.在不包含組級協(xié)調(diào)檢查點算法的條件下,系統(tǒng)級單階段檢查點算法的執(zhí)行時間與進(jìn)程數(shù)的關(guān)系如圖6所示.

圖6 系統(tǒng)級檢查點算法的執(zhí)行時間與進(jìn)程數(shù)的關(guān)系Fig.6 Execution time of system-level checkpoint algorithm versus number of processes

從圖 6中可以看出,系統(tǒng)級檢查點算法的執(zhí)行時間開銷基本上為毫秒級,與并行程序的運行時間相比是微不足道的.

設(shè)每個分組中有 10個進(jìn)程,每個節(jié)點對應(yīng)一個進(jìn)程,組內(nèi)進(jìn)程間帶寬為10Mb/s(節(jié)點經(jīng)由100Mb/s快速以太網(wǎng)連接,網(wǎng)卡采用Intel 8139,交換機采用H3CS5120,在端口作速率匹配),組間帶寬為1Mb/s (網(wǎng)卡采用Intel 8139,交換機采用H 3CS5120,在端口作速率匹配),操作系統(tǒng)為Windows XP,組級采用文獻(xiàn)[15]中協(xié)調(diào)檢查點算法,系統(tǒng)級采用單階段檢查點算法,兩級檢查點算法的執(zhí)行時間與進(jìn)程數(shù)的關(guān)系如圖7所示.

圖7 兩級檢查點算法的執(zhí)行時間與進(jìn)程數(shù)的關(guān)系Fig.7 Execution time of two-level checkpoint algorithm versus number of processes

從圖 7中可以看出,兩級檢查點算法的執(zhí)行時間開銷基本上為毫秒級,隨著并行進(jìn)程規(guī)模的擴(kuò)大,檢查點的時間開銷基本上呈線性增長,能夠適應(yīng)大規(guī)模的分布式并行應(yīng)用.

4 結(jié)語

文中提出了一種基于動態(tài)分組的兩級檢查點算法:組級采用協(xié)調(diào)檢查點算法,系統(tǒng)級采用單階段檢查點算法.該算法能動態(tài)適應(yīng)應(yīng)用自身的要求,提高了資源的整體效能,并通過發(fā)送分組來確保分組間不會產(chǎn)生孤兒消息,實現(xiàn)了由傳統(tǒng)的兩階段提交算法到單階段算法的轉(zhuǎn)變,大大提高算法的執(zhí)行速度,最后通過實驗驗證了文中算法的有效性,該算法能夠適應(yīng)大規(guī)模的分布式并行應(yīng)用.今后將在更大規(guī)模系統(tǒng)環(huán)境下對文中算法進(jìn)行實驗,驗證算法的有效性,同時考慮將檢查點算法與操作系統(tǒng)的調(diào)度算法結(jié)合起來,以提高系統(tǒng)的容錯能力.

[1] Monnet S,Morin C,Badrinath R.Hybrid checkpointing for parallel applications in cluster federations[C]∥Proceedings of IEEE International Symposium on Cluster Computing and the Grid.Washington D C:IEEE,2004:773-782.

[2] Gupta B,Rahim i S,Ahmad R.A new roll-forward checkpointing/recovery mechanism for cluster federation[J]. International Journal of Computer Science and Network Security,2006,6(11):292-298.

[3] Gupta B,Rahimi Shahram,Yang Yixin.A novel roll-back mechanism for performance enhancement of asynchronous checkpointing and recovery[J].Informatica:Slovenia, 2007,31(1):1-13.

[4] Elnozahy EN,Alvisi Lorenzo,Wang Yi-min,et al.A survey of rollback-recovery protocols in message-passing systems[J].ACM Computing Surveys,2002,34(3):375-408.

[5] Bowen N S,Pradhan D K.Processor-and memory-based checkpoint and rollback recovery[J].Computer,1993,26 (2):22-31.

[6] Bosilca George,Delmas Remi,Dongarra Jack,et al.Algorithm-based fault tolerance app lied to high performance computing[J].Journalof Parallel Distributed Computer, 2009,69(4):410-416.

[7] Sm ith Jim,Watson Paul.Applying low-overhead rollbackrecovery to wide area distributed query processing[R]. Newcastle:School of Computing Science,University of Newcastle upon Tyne,2004.

[8] Gupta Sunil K,Chauhan R K,Kumar Parveen.Backward error recovery protocols in distributed mobile systems:a survey[J].Journal of Theoretical and Applied In formation Technology,2008,30(4):225-240.

[9] Rusu Claudia,Grecu Cristian,Anghel Lorena.Blocking and non-b locking checkpointing and rollback recovery for networks-on-chip[C]∥Proceedings of the 2nd Workshop on Dependable and Secure Nanocomputing.Anchorage:IEEE, 2008:1-6.

[10] Manivannan D.Checkpointing and rollback recovery in distributed systems:existing solutions,open issues and p roposed solutions[C]∥Proceedings of the 12th WSEAS International Con ference on Systems.Herak lion: ACM,2008:22-24.

[11] de Camargo Raphael Y,Goldchleger Andrei,Kon Fabio, et al.Checkpointing-based rollback recovery for parallel app lications on the InteGrade grid iddleware[C]∥Proceedings of the 2nd Workshop on Middleware for Grid Computing.Toronto:ACM,2004:35-40.

[12] Janakiraman G,Tamir Y.Coordinated checkpointing-rollback error recovery for distributed shared memorymu lticomputers[C]∥Proceedings of the 13th Symposium on Reliable Distributed Systems.Dana Point:IEEE,1994: 42-51.

[13] Gupta Bidyut,RahimiShahram,Liu Ziping.Design ofhigh performance distributed snapshot recovery algorithms for ring networks[J].Journalof Computing and In formation Technology,2008,16(1):23-28.

[14] Chandy K Mani,Lamport Leslie.Distributed snapshots: determ ining global states of distributed systems[J]. ACM Transactions on Computer Systems,1985,3(1): 63-75.

[15] Wang D S,Shao M L.A cooperative checkpointing algorithm with message complexity O(n)[J].Journal of Software,2003,14(1):43-48.

[16] Cao G,Singhal M.Mutable checkpoints:a new checkpointing approach for mobile computing systems[J]. IEEE Transactions on Parallel and Distributed Systems, 2001,12(2):157-172.