□李陶深，李明麗，張希翔

（1. 廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院，廣西 南寧 530004；2.湖南大學(xué) 信息科學(xué)與技術(shù)學(xué)院，湖南 長(zhǎng)沙 4100075）

1 前言

云計(jì)算是近年來受到國(guó)內(nèi)外廣泛關(guān)注的研究熱點(diǎn)之一.云計(jì)算由一系列動(dòng)態(tài)變化的資源組成，這些資源通過虛擬化技術(shù)提供給云計(jì)算用戶，用戶可以通過網(wǎng)絡(luò)按需租賃云計(jì)算資源，從而減少用戶終端的處理負(fù)擔(dān)，并能享受云端強(qiáng)大的計(jì)算能力.云計(jì)算是分布式計(jì)算、集群計(jì)算、網(wǎng)格計(jì)算及并行計(jì)算的發(fā)展，它作為一種新穎、靈活、便捷、新崛起的商業(yè)計(jì)算模型，將計(jì)算任務(wù)分布在海量計(jì)算機(jī)構(gòu)成的集群上，用戶可以按需獲取計(jì)算能力、存儲(chǔ)容量和信息服務(wù)[1].

云計(jì)算對(duì)現(xiàn)代人類世界的改變正如發(fā)電廠對(duì)19世紀(jì)的人類用電方式的改變一樣.在沒有發(fā)電廠和電網(wǎng)的19世紀(jì)70年代，幾乎每個(gè)工廠甚至住戶都需要配備一臺(tái)發(fā)電機(jī)以供應(yīng)自身電力的需要，這樣的自發(fā)電機(jī)制無疑是低效而且昂貴.隨著電力需求的增加，人們提出了建立電力生產(chǎn)中心的思想，電能通過電網(wǎng)輸送到工廠、住所，人們不再需要購(gòu)買自己的發(fā)電機(jī)，轉(zhuǎn)向購(gòu)買發(fā)電廠通過電網(wǎng)輸送的電力資源.云計(jì)算的本質(zhì)和發(fā)電廠一致，龐大的計(jì)算中心或數(shù)據(jù)中心通過猶如電網(wǎng)一樣無所不在的互聯(lián)網(wǎng)，將計(jì)算資源輸送給千家萬戶，而用戶只需通過簡(jiǎn)單的設(shè)備根據(jù)需求訪問計(jì)算機(jī)與存儲(chǔ)系統(tǒng).

云計(jì)算的商業(yè)化特性使其必須具有通用性設(shè)計(jì)，并能便捷的為用戶動(dòng)態(tài)需求提供多樣化的服務(wù)，這樣的制約條件下，使得云計(jì)算的作業(yè)調(diào)度具有較高的復(fù)雜性.尤其云計(jì)算是一種商業(yè)實(shí)現(xiàn)，更為注重用戶每次使用云計(jì)算的體驗(yàn)和評(píng)價(jià).因此，云計(jì)算服務(wù)提供商如何通過恰當(dāng)?shù)恼{(diào)度策略高效地運(yùn)營(yíng)云計(jì)算資源顯得尤為重要[2].

任務(wù)調(diào)度就是以優(yōu)化為目的在一定的規(guī)則限制下將任務(wù)與資源做映射[3].任務(wù)調(diào)度是在所有計(jì)算機(jī)系統(tǒng)中都是影響系統(tǒng)性能的關(guān)鍵所在，它也是云計(jì)算系統(tǒng)中的關(guān)鍵問題.在云計(jì)算概念提出之前，在并行計(jì)算、網(wǎng)格計(jì)算和分布式計(jì)算中已經(jīng)存在著許多經(jīng)典的任務(wù)調(diào)度算法，例如：遺傳算法[4]、模擬退火算法[5]、Min-Min算法[6]、Min-Max算法[]和蟻群算法[7]等.這些算法經(jīng)過為適應(yīng)云計(jì)算的新特征做相應(yīng)改進(jìn)以后，都可以應(yīng)用于云計(jì)算系統(tǒng)的任務(wù)調(diào)度.但是在云計(jì)算環(huán)境下，作業(yè)調(diào)度系統(tǒng)需充分考慮制約用戶作業(yè)的各種因素，負(fù)責(zé)為用戶作業(yè)選取“云”或者網(wǎng)格中最適合的資源.

本文對(duì)云計(jì)算環(huán)境下任務(wù)調(diào)度的新特性、任務(wù)調(diào)度算法的研究現(xiàn)狀和相關(guān)研究成果進(jìn)行歸納和總結(jié)，探討和分析一些尚待解決的問題或尚未很好解決的問題，討論未來可以開展研究的工作方向.

2 云計(jì)算環(huán)境下任務(wù)調(diào)度的新特性

如前所述，云計(jì)算是網(wǎng)格計(jì)算、集群計(jì)算、并行計(jì)算的發(fā)展，因此在一定程度上，網(wǎng)格計(jì)算、集群計(jì)算和并行計(jì)算的作業(yè)調(diào)度策略對(duì)云計(jì)算具有相似性和借鑒性.但是，云計(jì)算不同于網(wǎng)格計(jì)算、集群計(jì)算和并行計(jì)算，它所采用的商業(yè)理念、形式、成熟的虛擬化技術(shù)以及非標(biāo)準(zhǔn)化的規(guī)范，使得云計(jì)算環(huán)境下的任務(wù)調(diào)度需要充分考慮按需提供虛擬化資源、付費(fèi)服務(wù)、用戶群體大、任務(wù)差異大等各種制約用戶作業(yè)的因素，調(diào)度中面臨許多新問題.

云計(jì)算系統(tǒng)是由海量商用機(jī)和高性能服務(wù)器混合組成，數(shù)據(jù)中心通過向用戶分配虛擬機(jī)的方式來運(yùn)行其所提交的任務(wù)，任務(wù)調(diào)度決定虛擬機(jī)的分配數(shù)量及任務(wù)執(zhí)行次序（如下圖1所示）.

圖1 云計(jì)算系統(tǒng)用戶獲取服務(wù)示意圖

從云計(jì)算資源使用者角度來說，用戶通?？紤]哪個(gè)云計(jì)算資源能滿足他們作業(yè)計(jì)算的QoS要求（例如作業(yè)類型、預(yù)期完成時(shí)間、計(jì)算時(shí)間等），及他們需要為云計(jì)算資源所支付的費(fèi)用.因此，在云計(jì)算任務(wù)調(diào)度中，需要滿足云計(jì)算用戶的作業(yè)QoS要求、性價(jià)比要求，使之以一種經(jīng)濟(jì)方式高效地利用云資源.從云服務(wù)提供商角度來說，系統(tǒng)是通過用戶所租用的資源(虛擬機(jī)數(shù)量、帶寬、內(nèi)存等)和時(shí)長(zhǎng)進(jìn)行收費(fèi)，因此在在云計(jì)算任務(wù)調(diào)度中，需要任務(wù)調(diào)度機(jī)制高效、及時(shí)地處理用戶任務(wù)請(qǐng)求，保持處理機(jī)負(fù)載均衡，以保障在滿足用戶服務(wù)質(zhì)量的前提下，提高云系統(tǒng)的吞吐量和整體用戶數(shù)量，進(jìn)而使云計(jì)算資源的使用獲得最大的收益.

假設(shè)有用戶向數(shù)據(jù)中心提交一個(gè)任務(wù)，可以分解為5個(gè)子任務(wù)，并根據(jù)子任務(wù)之間的依賴關(guān)系和先后關(guān)系生成有向無環(huán)圖(Directed Acyclic Graph，DAG)，如圖2所示.在傳統(tǒng)的任務(wù)調(diào)度中，一般只是從用戶的角度來考慮任務(wù)如何高效地完成.具體做法是：假設(shè)數(shù)據(jù)中心分配給該用戶三個(gè)虛擬機(jī)，定義預(yù)期執(zhí)行時(shí)間(Expected Execution Time)子任務(wù)ni在主機(jī)mj上 執(zhí)行的時(shí)間可用矩陣元素EETij表示，即：

運(yùn)用傳統(tǒng)的Min-Min算法來進(jìn)行任務(wù)調(diào)度，最后求得的運(yùn)行時(shí)間為100，子任務(wù)執(zhí)行順序與虛擬機(jī)資源分配如圖3所示.

圖2 子任務(wù)DAG圖

圖3 Min-Min算法甘特圖

從圖3的調(diào)度結(jié)果可知，在整個(gè)任務(wù)執(zhí)行過程中，虛擬機(jī)m1從未被分配子任務(wù)執(zhí)行.從云服務(wù)提供商的角度來說，本來可以分配給其他用戶的m1被閑置了，這造成了機(jī)會(huì)成本的浪費(fèi)；而從用戶的角度來說，如果租借不必要的虛擬機(jī)m1，就需要支出額外的費(fèi)用.

在本例中，雖然傳統(tǒng)的任務(wù)調(diào)度算法能夠滿足任務(wù)執(zhí)行時(shí)間最小的要求，但是未能達(dá)到用戶與服務(wù)提供商的利益最大化.文獻(xiàn)[8]提出了一種預(yù)先調(diào)度的算法，該算法應(yīng)用博弈論中納什均衡的思想來預(yù)先決定任務(wù)分解后所需的虛擬機(jī)數(shù)量，然后再進(jìn)行虛擬機(jī)的分配.這一算法減少了虛擬機(jī)的閑置時(shí)間，并達(dá)到了最小化執(zhí)行時(shí)間的目的.但是，為了降低兄弟節(jié)點(diǎn)的最早開始時(shí)間，該算法需要對(duì)其父節(jié)點(diǎn)進(jìn)行復(fù)制，這無形中會(huì)增加需執(zhí)行任務(wù)的數(shù)量并增加了通信開銷.文獻(xiàn)[9]從另外一個(gè)角度來避免虛擬機(jī)資源的浪費(fèi)，提出了一種云計(jì)算下適應(yīng)用戶任務(wù)動(dòng)態(tài)變更的調(diào)度算法，針對(duì)用戶因個(gè)人因素撤銷任務(wù)的情形，對(duì)每個(gè)撤銷任務(wù)根據(jù)其依賴關(guān)系撤銷關(guān)聯(lián)任務(wù)，更新DAG圖，然后再使用Min-Min算法進(jìn)行調(diào)度.這個(gè)算法提高了調(diào)度效率和云資源的利用率，保障了云服務(wù)提供商的利益.

與傳統(tǒng)系統(tǒng)的任務(wù)調(diào)度機(jī)制相比，云計(jì)算任務(wù)調(diào)度呈現(xiàn)出一些新的特性要求[2]：

(1)用戶對(duì)云計(jì)算資源需求具有多樣性與偏好性，因此需要考慮更復(fù)雜的QoS約束，最大限度地保障用戶QoS要求.對(duì)于這個(gè)特點(diǎn)，可以利用基于行為成本方法、基于工作流的方法、啟發(fā)式算法等求解組合優(yōu)化問題.

(2)調(diào)度時(shí)保證云計(jì)算服務(wù)提供商有效地利用云計(jì)算資源和獲得最大收益.云計(jì)算或網(wǎng)格中傳統(tǒng)的調(diào)度策略往往只考慮如何滿足各用戶的QoS要求，卻很少考慮資源提供商的最大收益.針對(duì)這個(gè)特點(diǎn)，可利用隊(duì)列模型方法、博弈論等解決任務(wù)調(diào)度問題.

3 云計(jì)算中任務(wù)調(diào)度技術(shù)的現(xiàn)狀分析

由于云計(jì)算技術(shù)比較新穎，目前有關(guān)云計(jì)算下任務(wù)調(diào)度的研究還比較少.一些學(xué)者根據(jù)云計(jì)算的特點(diǎn)，對(duì)云計(jì)算下的任務(wù)調(diào)度做了相關(guān)研究，取得了一些研究進(jìn)展.

3.1 經(jīng)典任務(wù)調(diào)度算法的改進(jìn)運(yùn)用

傳統(tǒng)的分布式計(jì)算和網(wǎng)格計(jì)算中有許多經(jīng)典的任務(wù)調(diào)度算法，這些算法經(jīng)過恰當(dāng)?shù)馗倪M(jìn)，可以適用于云計(jì)算環(huán)境中.下面是一些可用于云計(jì)算的經(jīng)典任務(wù)調(diào)度算法：

(1)機(jī)會(huì)負(fù)載均衡算法(OLB)：它將每一個(gè)任務(wù)，以任意順序，分配到下一個(gè)空閑的虛擬機(jī)中.這個(gè)算法非常簡(jiǎn)單，目的就是使所有虛擬機(jī)都運(yùn)轉(zhuǎn)效率.

(2)最小執(zhí)行時(shí)間算法(MCT)：它將任務(wù)以任意順序分配到虛擬機(jī)中的對(duì)該任務(wù)具有最小執(zhí)行時(shí)間的那臺(tái).最小執(zhí)行時(shí)間算法把每一個(gè)任務(wù)映射到對(duì)該任務(wù)而言的最佳虛擬機(jī)上，但是，它忽視了該虛擬機(jī)的機(jī)會(huì)成本，該算法損害了虛擬機(jī)的負(fù)載均衡性.

(3)最早完成時(shí)間算法(MCT)：將每一個(gè)任務(wù)以任意順序映射到對(duì)該任務(wù)而言具有最小最早完成時(shí)間的虛擬主機(jī)上.在該算法中，不能保證每一個(gè)任務(wù)都可以在最小執(zhí)行時(shí)間完成.

(4)Min-Min算法：從一個(gè)未分配任何虛擬機(jī)的任務(wù)集合開始，分為三個(gè)階段.第一階段：計(jì)算集合中每個(gè)任務(wù)的最小期望完成時(shí)間，并找出相對(duì)應(yīng)的機(jī)器.第二階段：找出所有最小期望完成時(shí)間集合里的最小值，并將該任務(wù)映射到相應(yīng)的虛擬機(jī)上.第三階段：指派完成后，更新機(jī)器期望就緒時(shí)間并將已映射的任務(wù)從任務(wù)集合中刪除.重復(fù)上面三個(gè)階段，直至所有的任務(wù)被映射到處理機(jī)中.

(5)Max-Min算法：Max-Min算法與Min-Min算法思想基本一致.不同的是Max-Min算法首先調(diào)度大任務(wù).因此，在第二階段中，Max-Min算法找出所有最小期望完成時(shí)間集合里的最大值，并將該任務(wù)映射到相應(yīng)的虛擬機(jī)上.其余階段與Min-Min算法完全相同.

3.2 啟發(fā)式任務(wù)調(diào)度算法

研究表明[10]：在云計(jì)算環(huán)境中，任務(wù)調(diào)度是一個(gè)NP完全問題.因此，啟發(fā)式算法經(jīng)常被視為解決該類問題的最佳選擇.啟發(fā)式算法可以劃分為靜態(tài)的和動(dòng)態(tài)的.靜態(tài)啟發(fā)式算法應(yīng)用于所要執(zhí)行的任務(wù)數(shù)量是已知的狀況，動(dòng)態(tài)啟發(fā)式算法適用于任務(wù)動(dòng)態(tài)地達(dá)到系統(tǒng)的情形[11].

3.2.1 靜態(tài)調(diào)度

當(dāng)以下兩種情形同時(shí)出現(xiàn)時(shí)，可用靜態(tài)策略進(jìn)行調(diào)度：

(1)所有任務(wù)在同一時(shí)刻到達(dá)；

(2)當(dāng)每一個(gè)任務(wù)被調(diào)度后，都立即更新虛擬機(jī)可用時(shí)間.

可用于靜態(tài)啟發(fā)式調(diào)度算法有遺傳算法(GA)和模擬退火算法(SA).文獻(xiàn)[12]對(duì)傳統(tǒng)的遺傳算法進(jìn)行了改進(jìn)，提出了一種雙適應(yīng)度的改進(jìn)型遺傳算法，同時(shí)考慮了總?cè)蝿?wù)完成時(shí)間的個(gè)體適應(yīng)度和任務(wù)平均所用時(shí)間的個(gè)體的適應(yīng)度，較好地避免了潛在優(yōu)良基因的丟失、陷入局部收斂.在雙適應(yīng)度遺傳算法和傳統(tǒng)遺傳算法得出的總?cè)蝿?wù)完成時(shí)間相差不大的情況下，雙適應(yīng)度遺傳算法得出的任務(wù)平均完成時(shí)間要明顯少于傳統(tǒng)遺傳算法，從而降低了能耗，達(dá)到節(jié)能的目的.但是，該算法需要進(jìn)化到一定的代數(shù)才能體現(xiàn)其優(yōu)越性，其收斂速度比一般的遺傳算法要慢.文獻(xiàn)[13]采用統(tǒng)計(jì)技術(shù)預(yù)測(cè)任務(wù)執(zhí)行時(shí)間，然后再用模糊控制理論設(shè)置遺傳算法的參數(shù)(收斂速度，適應(yīng)度)，最后使用遺傳算法進(jìn)行迭代，獲得任務(wù)調(diào)度方案.該算法是一種在線模式動(dòng)態(tài)調(diào)度算法，符合云計(jì)算的特性，并且可以均衡虛擬機(jī)的負(fù)載.但是其實(shí)現(xiàn)比較復(fù)雜，性能依賴于概率統(tǒng)計(jì)中預(yù)測(cè)執(zhí)行時(shí)間的準(zhǔn)確性.

3.2.2 動(dòng)態(tài)調(diào)度

在動(dòng)態(tài)任務(wù)調(diào)度中，任務(wù)不是同時(shí)到達(dá)的，而是在一段時(shí)間里以一定的概率到達(dá).在這種任務(wù)到達(dá)的模式下，任務(wù)集中的任務(wù)數(shù)量是變化的，可分配的虛擬機(jī)數(shù)量也隨著變化.動(dòng)態(tài)啟發(fā)式算法可以分成兩種類型：批模式與在線模式.批模式中，任務(wù)到達(dá)后被分配到一個(gè)集合中，在集合中做預(yù)調(diào)度.在線模式中，一旦任務(wù)到達(dá)，就立即給它分配虛擬機(jī)，每個(gè)任務(wù)只能被調(diào)度一次.

3.2.2.1 批模式動(dòng)態(tài)調(diào)度

批模式動(dòng)態(tài)調(diào)度算法有：

（1）痛苦算法：該算法將機(jī)器分配給痛苦值最大的任務(wù).在每次調(diào)度事件中，痛苦值被重新計(jì)算，它等于最早完成時(shí)間和次早完成時(shí)間的差值.對(duì)于任務(wù)Ti，若在最早完成時(shí)間計(jì)劃里的機(jī)器Mk未被映射，則將Mk映射到Ti.否則，假設(shè)Mk已映射到Tj，算法比較任務(wù)Ti和Tj的痛苦值，若Ti的痛苦值較大，則取消對(duì)Tj的映射，將Tj放回任務(wù)集合.任務(wù)集中的每一個(gè)任務(wù)只被考慮一次.

（2）優(yōu)先權(quán)變化的輪詢調(diào)度算法：該算法基于任務(wù)的期限完成時(shí)間進(jìn)行優(yōu)先權(quán)的確定，具有越早期限完成時(shí)間的任務(wù)，其優(yōu)先權(quán)越高.算法每進(jìn)行一輪調(diào)度，都要對(duì)優(yōu)先權(quán)進(jìn)行重新分配，然后基于優(yōu)先權(quán)重新映射虛擬機(jī).優(yōu)先權(quán)高的任務(wù)可以優(yōu)先選擇性能優(yōu)良的虛擬機(jī)，極端情況下甚至可以獨(dú)享虛擬機(jī).

3.2.2.2 在線模式動(dòng)態(tài)調(diào)度

在線模式動(dòng)態(tài)調(diào)度算法有：

（1）交換算法(SA)：它結(jié)合了MCT和MET這兩種啟發(fā)式算法的思想.在最短執(zhí)行時(shí)間算法(MET)中，可能會(huì)將過多的任務(wù)分配到同一個(gè)性能優(yōu)異的虛擬機(jī)中，從而造成負(fù)載不均衡.而最短完成時(shí)間算法(MCT)可以均衡負(fù)載，但不能確保每個(gè)任務(wù)都可以分配至最短執(zhí)行時(shí)間的機(jī)器上.交換算法將兩個(gè)結(jié)合起來，可以只付出一定量額外時(shí)間的同時(shí)，均衡系統(tǒng)負(fù)載.

（2）K百分比最佳算法(KPB)：該算法在調(diào)度任務(wù)時(shí)，只考慮虛擬機(jī)集合里的一個(gè)子集.該子集由任務(wù)執(zhí)行時(shí)間最優(yōu)的前百分之K比例的虛擬機(jī)組成.該算法將任務(wù)映射到性能優(yōu)異的虛擬機(jī)子集中，使其與最短執(zhí)行時(shí)間算法相比，獲得更好的負(fù)載均衡；與最短完成時(shí)間相比，又能獲得更短的執(zhí)行時(shí)間.

3.3 構(gòu)建新的任務(wù)調(diào)度算法模型

一些研究人員根據(jù)云計(jì)算的技術(shù)特性，提出構(gòu)建新的適應(yīng)云計(jì)算需求的任務(wù)調(diào)度算法模型.

文獻(xiàn)[14]將網(wǎng)絡(luò)中虛擬機(jī)使用費(fèi)用按性能從高到低設(shè)置，用戶提交的任務(wù)具有截止時(shí)間.使算法在滿足截止時(shí)間限制的同時(shí)，完成任務(wù)的花費(fèi)最低，滿足了用戶的QoS和性價(jià)比最優(yōu)要求.文章所設(shè)計(jì)的算法只考慮了獨(dú)立型任務(wù)，沒有考慮依賴型任務(wù)，這是不符合云計(jì)算中任務(wù)之間的實(shí)際聯(lián)系的.

文獻(xiàn)[15]采用了社會(huì)學(xué)領(lǐng)域中關(guān)于分配性正義的伯格模型，對(duì)云環(huán)境下的任務(wù)調(diào)度建立雙重公平行約束.從用戶角度，以一般期待完成時(shí)間來約束不同QoS的偏好分類；云服務(wù)方面，以資源分配的評(píng)判函數(shù)進(jìn)行系統(tǒng)公平性的約束.與社會(huì)學(xué)領(lǐng)域的普遍結(jié)論一致，達(dá)到公平的同時(shí)，卻損失了一定的效率.

文獻(xiàn)[16]利用經(jīng)濟(jì)學(xué)領(lǐng)域的博弈論對(duì)具有QoS限制的資源分配進(jìn)行了研究，采用了“兩步走”的方法.第一步：每一個(gè)任務(wù)都獨(dú)自地進(jìn)行問題最優(yōu)化求解，在這一步，不用考慮任務(wù)之間資源分配的相互關(guān)系.第二步：設(shè)計(jì)一個(gè)進(jìn)化機(jī)制，機(jī)制中的博弈算法同時(shí)考慮效率和公平，算法考慮任務(wù)之間的相互關(guān)系，在改變最初的調(diào)度策略的時(shí)候，以盡可能小的效率損失來提升資源分配公平性.最后證明如果資源分配中有可行解的時(shí)候，總是存在著納什均調(diào)度算法結(jié)合起來，設(shè)計(jì)出了一種選擇算法.該算法避免了Min-Min算法面臨少量長(zhǎng)任務(wù)和大量短任務(wù)時(shí)的低效調(diào)度和Max-Min算法面臨少量短任務(wù)和大量長(zhǎng)任務(wù)時(shí)，對(duì)短任務(wù)實(shí)時(shí)性需求不能滿足的缺陷.選擇算法根據(jù)最短執(zhí)行時(shí)間對(duì)任務(wù)進(jìn)行預(yù)處理，然后根據(jù)所得到的數(shù)據(jù)判斷該任務(wù)集應(yīng)采用Min-Min算法還是Max-Min算法.實(shí)驗(yàn)結(jié)果表明，選擇算法性能優(yōu)于Min-Min算法和Max-Min算法，顯然，由于加入了預(yù)處理和判斷函數(shù)，選擇算法的復(fù)雜度有所增加.

除了上述方面以外，專家學(xué)者們還從不同的角度對(duì)云計(jì)算環(huán)境下的任務(wù)調(diào)度進(jìn)行研究.例如：利用層次分析法進(jìn)行資源分配[18]、考慮虛擬機(jī)之間網(wǎng)絡(luò)帶寬的任務(wù)調(diào)度[19]、異構(gòu)多處理器組成的云平臺(tái)中的任務(wù)調(diào)度[20]和基于用戶預(yù)算的任務(wù)調(diào)度[21].文獻(xiàn)[22]根據(jù)云計(jì)算下用戶任務(wù)對(duì)資源需求存在廣泛差異的特點(diǎn)，在考慮資源代價(jià)和計(jì)算性能的條件下提出一種改進(jìn)的基于成本的調(diào)度算法.文獻(xiàn)[23]從用戶的區(qū)分QoS需求和云服務(wù)提供商最大化收益的角度提出一種作業(yè)調(diào)度方法.

還有很多學(xué)者在MapReduce下開展云計(jì)算的任務(wù)調(diào)度研究.MapReduee是云計(jì)算平臺(tái)下的一種編程模型[24]，它作為云計(jì)算的開源項(xiàng)目Hadoop的重要組成部分，在企業(yè)界和學(xué)術(shù)界都有著廣泛應(yīng)用.文獻(xiàn)[25]在云計(jì)算環(huán)境中改進(jìn)MapReduce的調(diào)度，把原來任務(wù)調(diào)度FIFO改為多級(jí)反饋隊(duì)列，既能使高優(yōu)先級(jí)的任務(wù)得到響應(yīng)，又能使短任務(wù)迅速完成.文獻(xiàn)[26]則采用Triple-Queue調(diào)度，把Map階段分解，設(shè)置Map-Shuffle階段，在任務(wù)調(diào)度時(shí)進(jìn)行工作負(fù)載預(yù)處理，分為等待隊(duì)列，CPU受限隊(duì)列，I/O受限隊(duì)列.文獻(xiàn)[27]提出在異構(gòu)型環(huán)境中改進(jìn)MapReduce性能.文獻(xiàn)[28]提出一種在異構(gòu)型環(huán)境里自適應(yīng)的MapReduce調(diào)度算法.

4 云計(jì)算中任務(wù)調(diào)度技術(shù)的研究展望

就目前云計(jì)算中任務(wù)調(diào)度技術(shù)的研究現(xiàn)狀和現(xiàn)有研究存在的一些不足，本節(jié)給出筆者認(rèn)為需要進(jìn)一步研究和解決的問題.

4.1 適應(yīng)用戶任務(wù)動(dòng)態(tài)變更的調(diào)度策略研究

在數(shù)量有限的云資源環(huán)境下對(duì)數(shù)量龐大的用戶任務(wù)進(jìn)行調(diào)度時(shí)，當(dāng)有用戶提交任務(wù)后發(fā)現(xiàn)作業(yè)存在不足需要?jiǎng)h除、撤銷時(shí)，調(diào)度系統(tǒng)如何采取一種有效策略與之適應(yīng)，以避免云資源不必要的浪費(fèi)是值得關(guān)注的問題.這個(gè)問題在云計(jì)算下用戶群越龐大時(shí)，越將頻繁的出現(xiàn)，特別在私有云下資源較緊缺的情形下，更是需要一種適應(yīng)用戶任務(wù)動(dòng)態(tài)變更的調(diào)度策略，以達(dá)到資源的高效管理和使用.但是在現(xiàn)有的云計(jì)算調(diào)度研究中，還沒有適當(dāng)?shù)尼槍?duì)海量任務(wù)數(shù)量的調(diào)度算法.為此，可以針對(duì)云計(jì)算任務(wù)調(diào)度過程中資源動(dòng)態(tài)變化和用戶作業(yè)動(dòng)態(tài)變更的情況，研究用戶作業(yè)動(dòng)態(tài)變更過程中存在著的數(shù)據(jù)依賴關(guān)系，設(shè)計(jì)相應(yīng)的任務(wù)調(diào)度策略.

4.2 啟發(fā)性技術(shù)在云計(jì)算任務(wù)調(diào)度問題中的應(yīng)用

如前所述，云計(jì)算任務(wù)調(diào)度是一個(gè)NP完全問題，為此許多學(xué)者都在關(guān)注啟發(fā)性技術(shù)在云計(jì)算任務(wù)調(diào)度問題中的使用，將一些經(jīng)典啟發(fā)式算法運(yùn)用于任務(wù)調(diào)度中，也取得了不錯(cuò)的效果.然而，云計(jì)算環(huán)境下的作業(yè)（任務(wù)）往往有較大規(guī)模計(jì)算量、不同偏好的作業(yè)組，以及更多的制約條件，因此在特定的云資源環(huán)境選取一個(gè)最優(yōu)的調(diào)度策略仍是一個(gè)棘手的問題.如何根據(jù)云計(jì)算的新特性，對(duì)傳統(tǒng)的啟發(fā)式任務(wù)調(diào)度算法進(jìn)行適當(dāng)?shù)母倪M(jìn)，使之能應(yīng)用到云計(jì)算任務(wù)調(diào)度中，這還需要做進(jìn)一步的深入研究.

4.3 以商業(yè)的視角研究云計(jì)算任務(wù)調(diào)度

云計(jì)算及網(wǎng)格計(jì)算中的傳統(tǒng)調(diào)度系統(tǒng)往往只考慮如何滿足各用戶的QoS要求，卻很少考慮資源提供商的收益最大化問題.實(shí)際上，云計(jì)算中的任務(wù)調(diào)度問題不僅要滿足云計(jì)算用戶的作業(yè)QoS要求，還需要以一種經(jīng)濟(jì)方式高效利用云資源.構(gòu)建出新的任務(wù)調(diào)度算法模型應(yīng)該更多地關(guān)注如何去保障用戶服務(wù)質(zhì)量和用戶與提供商的經(jīng)濟(jì)利益.這里不僅需要對(duì)服務(wù)類型做進(jìn)一步的細(xì)分，綜合考慮網(wǎng)絡(luò)帶寬和通信代價(jià)等因素，使QoS保障和服務(wù)具有較好的性價(jià)比，而且還要充分地考慮使服務(wù)提供商獲得最大化云系統(tǒng)的收益.也就是說，可以從兩個(gè)方面來考慮：一是從云計(jì)算資源使用者角度出發(fā)，綜合地考慮哪個(gè)云計(jì)算資源能滿足用戶作業(yè)計(jì)算的QoS要求（例如作業(yè)完成的預(yù)期時(shí)間，計(jì)算量等），以及用戶需要為云計(jì)算資源所支付的費(fèi)用；二是從云計(jì)算服務(wù)提供商的角度出發(fā)，綜合考慮在滿足用戶作業(yè)QoS約束的前提下，如何在提供云計(jì)算資源時(shí)使供應(yīng)商獲得最大的收益.為此，云計(jì)算中的任務(wù)調(diào)度必須以高效、經(jīng)濟(jì)的策略來滿足用戶不同的需求.目前盡管已有研究人員根據(jù)資源代價(jià)和計(jì)算性能、或者根據(jù)用戶的區(qū)分QoS需求和云服務(wù)提供商最大化收益提出了一些任務(wù)調(diào)度算法，但是這些研究還遠(yuǎn)遠(yuǎn)不夠，需要我們進(jìn)一步拓展.

4.4 其他學(xué)科領(lǐng)域的模型或理論在云計(jì)算任務(wù)調(diào)度中的應(yīng)用

因?yàn)樵朴?jì)算資源由海量高性能計(jì)算機(jī)和商用計(jì)算機(jī)混合組成，具有較強(qiáng)的異構(gòu)性和伸縮性，使得云資源動(dòng)態(tài)多變.另一方面，云用戶提交的作業(yè)也具有各類偏好，如一些任務(wù)偏向于高計(jì)算復(fù)雜度的科學(xué)計(jì)算，屬于計(jì)算型任務(wù)；一些任務(wù)需要對(duì)大型數(shù)據(jù)進(jìn)行存儲(chǔ)，則需要大量的存儲(chǔ)空間，屬于存儲(chǔ)型任務(wù)；一些任務(wù)需要高帶寬接入、通信數(shù)據(jù)量大，屬于帶寬型任務(wù)，等等.因此，應(yīng)該針對(duì)用戶任務(wù)的偏好不同，設(shè)計(jì)區(qū)分服務(wù)的調(diào)度方法，讓有不同類型優(yōu)勢(shì)的資源優(yōu)先分配給相應(yīng)的任務(wù)，可以得到更好的用戶評(píng)價(jià)和反饋，也更符合云計(jì)算的商業(yè)模式.但是，現(xiàn)有的調(diào)度算法并沒有很好的對(duì)其性能的進(jìn)行持續(xù)評(píng)估，資源的選擇存在較大的盲目性和局限性，云計(jì)算的運(yùn)營(yíng)模式也要求云資源分配時(shí)更注重用戶使用的滿意度.因此，如何在動(dòng)態(tài)多變的云資源環(huán)境下分配恰當(dāng)?shù)馁Y源以保證用戶任務(wù)區(qū)分服務(wù)的質(zhì)量是一個(gè)值得研究的問題.

可以把一些其他學(xué)科領(lǐng)域的模型或理論知識(shí)（如經(jīng)濟(jì)學(xué)中的博弈論，社會(huì)學(xué)中的伯格模型等）應(yīng)用到云計(jì)算任務(wù)調(diào)度中，更好地為用戶任務(wù)分配恰當(dāng)?shù)奶摂M資源，同時(shí)又能保證云計(jì)算服務(wù)提供商有效利用云計(jì)算資源和獲得最大收益.例如，可以針對(duì)云計(jì)算資源需求的多樣性與偏好性，綜合地考慮云計(jì)算環(huán)境下用戶QoS和資源參數(shù)更為復(fù)雜的依賴關(guān)系，研究多態(tài)型的演化博弈調(diào)度模型，通過任務(wù)方和資源方的混合博弈，按照服務(wù)類別的劃分進(jìn)行資源分配，依據(jù)用戶反饋評(píng)分或任務(wù)執(zhí)行估計(jì)評(píng)分不斷演化改進(jìn)虛擬機(jī)資源及其所屬種群的各項(xiàng)服務(wù)評(píng)價(jià)，達(dá)到最后博弈均衡.

5 結(jié)束語

云計(jì)算具有資源動(dòng)態(tài)多變、按需提供虛擬化資源、付費(fèi)服務(wù)、用戶群體大、任務(wù)差異大、用戶任務(wù)偏好多樣性等特點(diǎn)，現(xiàn)有的任務(wù)調(diào)度技術(shù)不能很好地適應(yīng)云計(jì)算任務(wù)調(diào)度的需求.因此，任務(wù)調(diào)度策略是云計(jì)算技術(shù)領(lǐng)域的研究熱點(diǎn)之一.本文介紹了云計(jì)算環(huán)境下任務(wù)調(diào)度技術(shù)的特性，對(duì)云計(jì)算任務(wù)調(diào)度技術(shù)的研究進(jìn)展進(jìn)行了較系統(tǒng)的分析和總結(jié)，可以看出，盡管國(guó)內(nèi)外在云計(jì)算任務(wù)調(diào)度技術(shù)方面的研究取得了一些進(jìn)展，但是還要許多不足之處，任務(wù)調(diào)度策略的綜合性能還有待于提高，還有許多工作值得我們?nèi)ヌ剿骱脱芯?

[1]M. Armbrust, A. Fox, R. Griffith et al. Above the Clouds:A Berkeley View of Cloud Computing[R]. University of California, Berkeley: Technical Report(UCB/EECS-2009-28), February 10, 2009

[2]張希翔. 云計(jì)算環(huán)境下任務(wù)調(diào)度算法的研究[D].碩士學(xué)位論文,南寧：廣西大學(xué), 2011

[3]S. Nagadevi, K.Satyapriya and D.Malathy. A Survey on Economic Cloud Schedulers for Optimized Task Scheduling[J].International Journal of Advanced Engineering Technology, 2013, 4(1):58-62

[4]W. Yao, B. Li and J. You.Genetic Scheduling on Minimal Processing Elements in the Grid[M]. Lecture Notes in Computer Sciences 2557, Springer-Verlag Berlin, Berlin,2002. pp.465-476

[5]遆鳴，陳俊杰，強(qiáng)彥.基于模擬退火的Map Reduce調(diào)度算法[J].計(jì)算機(jī)工程, 2012,38(19):45-48

[6]X. He, X. Sun and G..Laszewski. A QoS Guided Min-Min Heuristic for Grid Task Scheduling [J]. Journal of Computer Science and Technology , 2003, 18(4): 442-451

[7]王登科，李忠.基于粒子群優(yōu)化與蟻群優(yōu)化的云計(jì)算任務(wù)調(diào)度算法[J].計(jì)算機(jī)應(yīng)用與軟件, 2013，30(1)：290-293

[8]M. Abdeyazdan, S. Parsa and A. M. Rahmani. Task Graph Pre-scheduling, Using Nash Equilibrium in Game Theory[J].The Journal of Supercomputing, 2013, 64 (1):177-203

[9]張希翔，李陶深.云計(jì)算下適應(yīng)用戶任務(wù)動(dòng)態(tài)變更的調(diào)度算法[J].華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版),2012,(S1):163-169

[10]M. A. Arfeen, K. Pawlikowski and A. Willig. A Framework for Resource Allocation Strategies in Cloud Computing Environment[C]. Proceeding of 2011 IEEE 35th Annual Computer Software and Applications Conference Workshops , Munich , Germany, July 18-22, 2011,pp.261-266

[11]P. Salot. A Survey of Various Scheduling Algorithm in Cloud Computing Environment[J]. International Journal of Research in Engineering and Technology, 2013,2(2):131-135

[12]李建峰，彭艦.云計(jì)算環(huán)境下基于改進(jìn)遺傳算法的任務(wù)調(diào)度算法[J].計(jì)算機(jī)應(yīng)用, 2011, 31(1):184-186

[13]S. Tayal. Tasks Scheduling Optimization for the Cloud Computing Systems[J].International Journal of Advanced Engineering Sciences and Technologies, 2011,5(2):111-115

[14]帥志偉.一種改進(jìn)型 Min-Min調(diào)度算法[D].碩士學(xué)位論文，南昌：華東交通大學(xué)，2009

[15]趙春燕.云環(huán)境下作業(yè)調(diào)度算法研究與實(shí)現(xiàn)[D].碩士學(xué)位論文,北京：北京交通大學(xué), 2009

[16]G. Wei, V. Vasilakos, Z. Yao and N. Xiong. A Game-Theoretic Method of Fair Resource Allocation for Cloud Computing Services[J]. The Journal of Supercomputing,2010, 54(2):252-269

[17]K. Etminani and M. Naghibzadeh. A Min-Min Max-Min Selective Algorithm for Grid Task Scheduling [C].Proceedings of The Third IEEE/IFIP International Conference in Central Asia on on Internet, Tashkent ,Uzbekistan, September 26-28,2007, pp.1-7

[18]D. Ergy, G. Kou, Y. Peng, Y. Shi and Y. Shi.The Analytic Hierarchy Process: Task Scheduling and Resource Allocation in Cloud Computing Environment[J].The Journal of Supercomputing, 2013,64(3):835-848

[19]W. Lin, C. Liang, Z. Wang and R. Buyya. Bandwidthaware Divisible Task Scheduling for Cloud Computing[J].Software: Practice and Experiment, 2014, 44(2): 163-174

[20]C.Augonnet, S.Thibault, R.Namyst and PA.Wacrenier.StarPU: A Unified Platform for Task Scheduling on Heterogeneous Multicore Architectures[J].Concurrency and Computation: Practice and Experience, 2011,23(2):187-198

[21]A. M. Oprescu, T. Kielmann and H. Leahu. Budget Estimation and Control for Bag-of-Tasks Scheduling in Clouds [J].Parallel Processing Letters, 2011, 21(2):219-243

[22]S. Selvarani, G. S. Sadhasivam. Improved cost-based algorithm for task scheduling in cloud computing[C].Proceedings of 2010 IEEE International Conference on Computational Intelligence and Computing Research,Coimbatore, India, December 28-29, 2010, pp. 620-624.

[23]L. Li. An Optimistic Differentiated Service Job Scheduling System for Cloud Computing Service Users and Providers[C]. Proceedings of 2009 Third International Conference on Multimedia and Ubiquitous Engineering,Qingdao, China, June 4-6, 2009, pp.295–299.

[24]J. Dean, S. Ghemawat. MapReduce: Simplified Data Processing on Large Clusters[J]. Communications of the ACM, 2008, 51(1): 107-113.

[25]S. Gao, T. Huang, G. Gan. An improved schedule of MapReduce programming environment in cloud computing[C]. Proceedings of Intelligent Computing and Integrated Systems (ICISS), Guilin, China, October 22-24, 2010, pp.665 – 668.

[26]Chao Tian, Haojie Zhou, Yongqiang He, Li Zha. A Dynamic MapReduce Scheduler for Heterogeneous Workloads[C]. Proceedings of 2009 Eighth International Conference on Grid and Cooperative Computing ,Lanzhou, China, August 27-29, 2009, pp.218 – 224.

[27]M. Zaharia, A. Konwinski, A. D. Joseph, R. et al.Improving Mapreduce Performance in Heterogeneous Enviroments[C].Proceedings of the 8th USENIX Symposium on Operating systems design and implementation , San Diego, California, USA, December 8-10,2008, pp.29-42.

[28]Q. Chen, D. Zhang, M. Guo, et al. SAMR: A Selfadaptive MapReduce Scheduling Algorithm in Heterogeneous Environment[C]. Proceedings of 2010 IEEE 10th International Conference on Computer and Information Technology, Bradford, United kingdom, June 29-July 1, 2010, pp.2376-2743.