網格工作流中一種擴展的ＱＤ－Ｓｕｆｆｅｒａｇｅ調度算法
2008-01-01 00:00:00胡志剛陳俊
計算機應用研究 2008年5期
摘要：首先在分析工作流執行模型的基礎上，提出了工作流就緒隊列發現算法；并在QD－Sufferage算法的基礎上，提出了一種擴展的QD－Sufferage網格工作流調度算法，并通過試驗驗證了該算法優于傳統的調度算法。
關鍵詞：工作流；調度；擴展拓撲排序；Extended QD－Sufferage算法
中圖分類號：TP393文獻標志碼：A
文章編號：1001-3695(2008)05-1504-03
0引言
網格工作流技術已成為網格計算領域的研究熱點。網格工作流是指：在網格環境下，利用網格提供的資源和服務，通過業務流程的全部或部分自動化，實現組織成員間的協調工作以達到業務的整體目標[1]。
在網格服務組成的工作流中，網格服務的調度方案是指服務與資源的映射關系，這種調度往往是NP完全問題。在已有的網格資源調度算法中，主要側重解決網格作業與網格資源的調度問題。其中Buyya等人[2]提出基于經濟學模型的優化調度模型，其目的是在資源提供者與使用者之間建立一種交易，以盡可能低的費用滿足資源使用者進行任務計算的最低要求；文獻[3]提出了一種在GrADS中基于開銷等級值和組件性能模型的工作流任務調度算法，在獲得任務在所有資源等級值的基礎上，從三種啟發式調度算法中擇優選擇任務進行調度分配。以上這些調度方案未能從任務和資源的服務質量、任務的截止時間等方面進行考慮，文獻[4]提出了一種面向Deadline約束的網格QoS任務調度，但資源的利用存在浪費。本文在文獻[4]的基礎上，對QD－Sufferage算法進行了擴展，進一步提出一種擴展的QD－Sufferage算法。實驗結果表明，后者結果較前者在任務接受率和makespan性能方面都有進一步提高。
1網格工作流及其調度問題
大多數重要的網格應用都已采取工作流應用來實現，如在網格上的LIGO脈沖搜索、網格上的圖像處理等。本文所討論的網格工作流應用是由一組約束關系（如數據間的依賴關系、控制關系等）的服務組合而成的。它們形成了一個復雜的工作流，可以用一個有向無環圖（DAG）表示。該圖是拓撲有序的。其中：節點表示服務；弧表示服務之間的約束關系；方向表示服務依賴。對于圖中的m個節點S＝{s1，s2，…，sm}， si為第i個服務，它既可以是原子服務，也可以是一個復合服務。本文為討論方便，假定每個服務都是原子服務。
1．1工作流執行模型及分析
工作流調度是對當前已經就緒的服務調度。所謂就緒的服務是指其所有前驅服務都已經執行完畢。整個工作流的執行可以看成就緒隊列的執行過程。其執行過程[5]可以描述如圖1所示。
它由兩大部分構成：左邊是就緒服務監控器，負責在工作流的調度過程中監控每個服務的執行過程，收到服務完成事件后更新就緒服務隊列；右邊是服務調度器，對就緒隊列中的服務按照某種調度算法進行資源的匹配和發現，啟動執行。
1．2工作流就緒隊列發現算法——擴展拓撲排序
網格工作流應用可以用DAG圖表示，如圖2所示。其中：節點表示服務；弧表示服務之間的約束關系；方向表示服務依賴。
用一種擴展拓撲排序方法來找出其整個用DAG圖表示的網格工作流應用的就緒隊列。
算法描述如下：
a)在有向頭中選擇所有沒有前驅的頂點，組成一個集合Ready(i)；(i=0，i++)。
b)從圖中刪除該頂點和所有以它為尾的弧，回到a)繼續執行。
重復上述步驟，直至全部頂點均已輸出，或者當前圖中不存在無前驅的頂點為止。再將所有無前驅的頂點組合成一個集合。
如圖2所示，根據擴展拓撲排序算法可得到{(S1，S2，S3)；（S4，S6）；（S5）；（S7，S8）}四個就緒隊列。每一就緒隊列Ready(i)串行執行，就緒隊列中的服務Si可串行或并行執行，視資源情況而定。
綜上所述，網格服務工作流的執行過程就是對網格就緒隊列的執行過程，通過擴展拓撲排序將一工作流應用映射成一組子服務的調度后，再分別對每一個子服務Ready(i)實行調度算法。問題就轉變為：產生一個從Ready(i)到Resource的映射。Ready(i)表示一個子服務應用，也就是上面的一個（Si，S(i+1)，S(i+2)，…，)(i≥1)。Resource表示可獲得的網格資源的集合， Resource＝{R1，R2，…，Rm}。而調度算法的目的是使目標函數f=min (ni=1Exec(Ready(i)))達到最小值。其中Exec(Ready(i))表示就緒隊列的執行時間。
2網格工作流中一種擴展的QD－Sufferage調度算法
為了適應用戶提交任務的需求，在基于QoS優先級分組[4]改進思想的任務調度基礎上引入任務的Deadline 約束。 同時考慮在傳統的以Deadline為導向的調度策略當中，如果單純地根據任務Deadline的緊迫程度進行調度，則可能出現：a)先調度的任務完成時間較大，會使得makespan性能下降；b)先調度的任務QoS優先級較低，可能會導致搶占有高QoS優先級的任務。綜合的改進思想是：在調度的過程中不僅要考慮任務對資源的QoS 需求，而且要將用戶對任務的截止時間需求考慮進去，同時在此基礎上調度完成時間較小的任務，通過對其進行加權綜合處理來決定任務的調度次序。 由于各個因素之間是一個折中的關系，其間的權值是根據具體應用要求來決定的。
引入Deadline約束的網格任務調度系統模型及算法流程如下：
Deadline（ti）表示任務ti所對應的Deadline值；Last(ti，hj)表示任務ti在主機hj上的最晚開始時間；Span(ti，hj)表示任務ti在主機hj當前負載下距離相應的最晚開始時間的跨度。該值在調度過程中能正確反映出任務的緊迫程度。QDWeight表示QoS優先級分組與任務Deadline之間的權值；SCWeight表示任務的Deadline約束值與任務的完成時間之間的權值。
3試驗及分析
本文參照文獻[6]中的實驗方法編寫了一個模擬程序，程序分為兩部分：a)任務提交部分，負責模擬泊松分布提交任務；b)任務分配部分，負責按照給定的算法調度任務。為使實驗簡單，假定提交的任務都是經過工作流處理過的就緒隊列Ready(i)，并且在本實驗中，只考慮Deadline一個QoS參數。筆者在b）中分別運行了以Deadline為導向的調度算法、QD－Sufferage調度算法和擴展QD－Sufferage調度算法。
首先比較了三種算法分別在以下四種環境中運行的結果：a）沒有Deadline的任務；b）25%的任務擁有Deadline，其他任務對Deadline沒有要求；c）兩種任務各為50%；d）兩種任務分別為25%、75%。實驗進行100次獨立的調度仿真，獲得100次仿真的平均網格任務接受率（圖3）和makespan性能參數（圖4）。調度程序每隔20 s執行一次。然后比較了以情況c）為背景，調度周期分別為10 s、20 s、30 s時三種算法的運行結果(圖5)。
從圖3可以看出，隨著任務序列當中Deadline任務百分比的不斷增大，擴展的QD－Sufferage的接受任務數目與以Deadline為導向的策略接受任務數目很接近，優于QD－Sufferage算法。從圖4可以看出，三種算法的makespan參數都隨著Deadline任務的增多而不斷增大，但顯然擴展的QD－Sufferage的makespan性能要始終優于其他兩種的性能，并且其增長斜率要比其他兩種低。
由圖5可以看出，擴展的QD－Sufferage算法相對于QD－Sufferage算法能夠更充分地利用計算資源。當調度周期提高到20 s時，擴展算法運行結果有明顯優勢。這是因為調度周期時間過長，使得許多主機在很多時間內處于空閑狀態，而擴展的QD－Sufferage算法能有效地利用這些空閑時間。因此，相對于QD－Sufferage算法，空閑時間越多，擴展的QD－Sufferage算法的性能提高幅度就越大。
4結束語
本文針對網格服務工作流調度問題，首先提出了就緒隊列發現算法；然后在此基礎上，提出了擴展的QD－Sufferage算法來對就緒隊列進行任務調度。實驗結果表明，擴展算法要比原算法性能高，對同一批任務進行調度，可獲得比原算法更短的最大完成時間。
在本文中，為簡化研究，筆者只考慮任務優先級和Deadline約束。在未來的工作中，將研究QoS其他方面對網格任務調度的影響。此外，網格環境的動態性將很大程度地影響網格工作流任務調度算法的實施。因此，在下一步工作中，將針對復雜的網格工作流應用，研究網格工作流的動態調度問題。
參考文獻：
［1］高蓓蓓，葛瑋，董云衛.網格工作流研究[J].計算機技術與發展，2006，16(1): 80-86.
[2]BUYYA R，ABRAMSON D，GIDDY J.An economy driven recourse management architecture for global computational power grids[C]//Proc of Int’l Conf on Parallel and Distributed Processing Techniques and Applications.[S.l.]:Las Vegas，2000.
[3] MANDAL A，DASGUPTA A，KENNEDY K.Scheduling workflow applicati:ons in GrADS[C]//Proc of IEEE International Symposium on Cluster Computing and the Grid.[S.l.]:IEEE，2004:790－797.
[4] DONG Fang，LUO Jun－zhou，GAO Li－sha.A grid task scheduling algorithm based on QoS priority grouping[C]//Proc of the 5th International Conference on Grid and Cooperative Computing.2006.
[5]SINGH G，KESSELMAN C，DEELMAN E.Optimizing grid－based workflow execution，CS 05-851[R].Los Angeles:Informalion Sciences Institute，University of Southern California，2005.
[6]HE Xiao－shan，SUN Xian－he，LASZEWSKI G von.QoS guided min－min heuristic for grid task scheduling[J].Journal of Computer Science and Technology，2003，18(4):442-451.
“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”
