基于QoS約束的網格任務調度算法

王 浩，李 飛

(成都信息工程學院網絡工程學院，成都 610225)

引言

網格［1］環境下的任務調度問題是網格技術中的一個基本問題。由于網格環境中的資源所具有的異構性、動態性和分布性等特點，使得如何對任務進行調度以期滿足各方面(系統用戶、資源提供者、系統管理者等)的需求成為一個極具挑戰性的問題。網格任務調度［2］的實質是將其環境中的m個需要調度的任務合理的分配到n個系統可用資源主機上去執行。由于現實環境中的網格系統規模一般都比較大，這樣就決定了m和n都比較大，因此問題則轉變成為一個NP難問題，即需要在有限時間內，在2n個資源集合中尋找出最優任務-資源匹配方案，然而這又是不可能實現的，因此，一般都采用啟發式任務調度算法獲取近似最優配對。

目前國內外所研究的調度算法一般分為在線模式(on-linemode)和批處理(batch mode)模式兩類。在線模式在任務到達的第一時間執行映射。批處理模式則需將任務收集到一定數量(系統設定的一個參數數值)，等待映射事件發生后才開始映射所收集的任務。

1 相關工作

本文主要研究的是批處理模式下的啟發式任務調度算法，并且已假定各任務之間相互獨立，各任務在不同的資源上運行的預測執行時間可知。目前，經典的批處理模式下的調度算法有:Max-min［3］算法、Minmin［3-6］算 法、GA［7-8］算 法、Sufferage［9-10］算 法 和SA［11］(Simulated Annealing)等。Max-min算法是基于MCT(Minimum Completion Time，最小完成時間)的改進算法，算法選取最早完成時間最大的任務進行優先調度。GA算法與SA算法，其復雜度一般認為都比較高。對于QoS約束［12-14］下的任務調度算法，國內外已有不少研究成果，其都考慮了多QoS約束的問題，但是對于大量的QoS約束(來自于系統用戶、資源提供者、系統管理者等方面的)并未進行細分討論;并且考慮的QoS約束一般都比較少，其對新約束條件的擴展性也比較差。

Min-min算法也是基于MCT的改進算法，算法優先選擇最早完成時間最小的任務進行調度，其以最快的速度減少任務調度隊列中的待調度任務，以縮短任務的完成時間。但是Min-min算法同時也是一種貪心算法，僅追求任務完成時間最早的局部最優解，使得系統負載不均衡，導致時間跨度值變大。尤其當任務的執行時間差異較大的時候，產生的負面效應就越突出。任務的損失度值反映出任務在資源主機上的執行完成時間差異，反映了環境的異構性。Sufferage算法的時間跨度較小并且系統負載基本均衡，算法在減小任務調度跨度上的性能優于其它批處理算法，其表現出良好的綜合性能;而對于具有QoS需求的任務的情況，基本欠缺考慮，并且任務本身也可能被多次進行分配。

在對多種異構環境下的啟發式任務調度算法進行了研究、分析對比以后，結合Min-min算法和Sufferage算法的思想，提出了基于任務QoS約束和任務調度損失度的最小最早完成時間算法(QoSDimensions and Sufferage Min-min，QDSM)。本文將任務QoS約束與任務損失度引入Min-min算法中，在綜合權衡任務最早完成時間、任務QoS約束與調度損失的基礎上進行任務調度，使得算法更加適應于異構環境。仿真測試表明，QDSM算法具有較好的綜合性能。

2 QDSM算法

2.1 參數定義

為了更好的說明QDSM算法，本文使用以下一般性定義:

定義1 集合T={t1，t2，…，tm}包含m個相互獨立的任務。

定義2 集合H={h1，h2，…，hn}包含n個可用資源。

定義3 任務集合T所包含的m個任務在可用資源集合H所包含的n個主機上的預測執行時間(Expected Time to Compute，ETC)結果為m×n的矩陣:

元素eij表示待執行任務ti在可用主機資源hj上的預測執行時間。

定義4 m個待執行任務在n個可用資源上面的預測最小完成時間MCT結果為m×n的矩陣:

元素cij表示待執行任務ti在可用主機hj上的預測最小完成時間。

定義5 目前研究的用戶QoS約束，考慮了4個維度:安全性、費用、成功率以及穩定性，映射為m×4的用戶QoS約束(User QoSDimensions，UQD)矩陣:

定義6 集合V為待調度分配任務集合，其中，所有元素均屬于T并且尚未被分配。

定義7 第i個任務ti的損失度(sufferage)為任務的最優最早完成時間與次優最早完成時間之差。即:

m個任務的suffer值構成了維度為m的向量S={s1，s2，…，sm}。

定義8 m×k維矩陣MT，用于儲存每個任務在各個資源主機上的前k個最小執行時間，其中，元素mtij表示任務ti的最小完成時間，參數k為可調節參數，取值范圍為［1，n］。

2.2 算法描述

根據前述參數定義，首先對UQD矩陣進行歸一化處理，計算權重，選取權重最大者存入向量Q;分別選取待調度任務中的最小執行時間任務與suffer值最大的任務，分別進行標記;計算權衡系數α，根據權衡系數，選取相應的任務進行調度，同時更新MCT矩陣。

對于用戶QoS約束矩陣UQD和預測執行時間矩陣ECT均已知，并已初始化;MCT矩陣和集合V均為空。算法的詳細步驟如下:

(1)輸入矩陣ECT和UQD。

(2)對矩陣MCT和集合V進行初始化，其中，MCT=ECT，V=T，對矩陣UQD進行歸一化處理。

(3)在矩陣ECT中，查找每個任務的最小執行時間，并選取前k個元素存入矩陣MT。

(4)當V非空時，循環執行步驟(5)～步驟(9)。

(5)根據MCT矩陣，計算任務集合V的suffer值，并從中找出任務的最大suffer值，記為sa，其對應的任務ta∈V。

(6)在矩陣MT中，查找對應于任務集合V的最大執行時間任務，記為mtb，其對應的任務tb∈V，suffer值記為sb。

(7)對歸一化后的UQD矩陣，計算任務的各維QoS約束在待調度任務中所占權重，選取所占權重最大者存入向量Q={mq1，mq2，…，mqm}。

(8)求解權衡系數α，

(9)如果(sa≥(α×sb))

將任務ta分配到資源主機ra上執行，并依據ta的執行時間更新MCT矩陣，從集合V中刪除任務ta，否則，將任務tb分配到資源主機rb上執行，并依據tb的執行時間更新MCT矩陣，從集合V中刪除任務tb。

3 性能分析

在多任務、多資源的網格模擬環境GridSim［15］中使用隨機產生的ECT和UQD矩陣作為仿真輸入，分別針對Min-min算法、Sufferage算法、SMM算法和QDSM算法進行任務調度仿真，采集模擬數據，分析每個算法的性能，針對性的驗證了QDSM算法在最優跨度、資源平均利用率等方面的性能。其中，資源平均利用率按下式計算。

實驗使用統計數據均值對算法性能進行分析，分成2組進行實驗仿真驗證。

3.1 時間跨度

圖1為資源數為10時，在不同任務數下進行的仿真實驗得到的makespan均值，資源數與任務數分別按10∶100，10∶200和10∶300進行匹配。

圖1 makespan均值

分析圖1數據可知，Sufferage算法、SMM算法和QDSM算法的makespan均值均少于Min-min算法。隨著任務數量的增加，QDSM算法的性能略有下降，但與Min-min算法和SMM算法相比仍有較好的性能。

3.2 資源平均利用率

圖2所示為，資源數為10時，在不同任務數下進行的仿真實驗得到的資源平均利用率。

由圖2分析可知，QDSM算法使得系統的資源平均利用率比SMM算法略有提升，較Min-min算法和Sufferage算法都表現出較好的性能。

圖2 資源平均利用率

4 結束語

本文在研究了多種啟發式網格任務調度算法以后，提出了適合于異構環境的獨立任務調度算法:基于任務QoS約束和任務調度損失度的最小最早完成時間算法(QoSDimensions and Sufferage Min-min，QDSM)。所提算法克服了Min-min算法的局限性，更適應于異構環境下的任務調度。然而，對于網格中資源的異常處理，需要分析異常產生的原因，根據原因有針對性的提出解決方案;對于任務約束的動態可擴展性，則需要對QoS約束、資源系統等各方面進行深入的分析與研究。

［1］都志輝，陳 渝，劉 鵬.網格計算［M］.北京：清華大學出版社，2002.

［2］王相林，張善卿，王景麗.網格計算核心技術［M］.北京：清華大學出版社，2006.

［3］Chauhan Sameer Singh，Joshi R C.A weighted mean time Min-Min Max-Min selective scheduling strategy for Independent Tasks on Grid［C］.//Deepak Garg.Proceeding of IACC 2010，Patiala，India，February，19-20，2010：4-9.

［4］Braun T D，Siegel H J，Beck N.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.

［5］周洋，蔣昌俊，方鈺.異構環境下的獨立任務調度算法的研究［J］.計算機科學，2008，35(8)：90-92.

［6］莫 贊，謝 娜，賈功祥，等.基于多QoS需求驅動的網格資源調度研究［J］.計算機應用研究，2012，29(10)：3904-3907.

［7］Braun T D，Siegel H J，Maciejewski A.Static mapping heuristics for tasks with dependencies，priorities，deadlines，and multiple versions in heterogeneous environments［C］.Ibarra O H，Olariu S，Nakano K，et al.Proceedings of the 16thInt’l Parallel and Distributed Processing Symposium，F.L.，Florida，USA，April，15-19，2002：78-85.

［8］朱 海，王宇平.多目標約束的網格任務安全調度模型及算法研究［J］.電子與信息學報，2010，32(4)：988-992.

［9］He Xiaoshan，Sun Xianhe，von Laszewskig G.QoS Guided Min-min Heuristic for Grid Task Scheduling［J］.The Journal of Computer Science and Technology，2003，18(4)：442-451.

［10］李 炯，盧顯良，董 仕.基于GridSim模擬器的網格資源調度算法研究［J］.計算機科學，2008，35(8)：95-97.

［11］薛勝軍，徐鈞磊，刑國穩.一種用于網格任務調度的退火進化算法［J］.計算機應用研究，2011，28(11)：4049-4052.

［12］Dogan A，Ozguner F.On QoS-based scheduling of a meta-task with multiple QoS demands in heterogeneous computing［C］.Ibarra O H，Olariu S，Nakano K，et al.Proceedings of the 16thInt'l Parallel and Distributed Processing Symposium，F.L.，Florida，USA，April1，5-19，2002：50-55.

［13］Chauhan Sameer Singh，JoshiR C.QoSguided heuristic Algorithms for grid task scheduling［J］.International Journal of Computer Applications，2010，2(9)：24-31.

［14］Castillo C，Rouskas G N，Harfoush K.Online algorithms for advance resource reservations［J］.Journal of Parallel and Distributed Computing，2011，71(7)：963-973.

［15］Buyya R，MURSHED M.GridSim：a toolkit for the modeling and simulation of distributed resourcemanagement and scheduling for grid computing［J］.Concurrency and Computation：Practice and Experience，2002，14(13)：1175-1220.