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

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

0 引 言

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

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

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

1 相關工作

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

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

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

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｝表 示 任 務 集 合，n ＝｜T｜表示任務集合的大小，即任務的總數(shù)目，在此僅考慮元任務，任務之間相互獨立，且任務不跨資源節(jié)點執(zhí)行。其中ti＝ ｛tID，t QoS，t Sta，t Len，…｝表示第i個任務。

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

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

2.2 多維QoS約束

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

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

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

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

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

2.3 算法流程

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

對于用戶任務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）進行標準化處理，得到標準化矩陣Sn＋m，k，對標準化處理后的新矩陣進行分離，分別得到任務QoS矩陣tSn，k和資源QoS矩陣tRm，k。

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

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

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

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

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

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

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

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

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

3 性能分析

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

3.1 完成時間

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

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

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

圖1 完成時間

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

3.2 資源平均利用率

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

圖2 資源平均利用率比較

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

4 結束語

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

［1］DOU Zhihui，CHEN Yu，LIU Peng.Grid computing ［M］.Beijing：Tsinghua University Press，2002 （in Chinese）. ［都志輝，陳渝，劉鵬.網(wǎng)格計算 ［M］.北京：清華大學出版社，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)格計算核心技術 ［M］.北京：清華大學出版社，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）.［周洋，蔣昌俊，方鈺.異構環(huán)境下的獨立任務調度算法的研究 ［J］.計算機科學，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需求驅動的網(wǎng)格資源調度研究 ［J］.計算機應用研究，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)格負載調度算法 ［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）.［朱海，王宇平.多目標約束的網(wǎng)格任務安全調度模型及算法研究 ［J］.電子與信息學報，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)格資源調度算法研究［J］.計算機科學，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)格任務調度的退火進化算法 ［J］.計算機應用研究，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è)調度問題的多目標演化算法 ［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）. ［孫偉峰，覃振權，李明楚，等.QIA－CO：一種多QoS約束網(wǎng)格任務調度算法 ［J］.電子學報，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)指標指導的計算網(wǎng)格任務調度 ［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)格任務調度算法 ［J］.重慶郵電大學學報 （自然科學版），2009，21 （3）：416－420.］