基于QoS約束的網(wǎng)格任務(wù)調(diào)度算法

王 浩，李 飛

(成都信息工程學(xué)院網(wǎng)絡(luò)工程學(xué)院，成都 610225)

引言

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

目前國(guó)內(nèi)外所研究的調(diào)度算法一般分為在線模式(on-linemode)和批處理(batch mode)模式兩類。在線模式在任務(wù)到達(dá)的第一時(shí)間執(zhí)行映射。批處理模式則需將任務(wù)收集到一定數(shù)量(系統(tǒng)設(shè)定的一個(gè)參數(shù)數(shù)值)，等待映射事件發(fā)生后才開(kāi)始映射所收集的任務(wù)。

1 相關(guān)工作

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

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

在對(duì)多種異構(gòu)環(huán)境下的啟發(fā)式任務(wù)調(diào)度算法進(jìn)行了研究、分析對(duì)比以后，結(jié)合Min-min算法和Sufferage算法的思想，提出了基于任務(wù)QoS約束和任務(wù)調(diào)度損失度的最小最早完成時(shí)間算法(QoSDimensions and Sufferage Min-min，QDSM)。本文將任務(wù)QoS約束與任務(wù)損失度引入Min-min算法中，在綜合權(quán)衡任務(wù)最早完成時(shí)間、任務(wù)QoS約束與調(diào)度損失的基礎(chǔ)上進(jìn)行任務(wù)調(diào)度，使得算法更加適應(yīng)于異構(gòu)環(huán)境。仿真測(cè)試表明，QDSM算法具有較好的綜合性能。

2 QDSM算法

2.1 參數(shù)定義

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

定義1 集合T={t1，t2，…，tm}包含m個(gè)相互獨(dú)立的任務(wù)。

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

定義3 任務(wù)集合T所包含的m個(gè)任務(wù)在可用資源集合H所包含的n個(gè)主機(jī)上的預(yù)測(cè)執(zhí)行時(shí)間(Expected Time to Compute，ETC)結(jié)果為m×n的矩陣:

元素eij表示待執(zhí)行任務(wù)ti在可用主機(jī)資源hj上的預(yù)測(cè)執(zhí)行時(shí)間。

定義4 m個(gè)待執(zhí)行任務(wù)在n個(gè)可用資源上面的預(yù)測(cè)最小完成時(shí)間MCT結(jié)果為m×n的矩陣:

元素cij表示待執(zhí)行任務(wù)ti在可用主機(jī)hj上的預(yù)測(cè)最小完成時(shí)間。

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

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

定義7 第i個(gè)任務(wù)ti的損失度(sufferage)為任務(wù)的最優(yōu)最早完成時(shí)間與次優(yōu)最早完成時(shí)間之差。即:

m個(gè)任務(wù)的suffer值構(gòu)成了維度為m的向量S={s1，s2，…，sm}。

定義8 m×k維矩陣MT，用于儲(chǔ)存每個(gè)任務(wù)在各個(gè)資源主機(jī)上的前k個(gè)最小執(zhí)行時(shí)間，其中，元素mtij表示任務(wù)ti的最小完成時(shí)間，參數(shù)k為可調(diào)節(jié)參數(shù)，取值范圍為［1，n］。

2.2 算法描述

根據(jù)前述參數(shù)定義，首先對(duì)UQD矩陣進(jìn)行歸一化處理，計(jì)算權(quán)重，選取權(quán)重最大者存入向量Q;分別選取待調(diào)度任務(wù)中的最小執(zhí)行時(shí)間任務(wù)與suffer值最大的任務(wù)，分別進(jìn)行標(biāo)記;計(jì)算權(quán)衡系數(shù)α，根據(jù)權(quán)衡系數(shù)，選取相應(yīng)的任務(wù)進(jìn)行調(diào)度，同時(shí)更新MCT矩陣。

對(duì)于用戶QoS約束矩陣UQD和預(yù)測(cè)執(zhí)行時(shí)間矩陣ECT均已知，并已初始化;MCT矩陣和集合V均為空。算法的詳細(xì)步驟如下:

(1)輸入矩陣ECT和UQD。

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

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

(4)當(dāng)V非空時(shí)，循環(huán)執(zhí)行步驟(5)～步驟(9)。

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

(6)在矩陣MT中，查找對(duì)應(yīng)于任務(wù)集合V的最大執(zhí)行時(shí)間任務(wù)，記為mtb，其對(duì)應(yīng)的任務(wù)tb∈V，suffer值記為sb。

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

(8)求解權(quán)衡系數(shù)α，

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

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

3 性能分析

在多任務(wù)、多資源的網(wǎng)格模擬環(huán)境GridSim［15］中使用隨機(jī)產(chǎn)生的ECT和UQD矩陣作為仿真輸入，分別針對(duì)Min-min算法、Sufferage算法、SMM算法和QDSM算法進(jìn)行任務(wù)調(diào)度仿真，采集模擬數(shù)據(jù)，分析每個(gè)算法的性能，針對(duì)性的驗(yàn)證了QDSM算法在最優(yōu)跨度、資源平均利用率等方面的性能。其中，資源平均利用率按下式計(jì)算。

實(shí)驗(yàn)使用統(tǒng)計(jì)數(shù)據(jù)均值對(duì)算法性能進(jìn)行分析，分成2組進(jìn)行實(shí)驗(yàn)仿真驗(yàn)證。

3.1 時(shí)間跨度

圖1為資源數(shù)為10時(shí)，在不同任務(wù)數(shù)下進(jìn)行的仿真實(shí)驗(yàn)得到的makespan均值，資源數(shù)與任務(wù)數(shù)分別按10∶100，10∶200和10∶300進(jìn)行匹配。

圖1 makespan均值

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

3.2 資源平均利用率

圖2所示為，資源數(shù)為10時(shí)，在不同任務(wù)數(shù)下進(jìn)行的仿真實(shí)驗(yàn)得到的資源平均利用率。

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

圖2 資源平均利用率

4 結(jié)束語(yǔ)

本文在研究了多種啟發(fā)式網(wǎng)格任務(wù)調(diào)度算法以后，提出了適合于異構(gòu)環(huán)境的獨(dú)立任務(wù)調(diào)度算法:基于任務(wù)QoS約束和任務(wù)調(diào)度損失度的最小最早完成時(shí)間算法(QoSDimensions and Sufferage Min-min，QDSM)。所提算法克服了Min-min算法的局限性，更適應(yīng)于異構(gòu)環(huán)境下的任務(wù)調(diào)度。然而，對(duì)于網(wǎng)格中資源的異常處理，需要分析異常產(chǎn)生的原因，根據(jù)原因有針對(duì)性的提出解決方案;對(duì)于任務(wù)約束的動(dòng)態(tài)可擴(kuò)展性，則需要對(duì)QoS約束、資源系統(tǒng)等各方面進(jìn)行深入的分析與研究。

［1］都志輝，陳 渝，劉 鵬.網(wǎng)格計(jì)算［M］.北京：清華大學(xué)出版社，2002.

［2］王相林，張善卿，王景麗.網(wǎng)格計(jì)算核心技術(shù)［M］.北京：清華大學(xué)出版社，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，F(xiàn)ebruary，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］周洋，蔣昌俊，方鈺.異構(gòu)環(huán)境下的獨(dú)立任務(wù)調(diào)度算法的研究［J］.計(jì)算機(jī)科學(xué)，2008，35(8)：90-92.

［6］莫 贊，謝 娜，賈功祥，等.基于多QoS需求驅(qū)動(dòng)的網(wǎng)格資源調(diào)度研究［J］.計(jì)算機(jī)應(yīng)用研究，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(xiàn).L.，F(xiàn)lorida，USA，April，15-19，2002：78-85.

［8］朱 海，王宇平.多目標(biāo)約束的網(wǎng)格任務(wù)安全調(diào)度模型及算法研究［J］.電子與信息學(xué)報(bào)，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模擬器的網(wǎng)格資源調(diào)度算法研究［J］.計(jì)算機(jī)科學(xué)，2008，35(8)：95-97.

［11］薛勝軍，徐鈞磊，刑國(guó)穩(wěn).一種用于網(wǎng)格任務(wù)調(diào)度的退火進(jìn)化算法［J］.計(jì)算機(jī)應(yīng)用研究，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(xiàn).L.，F(xiàn)lorida，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.