李 飛，王 浩，張 琨，牛京武

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

0 引 言

網(wǎng)格［1］環(huán)境下的任務(wù)調(diào)度問題是網(wǎng)格技術(shù)中的基礎(chǔ)性問題。由于網(wǎng)格環(huán)境中的資源所特有的分布性、異構(gòu)性和動態(tài)性等特點，使得對任務(wù)如何進行調(diào)度安排并以期滿足各方面 （資源提供者、系統(tǒng)用戶、系統(tǒng)管理者等等）的需求成為一個極具挑戰(zhàn)性的問題。

網(wǎng)格任務(wù)調(diào)度［2－3］的目的是在網(wǎng)格異構(gòu)環(huán)境中，將m個待調(diào)度的任務(wù)分配到n個可用資源上去，并且使得任務(wù)完成總時間 （makespan）盡可能的小。對于實際的網(wǎng)格環(huán)境，其m和n一般都不會太小，因此，網(wǎng)格任務(wù)調(diào)度實際就是一個NP問題。對任務(wù)集合實現(xiàn)最優(yōu)調(diào)度，成為網(wǎng)格任務(wù)調(diào)度的首要目標(biāo)。具體的目標(biāo)包括負載均衡、時間跨度、安全度、費用、穩(wěn)定性、成功率等。負載均衡是影響網(wǎng)格中各節(jié)點之間進行協(xié)同工作最為重要的因素之一。時間跨度是指從任務(wù)等待調(diào)度開始到所有任務(wù)運行完畢所經(jīng)歷的時間，其值越小，該調(diào)度策略越好。當(dāng)用戶向網(wǎng)格系統(tǒng)提交自己的任務(wù)時，最大的愿望是：系統(tǒng)在滿足自己任務(wù)的多QoS約束條件下，盡可能快的完成自己的任務(wù)，并且相關(guān)費用越低越好。如何提高網(wǎng)格系統(tǒng)的性能，并保證用戶任務(wù)在調(diào)度過程中的服務(wù)質(zhì)量，正是網(wǎng)格調(diào)度算法所要解決的問題。

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

1 相關(guān)工作

對于網(wǎng)格環(huán)境下的任務(wù)調(diào)度已經(jīng)有不少研究成果，本文側(cè)重研究了批處理模式下的數(shù)據(jù)網(wǎng)格任務(wù)調(diào)度算法，并且假定各任務(wù)之間相互獨立，任務(wù)在不同的資源主機上運行的預(yù)測執(zhí)行時間可知。目前，經(jīng)典的批處理模式下的調(diào)度算 法 有：Min－min［4－6］算 法、Max－min［7］算 法、GA［8－9］算法、Sufferage［10］算 法 和 SA［11］（simulated annealing）等。Min－min算法是基于MCT的改進算法，算法優(yōu)先選擇最早完成時間最小的任務(wù)進行調(diào)度，以最快的速度減少任務(wù)調(diào)度隊列中的待調(diào)度任務(wù)，以縮短任務(wù)的完成時間。但是Min－min算法也存在其局限性，僅追求任務(wù)完成時間最早的局部最優(yōu)解，使得系統(tǒng)負載不均衡，導(dǎo)致時間跨度值變大。尤其當(dāng)任務(wù)的執(zhí)行時間差異較大時，產(chǎn)生的負面效應(yīng)就會越突出。Max－min算法也是基于最小完成時間 （minimum completion time，MCT）的改進算法，算法選取最早完成時間最大的任務(wù)進行優(yōu)先調(diào)度。上述算法都是比較有效的任務(wù)調(diào)度算法，但均未考慮用戶的QoS約束問題。

在以QoS約束作為指導(dǎo)的調(diào)度算法研究中，張偉哲［12］等人提出的多QoS約束下的多目標(biāo)演化算法，由于算法本身被規(guī)約為多目標(biāo)組合最優(yōu)化問題，潛在存在算法復(fù)雜度不可控的缺陷，并且不易于約束條件的擴展。Castillo等人［13］使用計算幾何的概念來解決當(dāng)服務(wù)質(zhì)量被滿足時資源提前預(yù)留機制中所產(chǎn)生的資源碎片問題，并制定了一套調(diào)度策略。孫偉峰［14］等人以多QoS約束的任務(wù)作為研究對象，結(jié)合改進的蟻群算法，提出了一種基于蟻群算法的多QoS約束網(wǎng)格任務(wù)調(diào)度算法 （QIACO），算法將QoS約束轉(zhuǎn)換成效用。Li［15］和 Gong［16］等人提出的基于效益模型的調(diào)度算法，利用效益函數(shù)來衡量用戶任務(wù)的QoS約束需求，其考慮了用戶的多維QoS約束要求，但沒有考慮系統(tǒng)指標(biāo)（負載均衡、系統(tǒng)穩(wěn)定性等）。Liu［17］等人提出的基于 QoS相識度的任務(wù)調(diào)度算法S－GTSA，在任務(wù)調(diào)度過程中，該算法雖對用戶的QoS需求給予了較好的滿足，卻沒有對全部待執(zhí)行任務(wù)的執(zhí)行時間跨度進行較好的考慮。

在分析、參考了大量異構(gòu)環(huán)境下的網(wǎng)格任務(wù)調(diào)度算法，并對系統(tǒng)任務(wù)調(diào)度中的時間跨度、負載均衡等問題進行了針對性的研究以后，在前人研究工作的基礎(chǔ)上，結(jié)合Minmin算法，提出了基于最早完成時間與QoS相識度的數(shù)據(jù)網(wǎng)格 任 務(wù) 調(diào) 度 算 法 （data grid task scheduling algorithm based on Min－min and QoS Similarity，MS－GTSA）。該算法在時間跨度、負載均衡和用戶費用等方面均有所提高，特別是在時間跨度方面，較S－GTSA算法有較大提高。仿真結(jié)果分析表明，所提改進算法具有較好的綜合性能。

2 MS－GTSA算法

2.1 問題定義

為了更好的描述MS－GTSA算法，本文采用以下一般性定義：

定義1 R ＝ ｛r0，r1，r2，…，rm－1｝表示網(wǎng)格資源集合，m＝｜R｜表示網(wǎng)格環(huán)境中的資源數(shù)目，其中ri＝ ｛rID，r QoS，r Data，r Cap，…｝表示第i個網(wǎng)格資源。

定義2 T ＝ ｛t0，t1，t2，…，tn－1｝表 示 任 務(wù) 集 合，n ＝｜T｜表示任務(wù)集合的大小，即任務(wù)的總數(shù)目，在此僅考慮元任務(wù)，任務(wù)之間相互獨立，且任務(wù)不跨資源節(jié)點執(zhí)行。其中ti＝ ｛tID，t QoS，t Sta，t Len，…｝表示第i個任務(wù)。

定義3 n個待執(zhí)行任務(wù)在m個可用資源主機上面的執(zhí)行時間 （execute time，ET）結(jié)果為n×m的矩陣

元素etij表示待執(zhí)行任務(wù)ti在可用資源主機rj上的執(zhí)行時間。

2.2 多維QoS約束

為了統(tǒng)一任務(wù)的多維QoS約束需求，對資源的QoS能力進行評價，使用式 （1）和式 （2）對任務(wù)的多維QoS需求矩陣和資源主機的QoS能力矩陣進行標(biāo)準(zhǔn)化處理。一般對于QoS約束，可分為積極的約束 （完成時間、負載均衡、成功率等）和消極的約束 （用戶費用等）兩類，需要分別進行歸一化處理，即

為了計算任務(wù)的第j維QoS參數(shù)在距離測量計算中所占的權(quán)重值，使用式 （3）計算其所占權(quán)重值，即

在對多QoS約束需求參數(shù)進行標(biāo)準(zhǔn)化處理之后，使用式 （4）對用戶的綜合QoS需求值進行計算，即

為了評估任務(wù)QoS約束與資源主機QoS能力之間的QoS距離，以選取QoS相識度最大的任務(wù)到相應(yīng)的資源主機上去執(zhí)行，需要使用式 （5）計算其之間的QoS距離，即

為了更合理的對任務(wù)進行調(diào)度分配，需要計算任務(wù)ti在可能被分配的資源主機rj上的QoS約束的綜合滿意度情況，使用式 （6）計算其QoS綜合滿意度值，即

2.3 算法流程

根據(jù)前述定義，首先合并用戶任務(wù)QoS約束矩陣Qn，k和資源QoS能力矩陣Qm，k，并對其進行標(biāo)準(zhǔn)化處理，分別得到任務(wù)QoS矩陣tSn，k和資源QoS矩陣tRm，k；計算各維QoS約束所占權(quán)重；計算任務(wù)的綜合QoS需求值，并對其從大到小排序；選取滿意度最大并且最早完成時間最小的任務(wù)優(yōu)先進行調(diào)度分配，并不斷更新任務(wù)集合，直至任務(wù)集合為空。

對于用戶任務(wù)QoS約束矩陣Qn，k、資源QoS能力矩陣Qm，k和執(zhí)行時間矩陣ET均已知，并已初始化，詳細算法流程如下：

（1）輸入矩陣Qn，k和Qm，k。

（2）合并矩陣Qn，k和Qm，k，組成新的矩陣 Qn＋m，k，對矩陣Qn＋m，k用式 （1）和式 （2）進行標(biāo)準(zhǔn)化處理，得到標(biāo)準(zhǔn)化矩陣Sn＋m，k，對標(biāo)準(zhǔn)化處理后的新矩陣進行分離，分別得到任務(wù)QoS矩陣tSn，k和資源QoS矩陣tRm，k。

（3）根據(jù)式 （3）計算出后面距離測量中所需的各維QoS約束所占的權(quán)重值。

（4）根據(jù)式 （4）計算每項任務(wù)的綜合QoS需求值，并對其從大到小排序。

（5）如果任務(wù)集合T非空，選取 （4）中第一個任務(wù)t0，并根據(jù)式 （6）計算出任務(wù)t0在各資源主機上的綜合滿意度值，選出滿意度值最高的資源，將其存入資源序列Rs。

（6）當(dāng)滿足最高滿意度值的資源不多于一個時，結(jié)合時間執(zhí)行矩陣ET，選取最早完成時間最小并且滿意度值最大的資源，將任務(wù)t0分配到該資源的調(diào)度序列上去等待執(zhí)行。

（7）根據(jù)式 （5）計算出任務(wù)t0和資源序列Rs中各個資源的距離值dis，結(jié)合時間執(zhí)行矩陣ET，選取出dis值最小并且最早完成時間最小的第一個資源，將任務(wù)t0分配到該資源的調(diào)度序列上去等待執(zhí)行。

（8）將t0從任務(wù)集合序列T中剔除，如果T非空，則返回 （5）。

（9）檢查所有任務(wù)是否執(zhí)行完成，如果存在尚未執(zhí)行的任務(wù)，則檢查是否有空閑資源。若所有任務(wù)都執(zhí)行完成，則跳轉(zhuǎn)到 （11）。

（10）如果有空閑資源，則查看該資源是否滿足尚未被執(zhí)行任務(wù)的最高滿意度值，如果滿足，則執(zhí)行該任務(wù)，并將任務(wù)從原來被分配到的資源序列隊列中剔除，否則轉(zhuǎn)到（9）。

（11）任務(wù)執(zhí)行完成。

3 性能分析

分別進行兩組實驗，每組實驗相互獨立，每組執(zhí)行20次，采集仿真模擬數(shù)據(jù)，取其均值，分析算法的性能。

3.1 完成時間

圖1為資源數(shù)為10時，在不同任務(wù)數(shù)下進行的仿真實驗得到的完成時間均值，任務(wù)數(shù)按20、40、60、80、100遞增。

為了驗證算法的有效性，使用GridSim仿真包作為本次的仿真實驗環(huán)境。在實驗中，任務(wù)執(zhí)行時間矩陣ET、各資源所提供的服務(wù)質(zhì)量能力矩陣Qm，k以及任務(wù)對資源服務(wù)能力要求矩陣Qn，k均由計算機模擬隨機產(chǎn)生。仿真環(huán)境中的資源數(shù)設(shè)定為10個，且每一個資源都只有一個PE，每一個資源的處理能力均為520（MIPS）。

仿真實驗主要側(cè)重于完成時間、資源平均利用率兩個方面，并與QoS－Min－Min算法和文獻 ［17］所提出的基于QoS相識度的任務(wù)調(diào)度算法 （S－GTSA）進行完成時間的對比；與文獻 ［17］所提的基于QoS相識度的任務(wù)調(diào)度算法進行資源平均利用率的對比。其中，資源平均利用率按下式計算

圖1 完成時間

圖1中，主要進行了3種算法在不同任務(wù)數(shù)下的完成時間情況比較。所提改進算法在完成時間上較原有S－GTSA算法有較明顯的下降，伴隨著任務(wù)數(shù)的增加，下降趨勢較為明顯；相比于QoS－Min－min算法，完成時間有所上升，分析其原因，主要是由于考慮了系統(tǒng)負載均衡所致。

3.2 資源平均利用率

由圖2可知，所提改進算法MS－GTSA在資源平均利用率上較S－GTSA略有下降，分析其原因，主要是由于考慮了用戶任務(wù)的執(zhí)行時間、QoS約束匹配程度等所致。

圖2 資源平均利用率比較

仿真結(jié)果表明，MS－GTSA算法有效降低了待調(diào)度任務(wù)的時間跨度，并且易于約束條件的擴展，達到了算法改進的預(yù)期。

4 結(jié)束語

本文對基于QoS約束下的各種任務(wù)調(diào)度算法進行了研究，分析了相應(yīng)的任務(wù)調(diào)度算法，并深入研究分析了S－GTSA任務(wù)調(diào)度算法。在原有算法的基礎(chǔ)上，將 Min－min算法引入S－GTSA算法之中，利用最早完成時間算法對原有算法進行改進，使得MS－GTSA算法在完成時間 （時間跨度）等指標(biāo)上有較大提高，在最大化用戶滿意度的同時，盡可能的縮短了任務(wù)的完成時間。不過在實際應(yīng)用中，我們認為還有很多不確定的參數(shù)需要考慮，比如：相關(guān)參數(shù)的動態(tài)可調(diào)整性、約束的即時變更等等，這些都還有待進一步的分析與研究。

［1］DOU Zhihui，CHEN Yu，LIU Peng.Grid computing ［M］.Beijing：Tsinghua University Press，2002 （in Chinese）. ［都志輝，陳渝，劉鵬.網(wǎng)格計算 ［M］.北京：清華大學(xué)出版社，2002.］

［2］Muthuvelu N，Chai I，Eswaran C.An adaptive and parameterized job grouping algorithm for scheduling grid jobs ［C］／／Proc of 10th International Conference on Advanced Communication Technology. Phoenix Park， Korea：IEEE，2008：975－980.

［3］WANG Xianglin，ZHANG Shanqing，WANG Jingli.The grid core technologies ［M］.Beijing：Tsinghua University Press，2006（in Chinese）.［王相林，張善卿，王景麗.網(wǎng)格計算核心技術(shù) ［M］.北京：清華大學(xué)出版社，2006.］

［4］ZHOU Yang，JIANG Changjun，F(xiàn)ANG Yu.Research of scheduling of independent tasks onto heterogeneous computing systems ［J］.Computer Science，2008，35 （8）：90－92 （in Chinese）.［周洋，蔣昌俊，方鈺.異構(gòu)環(huán)境下的獨立任務(wù)調(diào)度算法的研究 ［J］.計算機科學(xué)，2008，35 （8）：90－92.］

［5］MO Zan，XIE Na，JIA Gongxiang，et al.Research on grid re－source scheduling for multi－QoS demands ［J］.Application Research of Computers，2012，29 （10）：3904－3907 （in Chinese）.［莫贊，謝娜，賈功祥，等.基于多QoS需求驅(qū)動的網(wǎng)格資源調(diào)度研究 ［J］.計算機應(yīng)用研究，2012，29 （10）：3904－3907.］

［6］LEI Binghan，HE Jun，HE Xiang，et al.Grid load schedule algorithm based on QoS ［J］.Computer Engineering，2009，35 （24）：96－98 （in Chinese）.［雷炳翰，何軍，何翔，等.基于QoS的網(wǎng)格負載調(diào)度算法 ［J］.計算機工程，2009，35（24）：96－98.］

［7］Chauhan Sameer Singh，Joshi R C.Weighted mean time minmin max－min selective scheduling strategy for independent tasks on grid ［C］／／Proceedings of IEEE 2nd International Advance Computing Conference，2010：4－9.

［8］Fatos Xhafa，Javier Carretero.Genetic algorithm based schedulers for grid computing systems ［J］.International Journal of Innovative Computing，Information and Control，2007，3（5）：1－19.

［9］ZHU Hai，WANG Yuping.Constrained multi－objective grid task security scheduling model and algorithm ［J］.Journal of Electronics and Information Technology，2010，32 （4）：988－992（in Chinese）.［朱海，王宇平.多目標(biāo)約束的網(wǎng)格任務(wù)安全調(diào)度模型及算法研究 ［J］.電子與信息學(xué)報，2010，32（4）：988－992.］

［10］LI Jiong，LU Xianliang，DONG Shi.Research on resource scheduling strategies for grid based on GridSim ［J］.Computer Science，2008，35 （8）：95－97 （in Chinese）. ［李炯，盧顯良，董仕.基于GridSim模擬器的網(wǎng)格資源調(diào)度算法研究［J］.計算機科學(xué)，2008，35 （8）：95－97.］

［11］XUE Shengjun，XU Junlei，XING Guowen.Annealing evolution algorithm for grid task scheduling ［J］.Application Research of Computers，2011，28 （11）：4049－4052 （in Chinese）.［薛勝軍，徐鈞磊，刑國穩(wěn).一種用于網(wǎng)格任務(wù)調(diào)度的退火進化算法 ［J］.計算機應(yīng)用研究，2011，28 （11）：4049－4052.］

［12］ZHANG Weizhe，HU Mingzeng，ZHANG Hongli，et al.A multi－objective evolutionary algorithm for grid job scheduling of multi－QoS constraints ［J］.Journal of Computer Research and Development，2006，43 （11）：1855－1862 （in Chinese）.［張偉哲，胡銘曾，張宏莉，等.多QoS約束網(wǎng)格作業(yè)調(diào)度問題的多目標(biāo)演化算法 ［J］.計算機研究與發(fā)展，2006，43（11）：1855－1862.］

［13］Castillo，Rouskas G N，Harfoush K.Online algorithms for advance resource reservations ［J］.Journal of Parallel and Distributed Computing，2011，71 （7）：963－973.

［14］SUN Weifeng，QIN Zhenquan，LI Mingchu，et al.QIACO：An algorithm for grid task scheduling of multiple QoS dimensions ［J］.Acta Electronica Sinica，2011，39 （5）：1115－1120（in Chinese）. ［孫偉峰，覃振權(quán)，李明楚，等.QIA－CO：一種多QoS約束網(wǎng)格任務(wù)調(diào)度算法 ［J］.電子學(xué)報，2011，39 （5）：1115－1120.］

［15］LI Yuanhui，ZHAO Depeng，LI Jun.Scheduling algorithm based on integrated utility of multiple QoS attributes on service grid ［C］／／Proc of the 6th International Conference on Grid and Cooperative Computing.Washington D.C，USA：IEEE Computer Society，2007：288－295.

［16］GONG Hongcui，YU Jiong，HOU Yong，et al.User QoS and system index guided task sche－duling in computing grid ［J］.Com－puter Engineering，2009，35 （7）：52－54 （in Chinese）. ［龔紅翠，于炯，侯勇，等.用戶QoS及系統(tǒng)指標(biāo)指導(dǎo)的計算網(wǎng)格任務(wù)調(diào)度 ［J］.計算機工程，2009，35 （7）：52－54.］

［17］LIU Yanbing，CHEN Jie，XIONG Shiyong.Grid task scheduling algorithm based on QoS similarity ［J］.Journal of Chongqing University of Posts and Telecommunications （Natural Science Edition），2009，21 （3）：416－420 （in Chinese）. ［劉宴兵，陳杰，熊仕勇.基于QoS相識度的網(wǎng)格任務(wù)調(diào)度算法 ［J］.重慶郵電大學(xué)學(xué)報 （自然科學(xué)版），2009，21 （3）：416－420.］