基于動態備份的容錯網格任務調度

摘要：提出了一種基于自適應備份的網格容錯任務調度算法:最高百分之k備份算法。該算法對任務的安全需求和資源的信任等級進行匹配，在系統安全等級較低并且網絡和主機可能失效的網格環境中進行容錯任務調度。調度時，該算法根據整個網格系統的安全狀況，對具有最高安全需求的百分之k的任務進行動態備份，任務備份數根據系統安全狀況自適應變化，并對失敗的任務重新調度。仿真結果表明，該算法可以有效提高不安全網格環境下的任務調度成功率，具有很好的容錯性和可擴展性，優于固定備份數的網格任務調度算法。

關鍵詞：網格計算;任務調度;容錯;動態備份

中圖分類號：TP393文獻標志碼：A

文章編號：1001－3695(2008)03－0738－03

在網格[1]環境中，對于安全威脅的擔憂和對遠程資源不夠信任限制了將任務調度到遠程主機上。在任務調度過程中，如果一個節點遭受攻擊，那么它的資源從該自治域外部就有可能無法訪問，調度給該節點的任務就有可能會產生延遲或失敗。目前已知的大部分網格任務調度算法[2~4]都忽略了網格安全因素，假設網格資源100%可靠。隨著網格規模的擴大，在跨自治域的網格任務調度過程中，必須考慮安全性這一問題。網格的動態性使得網格系統各節點的特性和行為無法精確預測。隨著網格規模的擴大、任務執行時間的增長，網格系統的故障率將越來越高。因此，在網格任務調度過程中，必須保證任務調度具有自適應性、容錯性[5]和可擴展性。任務備份[6]是常用的容錯調度方法，以保證在由于節點本身的故障或者網絡延遲而導致任務失敗時仍然能夠成功執行任務，并保證任務調度的成功率保持在一個較高的水平。但是目前提出的基于備份的網格任務調度算法中，均使用固定數目的任務備份，無法適應網格環境的動態變化，造成在網格安全狀況較好時執行過多的任務備份，而在網格安全狀況較差時，過少的任務備份使得任務調度的成功率較低。

1相關工作

網格環境在內在本質上是不可靠的[7，8]。文獻[7]提出了一個失效檢測服務和一個靈活的錯誤處理框架作為網格上的容錯機制。在網格環境中，很多資源的利用率很低，這些空閑的資源可以用來執行任務備份，以保證至少有一個任務備份可以成功執行。因此，基于備份的容錯任務調度研究較多。文獻[6]提出了一個在線的容錯調度策略DFTS (distributed faulttolerant scheduling)。但是DFTS使用固定的兩個備份數的策略，對于網格環境的變化無法作出調整。本文提出一種自適應的備份策略，根據系統安全狀況的變化動態調整備份數。與固定備份數的調度策略相比，不僅提高了任務執行的成功率，并且減少了總的備份執行數量，節省了資源的使用。

文獻[9]將信任概念集成到網格資源管理中，并提出了一個將安全影響集成到調度算法中的信任模型。信譽度模型是在P2P網格和分布式安全資源訪問中使用較多的一種模型，即任一資源都有一定的信譽值，信譽值的大小反映了資源的可靠性程度。其中，有集中式信譽度模型[10]和分布式信譽度與授權模型[11]。文獻[12]提出了基于模糊推理的節點信任模型，解決了節點信任屬性的不確定性和模糊性問題，增強了大量網格資源節點間互操作的安全性。

為了使任務調度更加有效，網格任務必須帶有一個安全需求(security demand，SD)，而資源提供者必須帶有一個信任等級[12](trust level，TL)。本文假設網格用戶在提交任務時同時提交了安全需求，并通過文獻[12]中的模糊算法，根據資源節點的歷史性能評估資源節點的可信度，即節點的信任等級。當節點的信任等級滿足任務的安全需求時，才將任務調度到該節點。

文獻[13]提出了一種基于網格信任模型和信任效益函數的安全驅動的任務調度算法，但該調度算法對于不滿足信任需求的任務直接拋棄。在實際的網格環境中，在調度事件發生時，任務的安全需求和節點的信任等級可能不匹配，為了提高調度算法的容錯性，應該延遲調度這些任務，而不是直接拋棄。本文提出的基于網格安全的容錯調度算法，對于安全需求暫時無法滿足的任務不是直接拋棄，而是在下一輪調度時再次調度該任務，直到該任務能夠被成功執行。這樣，提高了任務調度的成功率。

2最高百分之k備份算法

由于固定的任務備份數不能適應網格安全環境的動態變化，本文提出一種自適應的任務備份數模型，即最高百分之k備份策略，使任務備份數隨著網格內所有節點的信任等級的變化而相應增減。最高百分之k備份策略將待調度任務按安全需求由高到低進行排序，然后將其中百分之k的具有最高安全需求的任務進行備份。假設節點的信任等級和系統的信任等級已經由文獻[12]提出的模糊模型計算得出。本文將系統的信任等級分為五級，從高到低依次為極高、較高、中等、較低、極低，被選中任務的備份數根據系統安全等級進行確定。當系統的安全等級變化時，備份數也相應變化。

為了簡化調度模型，進行如下假設:a)某一應用程序已經被分解為若干個子任務，子任務之間相互獨立;b)任務沒有截止時間限制和優先權;c)資源的實時狀態已知，且待執行任務在任意主機上的執行時間已知[2];d)在同一個主機上執行的子任務遵循FCFS(firstcome，firstserved)原則，且一個主機一次只執行一個任務，任務一旦執行，就不能被搶斷;e)所有網格系統組件均可能失效，失效可能在任意時間點發生并且最終可以恢復;f)節點失效是互相獨立的，且失效節點總數不超過一個給定百分比[6];g)存在一個主調度器，且主調度器維護一個job table，其中保存各任務的運行狀態及任務-節點對的相關信息。當主調度器失效以后，備用調度器可以接管主調度器的所有工作。

2．1調度流程

設M為主機集合，M={mj|j=1，2，3，…，m}，T為任務集合，T={ti| i=1，2，3，…，n}，給出如下的算法相關參數:

a)SDi，任務ti的安全需求，在用戶提交任務時由用戶指定。0＜SDi＜1，0表示最低的安全需求；1表示最高的安全需求。

b)TLj，主機mj的信任等級。0≤TLj≤1，0表示節點非常不安全；1表示節點完全可信。

c)TL，系統的信任等級。0≤TL≤1，0表示系統整體安全程度非常低，節點完全不可信；1表示系統整體安全程度非常高，節點完全可信。系統的信任等級利用文獻[5]中的算法計算得出。

d)replica，任務備份數。

e)k，備份任務百分比，(100/n)≤k≤100。k值計算如下:

k=max(100/n，100/eTL)

在實際調度中，根據任務隊列中的任務數對k值進行圓整。

f)queue_max，節點主機允許的CPU隊列的最大長度。

g)queue，節點主機實際的CPU運行隊列長度。

h)avail，滿足任務ti的信任需求并且CPU隊列不超過queue_max的主機數。

i)active，當前活動的備份數。

最高百分之k備份策略的調度過程如下:調度器定時對任務池中的任務進行調度。計算所有任務的安全需求SDi、節點的信任等級TLj、系統信任等級TL和任務備份數replica，當系統安全等級由極高到極低變化時， replica分別取0、1、2、3、4(實驗結果表明，當任務備份數大于4時，系統性能顯著下降)。對于任務集合中的所有任務，按照安全需求由高到低的順序進行排序。對于安全需求最高的百分之k的任務進行備份，每個任務的備份數為replica；對于沒有備份的任務，可以認為其備份數為0，即replica=0。調度時，將任務調度到CPU運行隊列沒有超出CPU隊列的最大長度且滿足任務安全需求的信任等級最高的replica+1個節點上，然后從任務集合中刪除該任務。如果可供調度的主機數不夠，則將任務插入到下一次調度的任務集合中，并從當前任務集合中刪除該任務。對剩余的任務重復上述過程，直到當前任務集合為空。最高百分之k備份調度算法的偽代碼描述如下:

when scheduling event occurs {

compute SDi，TLj ，TL and replica

sort the tasks descendingly by its SDi

replicate the kpercent highestSDi tasks in the task set with replica replications

set replica=0 if the task is not replicated

for each task in T

schedule the task to replica+1 machines with queueSD

delete the task from T

update job table

if avail

insert the task into next scheduling tasks set

delete the task from T

update job table

end if

end for

}

該算法充分考慮了網格系統的安全狀況的動態性。在生成每次的任務調度方案之前，均對節點信任等級和系統信任等級進行計算，以保證任務備份數與網格系統的安全狀況相適應。由于k值僅在[36.8，100]之間變化，對于k無法取值的[0，36.8)中，則由任務備份數replica的自適應取值來保證整個任務調度算法的自適應性和容錯性。

2．2任務備份管理

運行備份任務的節點定時向調度器報告自己的運行狀態。調度器一旦接收到任務備份完成的消息，就通知所有其他正在運行該任務備份的主機，終止該任務備份的執行，更新job table和下一次調度的任務隊列；反之，如果調度器在一定時間內沒有接收到某節點的狀態報告，則認為該節點已失效。如果此時活動的任務備份數active＜replica+1，則調度器從所有未運行該備份任務且滿足任務的安全需求的節點中，選擇replica+1-active個CPU運行隊列最短的節點，將任務備份調度到該節點。如果可用節點數不夠，則查看下一次任務集合；如果其中沒有該任務，則插入該任務。

3仿真實驗

3．1網格實例

利用SimGrid軟件包進行調度算法的仿真。網格中PC、集群和超級計算機的比例分別為0.92、0.06和0.02。總主機數為6 000個，單個節點的主機數最多不超過32個，節點之間的帶寬在64 kbps~64 Mbps。主機的計算能力服從正態分布，其中PC和集群的計算能力服從區間[100，400](MFlops)上的正態分布，超級計算機的計算能力服從區間[200，600](MFlops)上的正態分布。假設PC主機具有周期可用性，而集群節點和超級計算機不具有周期特性。PC主機的失效率服從泊松分布，失效率為λpc，集群和超級計算機的失效率分別為λcluster和λsc。

初始的節點信任等級由計算機生成。其中：PC主機的信任等級服從[0，1]上的正態分布；集群主機的信任等級服從[0．4，1]上的正態分布；超級計算機的信任等級服從[0．8，1]上的均勻分布；計算任務的安全需求服從[0．2，0.9]上的均勻分布；任務的期望執行時間滿足[60，160](ms)上的正態分布；任務到達率服從泊松分布；平均到達速率為λtask。

3．2實驗結果

本實驗對比提出的最高百分之k備份策略（KPR)和固定備份數的replication minmin (Rminmin)[6]算法以及不考慮安全和容錯的minmin[2]算法的性能，包括makespan、任務調度成功率、資源使用率和任務平均等待時間。Rminmin算法的固定備份數為2，取20次試驗結果的平均值作為性能參數的測試結果。圖1給出了仿真實驗各算法的性能參數對比。

3．3仿真結果分析

從圖1(a)可以看出，Rminmin算法的makespan最大，minmin算法的makespan最小。這是因為minmin算法不考慮網格安全因素，計算開銷較小，且不對失敗的任務重新調度;KPR算法能夠根據網格安全等級的變化，動態調整備份任務數，因此makespan也較小；固定備份數的Rminmin算法的makespan最大，這主要是由于Rminmin算法不能隨著網格系統的安全等級的變化動態調整任務備份數，使得在網格安全等級較高時，執行了較多的任務備份，造成任務隊列的延長，最終增加了任務的makespan。

從圖1(b)可以看出，在主機和網絡資源均可能失效的網格環境中，KPR算法的調度成功率最高， Rminmin次之，minmin算法的調度成功率最低。KPR和Rminmin由于使用了任務備份而使得調度成功率較高，對安全需求和節點信任等級不匹配的任務延遲一定時間后重新調度，也提高了任務調度的成功率；minmin算法由于不重啟失敗的任務，沒有容錯性，導致任務調度的成功率最低。

從圖1(c)可以看出，網格資源使用率由高到低分別是KPR、minmin和Rminmin算法(注:同一個任務的多個備份的執行，只算一次網格資源使用)。這主要是由于在不安全網格環境中，任務的安全需求和節點信任等級的不匹配往往是暫時的，KPR算法能夠根據網格安全狀況的變化動態調整任務備份數，提高了網格資源使用率;Rminmin算法由于任務備份數無法隨著網格安全環境的變化而變化，對所有任務均進行備份，導致過多地執行備份任務，網格資源的利用率最低。

從圖1(d)可以看出，任務平均等待時間由高到低依次為Rminmin、minmin和KPR算法。Rminmin算法由于過多地復制了任務備份數而導致需執行的總任務備份數增加較多，任務的平均等待時間也最長；KPR算法增加的等待時間要小于增加的任務備份的執行時間；Minmin算法只是簡單地將短任務調度到具有最先完成時間的主機上，可能造成任務負載的不平衡，適應性較差，總體的任務平均等待時間也較大。

綜上所述， KPR算法能夠根據網格安全環境的變化動態調整任務備份數，對于安全特性變化較大的網格系統具有很強的適應性。尤其是在主機和網絡均可能失效的情況下，對失敗的任務進行重調度，雖然增加了一定的任務執行時間，但是顯著提高了任務執行的成功率，并且在大規模網格環境下的擴展性能很好，可適用于大規模網格環境下的安全和容錯的任務調度。

4結束語

在互聯網安全越來越重要的今天，網格任務調度的安全和容錯問題也越來越重要。由于實際的網格節點存在著各種各樣的安全威脅，甚至失效，網格任務調度必須在保證盡快完成任務、提高系統吞吐率的同時，更應該在網格安全環境較差、不信任節點較多的情況下，較好地完成任務，并且在節點失效時能夠重新調度失敗的任務，保證任務調度成功率保持在一個較高的水平。這是符合實際的網格計算環境的，也是可以達到的。本文提出的最高百分之k備份算法以較小的時間代價換取了較高的任務執行成功率和容錯性能，對于大規模網格環境下的安全和容錯任務調度，具有一定的借鑒意義。

本文在對動態備份算法的安全和容錯性能研究中，假設各子任務之間相互獨立，不考慮任務之間的數據依賴關系和通信延遲。在實際的網格環境中，尤其是數據密集型網格應用中，任務通信往往是串行的，而任務的計算往往是并行的。因此，任務的通信開銷有時并不能忽略。在下一步的研究中將考慮任務之間的數據依賴和通信延遲，研究動態備份算法調度具有數據依賴的非獨立任務時的安全性和容錯性問題。另外，任務備份百分比k的取值僅在[36.8，100]變化， 建立更加精確的k值計算模型也是下一步的研究方向。

參考文獻：

［1］FOSTER I，KESSELMAN C.The grid 2:blueprint for a new computing infrastructure [M].2nd ed.金海，袁平鵬，石柯，譯.北京:電子工業出版社，2004：112.

[2]BRAUN T D，HENSGEN D，FREUND R，et al.A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems [J].Journal of Parallel and Distributed Computing，2001，61(6):810－837.

[3]DOGANA A，ZGNER F.Scheduling of a metatask with QoS requirements in heterogeneous computing systems [J].Journal of Parallel and Distributed Computing，2006，66(2):181196.

[4]羅紅，慕德俊，鄧智群，等.網格計算中任務調度研究綜述[J].計算機應用研究，2005，22(5):1619.

[5]SONG Shanshan，HWANG K，KWOK Y K.Riskresilient heuristics and genetic algorithms for securityassured grid Job scheduling [J].IEEE Trans on Computers，2006，55(6):703719.

[6]ABAWAJY J H.Faulttolerant scheduling policy for grid computing systems[C]//Proc of IEEE International Parallel and Distributed Processing Symposium.Los Alamitos: IEEE Computer Society Press，2004:238－244. [7]HWANG S，KESSELMAN C.A flexible framework for fault tolerance in the grid[J].Journal of Grid Computing，2003，1(3):251－272.

[8]石宣化，金海，羌衛中.通用網格容錯框架研究[J].華中科技大學學報:自然科學版，2006，34(7):42－45.

[9]AZZEDIN F，MAHESWARAN M.Integrating trust into grid resource management systems [C]//Proc of International Conference on Parallel Processing.Los Alamitos: IEEE Computer Society Press，2002:47－54.

[10]RESNICK P，ZECKHAUSER R，FRIEDMAN E，et al.Reputation systems[J].Communications of the ACM，2000，43(12):45－48.

[11]吳毓毅，賀也平.關于網格計算授權機制的研究[J].計算機應用研究，2005，22(8):81－83.

[12]SONG Shanshan，HWANG K.Trusted grid computing with security assurance and resource optimization [C]//Proc of the 17th International Conference on Parallel and Distributed Computing Systems.San Francisco:ISCA Press， 2004:110117.

[13]張偉哲，劉欣然，云曉春，等.信任驅動的網格作業調度算法[J].通信學報，2006，27(2):73－79.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”