一種基于任務(wù)分解的時間均衡調(diào)度算法

魏妮妮，宋 翌

(武漢生物工程學(xué)院計算機與信息工程系,湖北武漢 430415)

隨著大型的科學(xué)研究對高性能和大容量數(shù)據(jù)處理能力需求的不斷增加，網(wǎng)格計算技術(shù)的研究范圍迅速擴大。網(wǎng)格計算的實質(zhì)就是分布式計算，且主要研究在分布、異構(gòu)、自治的網(wǎng)絡(luò)資源環(huán)境上動態(tài)構(gòu)建虛擬組織并實現(xiàn)跨自治域的資源共享與協(xié)同工作。任務(wù)調(diào)度是網(wǎng)格計算研究的核心問題之一，并已證明是NP完全問題，它引起了眾多學(xué)者的關(guān)注[1-4]。

網(wǎng)格任務(wù)調(diào)度實質(zhì)就是按照一定的調(diào)度策略和調(diào)度規(guī)則，把用戶提交的網(wǎng)格作業(yè)映射到多管理域資源上的過程[5]。圍繞網(wǎng)格計算中的任務(wù)調(diào)度問題，國內(nèi)外已經(jīng)做了大量的研究工作，先后提出了各種任務(wù)調(diào)度算法[6-7]。其中比較經(jīng)典的有Min-min算法、Max-min算法、Sufferage算法、Max-int算法、SA算法和遺傳算法等。另外就是這些算法的組合算法，如文獻[8]—文獻[11]提到的算法。這些算法可分為兩類:在線模式和批處理模式。在線模式的實時響應(yīng)性較好，批處理模式調(diào)度算法的共性就是在進行調(diào)度時以優(yōu)化任務(wù)完成時間為目標。雖然上述算法在解決特定領(lǐng)域問題時具有一定的效果，但還是存有一定的缺陷。尤其是對于高吞吐率應(yīng)用中的“任務(wù)放牧”[12]問題的處理效果不佳，也沒有考慮到資源節(jié)點的性能度量及任務(wù)自身的區(qū)別。為此，本文針對高吞吐量應(yīng)用問題提出了一種新的任務(wù)調(diào)度算法。

1 基于任務(wù)分解的時間均衡調(diào)度算法

1．1算法思想

本文提出了一種基于任務(wù)分解的時間均衡啟發(fā)式調(diào)度算法(TBSTD，time-balancing heuristic task scheduling algorithm based on task decomposition)。該算法將一個獨立任務(wù)分解成多個子任務(wù)，并使多個分解后的子任務(wù)并行執(zhí)行，任務(wù)的完成時間由執(zhí)行時間最長的子任務(wù)決定。顯然，當分解后的子任務(wù)數(shù)目一定時，各子任務(wù)在相應(yīng)調(diào)度資源上的完成時間點相同，任務(wù)總的完成時間最短。使各個分解后的子任務(wù)具有相同的預(yù)測完成時間的點的分解策略稱為“時間均衡”策略。TBSTD算法是基于時間均衡策略對獨立任務(wù)進行分解，按具有最小的任務(wù)預(yù)測完成時間的任務(wù)分解方案實施調(diào)度，通過使任務(wù)分解后的多個子任務(wù)并行運行，縮短任務(wù)完成時間，提高系統(tǒng)資源的利用率。TBSTD在調(diào)度過程中充分考慮到了網(wǎng)格中資源節(jié)點具有動態(tài)、異構(gòu)、分布等特點，引入了自動調(diào)節(jié)因子，并進行重復(fù)調(diào)度，以使本算法能對任務(wù)作出及時響應(yīng)，能夠適應(yīng)更復(fù)雜的實際應(yīng)用環(huán)境。

1．2算法設(shè)計與描述

調(diào)度問題描述如下：假設(shè)網(wǎng)格計算系統(tǒng)中有N個相互獨立的任務(wù)形成的集合為t={ t[1],t[2],…,t[N] }，M個可用資源形成的集合p={p[1],p[2],…,p[M]}且規(guī)定這M個資源的負載低于某一固定閾值，各個可用資源的負載表示為 L[1]，L[2]，…，L[m]。E[k]j表示第k個任務(wù)在第j個節(jié)點上的預(yù)測執(zhí)行時間, C[k]j表示第k個任務(wù)在第j個節(jié)點上的預(yù)期完成時間。某時刻當用戶提交了一個問題規(guī)模為w的任務(wù)t[k]到達時，t[k]被分解成m個可并行執(zhí)行的子任務(wù)，并定義t[k]分解的子任務(wù)為t[k]j, t[k]j的問題規(guī)模為wj。為了簡化算法的設(shè)計，本文算法僅考慮本地任務(wù)的調(diào)度。

基于任務(wù)分解的時間均衡策略實施步驟描述如下：

1)確定任務(wù)分解的子任務(wù)的期望執(zhí)行時間；

2)確定時間均衡策略；

3)確定任務(wù)的自動調(diào)節(jié)因子；

4)實施調(diào)度。

1．2．1 子任務(wù)的期望執(zhí)行時間

假設(shè)本地任務(wù)在不同時間內(nèi)的到達是相互獨立的平穩(wěn)增量過程，子任務(wù)t[k]j在資源p[j]上執(zhí)行期間共有R個任務(wù)到達并被執(zhí)行完成。因為本地任務(wù)的到達是平穩(wěn)過程，所以可認為對充分小的Δt在時間區(qū)間[t,t+Δt]內(nèi)有一個本地任務(wù)到達的概率與t無關(guān)，而是與區(qū)間長Δt成正比;由于在此區(qū)間內(nèi)有兩個或兩個以上的本地任務(wù)到達的概率極小，以至可以忽略不計。又因為在不同時間內(nèi)的本地任務(wù)的到達是相互獨立的，所以在wj時間內(nèi)本地任務(wù)的到達數(shù)服從泊松分布，為此資源p[j] 對本地任務(wù)提供的服務(wù)可看作M/G/1排隊系統(tǒng)。在M/G/1排隊系統(tǒng)中本地任務(wù)被資源p[j]處理的平均服務(wù)率為μ，平均到達率為λ。μ表示單位時間內(nèi)能被資源完成的任務(wù)數(shù)，λ表示單位時間內(nèi)到達的任務(wù)數(shù)，ρ表示處理強度，ρ=λ/μ。

本地任務(wù)Tk在資源j上的期望完成時間定義為

(1)

由于本地任務(wù)的期望完成時間和子任務(wù)t[k]j在資源p[j]上執(zhí)行期間本地任務(wù)的到達數(shù)R，可建立任務(wù)t[k]分解的子任務(wù)期望執(zhí)行時間模型。規(guī)模為wj的子任務(wù)t[k]j在資源p[j]上的期望執(zhí)行時間E[k]j可表示為

(2)

其中wj表示子任務(wù)的問題規(guī)模大小，ρj表示資源p[j]的處理強度，即相同時間內(nèi)任務(wù)平均到達數(shù)與被服務(wù)的平均數(shù)之比。

1．2．2 確定時間均衡策略

在上述1．2．1中確定了子任務(wù)的期望執(zhí)行時間E[k]j由式(2)表示，在此基礎(chǔ)上來預(yù)測子任務(wù)t[k]j預(yù)期完成時間。子任務(wù)t[k]j在資源j上的預(yù)期完成時間等于子任務(wù)t[k]j的預(yù)期執(zhí)行時間E[k]j與子任務(wù)t[k]j等待資源j提供服務(wù)的時間之和，t[k]j等待資源j提供服務(wù)的時間是由資源j的負載決定的。當任務(wù)分解后的m個任務(wù)分別調(diào)度到m個相應(yīng)資源上執(zhí)行， m個 資源的負載分別表示為L[1]，L[2]，…，L[m]，則子任務(wù)t[k]j的預(yù)期完成時間表示為

C[k]j=L[j]+E[k]j。

(3)

當任務(wù)t[k]分解為m個子任務(wù)并行執(zhí)行時，其完成時間由具有最大完成時間的子任務(wù)來決定，即滿足：

C[k]m=max{C[k]j}，j=1,2,…，m。

(4)

任務(wù)t[k]分解成m個子任務(wù),各個子任務(wù)的預(yù)期完成時間分別表示為

C[k]1,C[k]2,…，C[k]m,設(shè)C[k]1=t1，C[k]2=t2,…，C[k]m=tm,且t1,t2,…,tm不全相等。假設(shè)其中t1最大，則任務(wù)的預(yù)期完成時間C[k]m=1，如果此時任務(wù)的預(yù)期完成時間最短，則t1與t2,…,tm滿足如下關(guān)系：ti=t1-Δti，其中i=2,3,…，m。由式(2)和式(3)可知在資源j上執(zhí)行的子任務(wù)t[k]j的問題規(guī)模可表示為

wj=(tj-Lj)(1-ρj)，j=1,2,…，m。

(5)

任務(wù)t[k]的問題規(guī)模w可表示為各個子任務(wù)的問題規(guī)模之和，即：

(6)

任務(wù)完成時間 t1經(jīng)變換可表示為

(7)

當t1最小時，任務(wù)的預(yù)期完成時間最短，由式(7)可知當Δtj為零時t1的值最小，即當各個子任務(wù)的預(yù)期完成時間相同時，任務(wù)的預(yù)期完成時間最短。與前面假設(shè)t1,t2,…,tm不全相等時矛盾，所以僅有當子任務(wù)的預(yù)期完成時間相等時任務(wù)的預(yù)期完成時間才最短。

當采用時間均衡進行任務(wù)分解時，設(shè)分解后的各個子任務(wù)的預(yù)期完成時間為常數(shù)a：

C[k]j=E[k]j+Lj=a。

(8)

由式(6)和式(8)可知，任務(wù)t[k]的問題規(guī)模w可用下式表示：

(9)

分解后子任務(wù)的問題規(guī)模wj可重新定義為

wj=(1-ρj)E[k]j。

(10)

由式(8)和式(10)可確定子任務(wù)t[k]j的預(yù)期執(zhí)行時間為

(11)

則子任務(wù)的預(yù)期完成時間為

(12)

由上述可知，當任務(wù)分解后的子任務(wù)數(shù)目確定時，只有各個子任務(wù)的預(yù)期完成時間全部相等時，才能保證整個任務(wù)的預(yù)期完成時間最短，即任務(wù)分解應(yīng)采取“時間均衡”策略。任務(wù)分解的時間均衡就是解決任務(wù)如何在m個資源間進行分解，從而使這種分解模式下任務(wù)的預(yù)期完成時間最小。

1．2．3 確定任務(wù)的自動調(diào)節(jié)因子

由于計算網(wǎng)格資源自身具有的動態(tài)性、異構(gòu)性、自治性等特點，在進行任務(wù)調(diào)度時如果采用批處理模式調(diào)度算法，會出現(xiàn)“饑餓現(xiàn)象”，饑餓現(xiàn)象是指有些任務(wù)長時間得不到調(diào)度，這種任務(wù)被稱為饑餓任務(wù)。特別是在使用“等長時間間隔”進行任務(wù)調(diào)度的系統(tǒng)中經(jīng)常出現(xiàn)，但在實際的任務(wù)調(diào)度中這種饑餓現(xiàn)象是不允許出現(xiàn)的。為解決這種饑餓任務(wù)的出現(xiàn)，本文引入了自動調(diào)節(jié)因子。

1．2．4 實施調(diào)度

通過上述定義和分析，現(xiàn)給出基于任務(wù)分解的時間均衡算法實施調(diào)度簡要步驟描述如下。

第1步：將當前系統(tǒng)到達的新任務(wù)和已經(jīng)被調(diào)度但未被執(zhí)行的任務(wù)收集到任務(wù)集t中;

第2步：找到當前系統(tǒng)中現(xiàn)存負載小于固定閾值的M個可用資源，形成可用資源集p;

第3步：依據(jù)可用資源當前負載由小到大進行排序;

第4步：將需要進行優(yōu)先調(diào)度的任務(wù)附上自動調(diào)節(jié)因子;

第5步：重新計算任務(wù)問題規(guī)模并按升序進行排序;

第6步：根據(jù)第5步結(jié)果，從任務(wù)集t中選擇任務(wù)問題規(guī)模最小的任務(wù)進行調(diào)度;

第7步：取m個資源根據(jù)式(12)計算任務(wù)的期望完成時間;

第8步：如果C[k]m≤L[m+1]，選擇具有最小任務(wù)期望完成時間和相應(yīng)的資源組;

第9步：按式(8)和式(10)實施任務(wù)分解并調(diào)度到相應(yīng)資源上執(zhí)行;

第10步：從任務(wù)集中刪除執(zhí)行完畢的任務(wù);

第11步：更新任務(wù)集和可用資源信息;

第12步：若任務(wù)集t中還有未被調(diào)度完成的任務(wù)，轉(zhuǎn)到第2步執(zhí)行，若任務(wù)集中的任務(wù)都已被調(diào)度執(zhí)行完成，則轉(zhuǎn)到第1步執(zhí)行。

2 仿真實驗與性能分析

針對TBSTD算法，在這里人們使用的是SimGrid[13-15]進行模擬仿真。創(chuàng)建1個中心節(jié)點，10個用戶節(jié)點作為計算資源，任意給出100個相互獨立的任務(wù)，進行10組仿真實驗。在實驗中規(guī)定任務(wù)的計算時間處于0.5～30 s之間。針對相同的任務(wù)在仿真平臺上對調(diào)度事件發(fā)生的頻率及對算法性能的影響進行了分析。從任務(wù)完成總的時間和系統(tǒng)資源利用率方面與Max-min和Max-int算法進行了對比。

圖1 γ取不同值時任務(wù)完成時間對比圖Fig.1 Task completion time while different γ value is used

實際上，要使Δt取值最優(yōu)，γ的取值應(yīng)是動態(tài)變化。從圖1中可知當γ=4時系統(tǒng)任務(wù)的總的完成時間最小，為此對本算法后面進行的仿真實驗中取γ值近似為4。

當取γ=4時分別對100個任務(wù)進行了10組實驗，從任務(wù)完成總的時間和系統(tǒng)吞吐率與Max-min和Max-int算法進行對比，實驗結(jié)果分別如圖2和圖3所示。

圖2 三種算法完成時間對比圖Fig.2 Completion time comparison of three algorithms

圖3 三種算法系統(tǒng)吞吐率對比圖Fig.3 System throughput rate comparison of three algorithms

由圖2可知Max-min算法的任務(wù)完成時間為285 s，Max-int算法的任務(wù)完成時間為273.7 s， TBSTD算法的任務(wù)完成時間為255.5 s,顯然相同處理任務(wù)情況下TBSTD算法具有較少的任務(wù)完成時間。 圖3是從3種算法完成相同任務(wù)系統(tǒng)吞吐率的方面進行對比，從圖3中可知，采用TBSTD算法每秒鐘完成的任務(wù)的個數(shù)多于Max-min和Max-int算法，具有較高的系統(tǒng)吞吐率。從以上實驗結(jié)果可知，Max-min和Max-int算法進行任務(wù)調(diào)度時沒有對任務(wù)進行分解，任務(wù)執(zhí)行的粒度大，不能充分利用空閑可用資源解決問題，從而導(dǎo)致任務(wù)總的完成時間較大，系統(tǒng)吞吐率較低。TBSTD算法實施調(diào)度時充分考慮了資源的特性，對任務(wù)進行分解，分解后的各個子任務(wù)可調(diào)度到多個可用資源上并行執(zhí)行，充分利用了系統(tǒng)的空閑資源，從而減少了任務(wù)的完成時間，有利于提高系統(tǒng)的吞吐率。

3 結(jié) 語

提出的TBSTD調(diào)度算法在時間均衡的策略下對任務(wù)進行分解，并采用重復(fù)調(diào)度的方式實施任務(wù)調(diào)度。通過仿真實驗從任務(wù)完成時間和系統(tǒng)吞吐率兩方面與Max-min和Max-int算法進行對比。實驗結(jié)果證明本文提出的TBSTD算法在任務(wù)總的完成時間和系統(tǒng)吞吐率方面都優(yōu)于上述兩種方法。即本文提出的TBSTD對于“任務(wù)放牧”這類問題的調(diào)度具有更好的優(yōu)越性，是一種較好的任務(wù)調(diào)度算法。

參考文獻/References：

[1] CASANOVA H．Network modeling issues for grid application scheduling[J].International Journal of Foundations of Computer Science, 2005，16(2)：145-162.

[2] 丁敏敏．網(wǎng)格計算中改進Min-Min算法的研究[D].西安：西北大學(xué),2010.

DING Minmin.Research of Improved Min-Min Algorithm in Grid Computing[D].Xi′an:Northwest University,2010.

[3] BRAUN T D, JAY S H, NOAH B. A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing dystems[J]. Journal of Parallel and Distributed Computing, 2001,61(6)：810-837.

[4] HE Xiaoshan, SUN Xiaohe, LASZEWSKIG V. QoS guided Min-Min heuristic for grid task scheduling[J]. Journal of Computer Science and Technology, 2003, 18(4): 442-451.

[5] YIN Fei, JIANG Changjun,DENG Rong, et al.Gird resource management policies for load-balancing and energy-saving by vacation queuing theory[J].Computer and Electrical Engineering,2009,35(6):966-979.

[6] 彭海云,李 騫,李 強.網(wǎng)格環(huán)境下資源負載均衡和優(yōu)化調(diào)度研究[J].計算機工程與應(yīng)用,2009,45(19):104-106.

PENG Haiyun, LI Qian,LI Qiang. Research on resources load balancing and task scheduling optimal algorithm in grid environment [J].Computer Engineering and Applications, 2009,45(19):104-106.

[7] 于 策，孫濟洲,李明楚，等.一種應(yīng)用于網(wǎng)格計算環(huán)境的任務(wù)調(diào)度模式[J].計算機應(yīng)用研究, 2008,25(5):1500-1503.

YU Ce, SUN Jizhou,LI Mingchu,et al.Task scheduling pattern for grid computing environment[J].Application Research of Computers, 2008,25(5):1500-1503.

[8] 李玲娟,史祥寧,王汝傳.一種基于改進螞蟻算法的網(wǎng)格任務(wù)調(diào)度策略[J].南京郵電大學(xué)學(xué)報(自然科學(xué)版),2008,28(3):17-20.

LI Lingjuan， SHI Xiangning, WANG Ruchuan. An improved ant algorithm-based task scheduling strategy in grid[J]. Journal of Nanjing Unicersity of Posts and Elecommunications (Natural Science), 2008,28(3):17-20.

[9] 孟憲福, 閆玲玲,劉偉偉. 基于動態(tài)任務(wù)優(yōu)先級的網(wǎng)格任務(wù)調(diào)度算法研究[J].大連理工大學(xué)學(xué)報, 2012，52(2):277-281.

MENG Xianfu, YAN Lingling,LIU Weiwei. Research on task scheduling algorithm in grid computing systems based on dynamic task priority[J].Journal of Dalian University of Technology, 2012，52(2):277-281.

[10] 劉波濤，劉金廣.基于動態(tài)粒子群優(yōu)化的網(wǎng)格任務(wù)調(diào)度算法[J].計算機應(yīng)用研究,2011，28(3):938-940.

LIU Botao, LIU Jinguang. Novel scheduling algorithm based on dynamic particle swarm optimization[J].Application Research of Computers, 2011，28(3):938-940.

[11] 林劍檸,吳慧中.一種基于動態(tài)決策路徑的網(wǎng)格任務(wù)調(diào)度算法[J].計算機研究與發(fā)展, 2008,45(5): 841-847.

LIN Jianning, WU Huizhong.A new scheduling algorithm in grid based on dynamic decisive path[J]. Journal of Computer Research and Development, 2008,45(5): 841-847.

[12] 胡艷麗,張維明,肖衛(wèi)東，等. 計算網(wǎng)格中基于時間均衡的并行粗粒度任務(wù)調(diào)度算法[J]. 小型微型計算機系統(tǒng),2008(1):124-129.

HU Yanli,ZHANG Weiming,XIAO Weidong, et al.A dynamic scheduling algorithm of parallel coarse grain tasks in computational grid based on time-balancing strategy[J]. Journal of Chinese Computer Systems, 2008(1):124-129.

[13] 金 海，袁平鵬，石 柯.網(wǎng)格計算[M].北京:電子工業(yè)出版社，2004.

JIN Hai,YUAN Pingpeng,SHI Ke.Gird Computing[M].Beijing:Pbulishing House of Electronics Industry,2004.

[14] 羅 紅,慕德俊,鄧智群,等. 網(wǎng)格計算中任務(wù)調(diào)度研究綜述[J].計算機應(yīng)用研究, 2005,22(5)：16-19.

LUO Hong, MU Dejun, DENG Zhiqun, et al.A review of job scheduling for grid[J].Application Research of Computers, 2005,22(5)：16-19.

[15] 查 禮，徐志偉，林國璋，等.基于Simgrid 的網(wǎng)格任務(wù)調(diào)度模擬[J].計算機工程與應(yīng)用，2003(14)：90-92.

ZHA Li,XU Zhiwei,LIN Guozhang,et al.Grid task scheduling simulations based on Simgrid[J].Computer Engineering and Applications, 2003(14)：90-92.

[16] 張京軍，劉文娟，劉光遠.基于改進免疫遺傳算法的網(wǎng)格任務(wù)調(diào)度[J].河北工程大學(xué)學(xué)報(自然科學(xué)版)，2013，30(2)：80-83.

ZHANG Jinjun,LIU Wenjuan, LIU Guangyuan.Task scheduling in grid computing based on improved immune genetic algorithm[J].Journal of Hebei University of Engineering(Natural Science Edition),2013,30(2):80-83.