成本限制下的網格工作流任務調度算法

摘要:在網格環境中，由于資源廣域分布、異構、動態且有多個管理域，考慮到網格環境中存在多個性能相同的網格資源，但其成本和有效度各不相同將會對工作流任務調度產生影響。該文針對DAG類型網格工作流任務調度，提出了一種LC(Limitation Cost)算法，在一定的成本限制下，選擇有效度較高的資源，從而提高了資源的利用率，減小了任務調度的失敗率。仿真實驗結果驗證了算法的有效性。

關鍵詞:網格計算;工作流;資源有效度

中圖分類號:TP393文獻標識碼:A文章編號:1009-3044(2010)03-683-03

Workflow Scheduling Algorithm on Grid under Cost Limitation

WANG Ming-jun， YU Jiong， LIU Jun-xiang， DENG Ding-lan

(School of Information Science and Engineering， Xinjiang University， Urumqi 830046， China)

Abstract: In the grid environment， as a result of the wide-area distribution， heterogeneous， dynamic of resources and there are multiple domains of management. Regarding that there are many grid resources with same performance， which will influence the workflow scheduling because of different reliability and service price. In this paper， aiming at the workflow scheduling of DAG-based workflow， we proposed one kind of LC (Limitation Cost) algorithm to choose reliability resources for higher degrees in the certain cost limitation， improving resource utilization， and reducing the failure rate of the task scheduling. The simulation shows the validity of the algorithm.

Key words: grid computing; workflow; resource reliability

1 概述

網格計算[1]是近年來得到快速發展的廣域網絡計算技術，它所要解決的問題是在動態多制度的虛擬組織之間協調資源共享與操作，這里的共享是指直接訪問計算機、軟件、數據和其他資源，而不單指文件交換。有向無環圖DAG(Directed Acyclic Graph)是工作流的一種常用描述方式，廣泛存在于E-science、E-business等網格應用領域[2]。工作流調度就是為任務選擇并分配合適的資源，并滿足不同的調度目標。然而，任務和資源的映射實質是一個復雜的優化問題，通常情況下多為NP-Hard問題[3]。現在關于網格工作流的調度算法有很多，也有很多的分類。本文通過市場機制合理地解決網格資源管理和調度問題，市場機制通過價格浮動反映資源供需狀況的動態變化，通過供需均衡實現資源優化，這種動態協調的資源管理機制適合網格資源的特性。為此，本文在Buyya博士提出的網格經濟資源管理模型的基礎上，提出了一種基于市場機制的成本和時間限制下的網格資源優化調度算法。

2 相關介紹

網格環境 中，可以將資源提供者視為生產者，將應用請求者(資源用戶)視為消費者，兩者構成經濟網格模型的兩個重要因素。計算經濟模型將經濟的概念引入網格資源管理中，它應用了市場經濟中的供求原則來對資源的所用者和使用者進行調節，以保證雙方均獲得最大利益。文獻[4]在Nimrod-G模型中提出的基于時間和成本限制下的優化調度算法(DBC)。完成時間優先調度算法、成本優先調度算法、限定時間成本保守時間最優化算法。以上三種算法從不同角度滿足了用戶需求，但是都未考慮資源有效度問題。文獻[2]中雖然考慮了資源的有效度，但是未涉及費用的優化問題。而本文針對上述問題，提出了一種基于成本限制(Limitation Cost)的調度算法。

3 基本概念與問題定義

網格中許多大型應用通常由多個任務相互協作完成，任務及任務間的約束關系可模型化為一個工作流，有向無環圖DAG是其常用的一種描述方式。令DAG圖記作G={V，E}，其中V={1，2…n}(|v|=n)表示應用中所有任務集合;是有向邊集合，表示任務間的控制或數據依賴關系，即對?坌(i，j)∈E，i執行完后j才可執行(i，j是結點編號，規定i

基于經濟的一般網格體系結構[3]為用戶提供了一致的訪問接口，因此對?坌i∈V，在其預測時間內都存在一個能夠完成該任務的候選服務集成為 的服務池，記作R(i)。l(i)是R(i)的集合長度，表示能完成任務 的服務個數;Sik表示能完成任務 的第k個服務;(cik，pik)描述為在任務 的預測時間內Sik的執行成本和有效度[2]，則R(i)={Sik ={( cik ，pik )}，1≤k≤l(i)}。表1給出了圖1中各個任務的服務池實例。

對于工作流有一個最低執行成本mcn，但是并不能保證完成工作流的有效度較高，這也是符合市場機制規律。用戶為獲得性能較好的資源，必須付出的較高的費用cn。其費用必須滿足(mcn≤cn)才可成功執行。調度目標就是在用戶給定的cn下，為工作流中各任務分配合適的資源，使工作流所需資源的有效度最高，得到性能較高的資源，形式化描述如下

max p(1)

st.

mcn≤cn(2)

其中p為調度工作流時整個資源的有效度，式(1)表示最大化資源有效度;式(2)滿足費用約束。

因此，目標函數(1)取最大值的關鍵在于將Δc(其中Δc=cn–mcn)合理的分配到任務所在的每一個任務當中選擇費用較高的資源，從而獲得有效度較高的資源，這種動態協調的資源管理機制適合網格資源的特性。

定義1 給定圖G={V，E}，對?坌i∈V，從其服務池中選擇費用最低的服務，總費用下限

由定義1可知，mcn是工作流完成所有任務所需的最小費用，因此，用戶給定的費用cn必須大于或等于mcn才能保證工作流完成。

定義2費用浮差Δc定義為用戶給定費用cn和最小完工費用之差，即

將Δc平均分配到執行各個任務的資源中，從而選擇有效度較高的資源。

定義3平均浮差Δc定義為費用浮差的平均值，即

其中虛任務除外，這樣每個結點分配到相同的平均浮差Δc。

LC算法的具體執行過程如下:

Begin

1為所有任務查找相應服務資源池R(i)， i∈V;

2由公式(3)計算完成工作流的最小完工費用mcn;

3提示用戶在有效的費用范圍(mc≤c)內輸入cn;

4當mc≥c時，返回步驟2;否則轉步驟5;

5由公式(4)，(5)計算費用浮差Δc和平均浮差ci并平均分配到各個結點;

6獲取就緒任務隊列RL;

7若RL不空，對就緒任務從其服務池中選擇合適的資源。否則轉步驟9;

8發送控制或數據信息到分配的服務資源并啟動執行;

9等待任務完成事件;

10 若還有任務未被調度，轉步驟6;否則轉步驟11;

11 計算工作流的有效度;

12 輸出結果;

End

該算法中步驟2，6的時間復雜度最差情況下為o(n2);而步驟7到步驟12的時間復雜度為o(n*len(Rl)*M)[6]，其中n是工作流中任務總數，len(Rl)是就緒隊列長度，M=max{l(i)}是所有任務的最大服務池長度。因此整個算法的時間復雜度最大不超過o(n2*M)。資源有效度的計算文獻[6]中有提及本文不在贅述。

4 實例說明

為說明LC的求解過程，下面用實例說明算法的求解過程。以圖1給出的工作流應用為例，設用戶給定的費用c=600。各個任務從表1給出的服務池中選擇執行成本最低的服務，其下界完成成本mc=495，可計算出最低有效度為mp=72.1%，費用浮差Δc=105，平均費用浮差Δc=7.5，將其平均分配到每個結點中，其有效度為79.3%。有效度提高了7.2%。而文獻[5]中提到的GBRR算法可計算出有效度為75.4%。比最低有效度提高了3.3%。LC算法比GBRR算法在有效度上提高了0.039個百分點。

5 實驗仿真與結果分析

為比較LC算法和GBRR算法，對大量不同DAG結構的工作流應用進行模擬測試。隨機DAG圖生成器需設置任務數V和任務最大初度out_degree等參數，通過組合不同參數的取值生成不同特征的DAG圖，實驗中結點數|V|={10，20，30，40，50，60，70，80，90，100}，其中cn為用戶給定相應任務數的執行成本，圖的最大初度out_degree={1，3，5，V}。在網格環境中，能在相同時間內完成某個任務有若干候選資源，這些資源信息可從GIS (Grid Information Service)中的RIS(Resource Info Service)獲得。從而可以得到每個任務在其預測執行時間內的資源有效度。每種參數組合產生10種不同實例。表2是兩個算法在不同任務數量下工作流執行的資源有效度情況。

從表2列出的數據可看出，LC算法有效度比GBRR算法計算出的有效度平均高出4.81%。

從整體來說隨著任務數的增加，各算法計算出的有效度有所下降，這比較符合實際情況，因為隨著執行各任務的資源數增多，其不確定因素也增加，從而降低了整個資源的有效度。如何解決這類問題也是本文以后研究的方向。

但是對于相同的任務數來說，對于用戶給出不同的執行成本進行模擬測試比較兩種算法的性能。隨機DAG圖生成器設置任務數|v|=200，圖的最大初度out_degree=3。仿真結果如圖2。

從圖2可以看出，相對GBRR算法LC算法能通過合理地調度，將任務分配到有效度較高的資源上執行，使整個資源的有效度提高4.45%。隨著執行成本的提高資源有效度不在提高，因為整個資源有效度有一個執行上限。當達到上限值時有效度不再增加。

6 結束語

本文結合網格系統分布、異構和動態的特點，充分考慮用戶QoS要求和時限要求的條件下，針對如何在這種復雜的環境下快速進行獨立任務調度的問題，提出了一種改進的LC算法。該算法能夠更好的滿足不同用戶的QoS需求和平衡資源的負載情況。仿真實驗證明LC算法能夠根據用戶的QoS需求，靈活有效的為用戶動態分配網格資源，降低了調度任務的失效率，提高了網格資源的利用率。

參考文獻:

[1] I. Foster，C. Kesselman，S. Tuecke.The Anatomy of the Grid:Enabling Scalable Virtual Organizations[J].International J.Supercomputer Application，2001，15(3):200-222.

[2] 田國忠，于炯.基于資源有效度的網格工作流調度算法[J].計算機工程，2008，34(11):80-82.

[3] Buyya R，Abramson D，Giddy J.High Ningrod/G: architecture for a Resource Management and Scheduling System in a Global Computational Grid[C].Proceedings of the 4th International Conference Exhibition High Performance Computing in the Asia Pacific Region，2000:283-289.

[4] Buyya R，Murshed M，Abramson.D.A Deadline and Budget Constrained Cost-Time Optimization Algorithm for Scheduling Task Farming Applications on Global Grids[C].Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications(PDPTA)，2002.

[5] Yu J，Buyya R.Taxonomy of scientific workflow systems for Grid computing[C].SIGMOD RECORD 2005，34(3):44-49.

[6] Blythe J.，Jain S.，Deelman E.et al.Task Scheduling Strategies for Workflow-based Applications in Grids[C].IEEE International Symposium on Cluster Computing and Grid，Cardiff，Wales，UK，2005，Piscataway，NJ，USA:IEEE Computer Society Press，2005:759-767.