田倬璟，黃震春，張益農(nóng)

1.北京聯(lián)合大學(xué) 北京市信息服務(wù)工程重點(diǎn)實(shí)驗(yàn)室，北京100101

2.清華大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系，北京100084

3.國(guó)家超級(jí)計(jì)算無(wú)錫中心，江蘇 無(wú)錫214072

4.北京信息科學(xué)與技術(shù)國(guó)家研究中心，北京100084

5.北京聯(lián)合大學(xué) 城市軌道交通與物流學(xué)院，北京100101

云計(jì)算利用互聯(lián)網(wǎng)和虛擬機(jī)技術(shù)，通過(guò)少量管理工作，以虛擬化形式提供隨時(shí)可用、可重新配置和無(wú)處不在的計(jì)算資源，在這種范例中，用戶(hù)利用互聯(lián)網(wǎng)和遠(yuǎn)程數(shù)據(jù)中心來(lái)運(yùn)行應(yīng)用程序和存儲(chǔ)數(shù)據(jù)。云計(jì)算技術(shù)按使用服務(wù)付費(fèi)的方式為用戶(hù)提供了高效可擴(kuò)展的計(jì)算能力，消除了用戶(hù)硬件配置維護(hù)成本，目前已發(fā)展成為一種流行且高效的計(jì)算范例[1]。

云計(jì)算環(huán)境是一個(gè)典型的分布式計(jì)算環(huán)境，任務(wù)調(diào)度是指在IaaS 層，根據(jù)任務(wù)和資源的實(shí)際情況，將任務(wù)分配到最佳資源上進(jìn)行執(zhí)行的過(guò)程。在云計(jì)算環(huán)境中，任務(wù)的類(lèi)型、狀態(tài)、數(shù)量隨時(shí)變化，資源具有異構(gòu)性和擴(kuò)展性，可自由組合為不同的任務(wù)提供服務(wù)。性能良好的任務(wù)調(diào)度算法可以?xún)?yōu)化服務(wù)質(zhì)量參數(shù)（QoS），如最大完工時(shí)間、響應(yīng)時(shí)間、吞吐量、資源利用率、任務(wù)拒絕率、可靠性、可伸縮性、能耗、執(zhí)行成本等，并可以在不違反服務(wù)級(jí)別協(xié)議（SLA）的前提下，考慮各類(lèi)約束，例如截止日期、優(yōu)先級(jí)、經(jīng)濟(jì)成本等，實(shí)現(xiàn)用戶(hù)的硬指標(biāo)約束，同時(shí)可避免負(fù)載不均衡的發(fā)生，這是一個(gè)典型的NP 困難問(wèn)題。目前，隨著用戶(hù)應(yīng)用程序?qū)υ茢?shù)據(jù)中心計(jì)算資源需求的逐漸增加，資源爭(zhēng)用、服務(wù)中斷、交互能力缺乏、QoS 性能降低、SLA 違反等問(wèn)題日益嚴(yán)重；此外，傳統(tǒng)單個(gè)云環(huán)境存在資源不足，服務(wù)部署易受故障影響，導(dǎo)致服務(wù)中斷和低可用性，因此促使產(chǎn)生了跨云環(huán)境（inter-cloud）來(lái)解決此類(lèi)問(wèn)題。

任務(wù)調(diào)度算法的類(lèi)型根據(jù)不同的分類(lèi)方式具有不同的定義。根據(jù)任務(wù)的類(lèi)型，可把任務(wù)調(diào)度分為獨(dú)立任務(wù)調(diào)度和工作流調(diào)度，根據(jù)任務(wù)調(diào)度算法的特點(diǎn)，可將算法分為啟發(fā)式、元啟發(fā)式和混合式，根據(jù)任務(wù)運(yùn)行的環(huán)境，可分為單云環(huán)境任務(wù)調(diào)度和跨云環(huán)境任務(wù)調(diào)度。

獨(dú)立任務(wù)彼此之間沒(méi)有關(guān)聯(lián)關(guān)系，只需按照用戶(hù)要求分配到指定虛擬機(jī)即可，而工作流的任務(wù)之間存在執(zhí)行順序，運(yùn)行較為復(fù)雜。通常工作流由有向無(wú)環(huán)圖（DAG）表示，節(jié)點(diǎn)表示任務(wù)所需的計(jì)算過(guò)程，邊表示任務(wù)之間的數(shù)據(jù)通信，除了一般商業(yè)應(yīng)用程序生成的業(yè)務(wù)工作流（business workflow）之外，天文學(xué)、生物信息學(xué)、地震科學(xué)和物理學(xué)等領(lǐng)域建立的科學(xué)應(yīng)用程序構(gòu)成了科學(xué)工作流（scientific workflow），典型科學(xué)工作流包括Montage、LIGO、CyberShake、SIPHT 和Epigenomics 等，獨(dú)立任務(wù)和科學(xué)工作流都屬于單次執(zhí)行作業(yè)。

啟發(fā)式算法是一類(lèi)基于直觀或經(jīng)驗(yàn)構(gòu)造的算法，其在可接受的計(jì)算時(shí)間和空間下給出待解決的組合優(yōu)化問(wèn)題的一個(gè)可行解，但無(wú)法保證結(jié)果最優(yōu)，且調(diào)度周期較長(zhǎng)。元啟發(fā)式算法是隨機(jī)算法和局部搜索算法結(jié)合的產(chǎn)物，這些算法獨(dú)立于問(wèn)題，尋找NP困難問(wèn)題的近似最優(yōu)解，針對(duì)大范圍尋優(yōu)問(wèn)題提供搜索流程，一般需要至少一個(gè)初始可行解，在預(yù)定義的搜索空間高效迭代搜索以改進(jìn)解，這類(lèi)算法往往具有較高的時(shí)間復(fù)雜度，但由于具有較高的解的精度，整體調(diào)度周期縮短了?；旌鲜剿惴ㄊ莾煞N以上算法結(jié)合的算法統(tǒng)稱(chēng)，這類(lèi)算法在一定程度上降低了局部最優(yōu)解的發(fā)生率，但時(shí)間復(fù)雜度更高，且性能結(jié)果差異較大。

當(dāng)一個(gè)云以即付即用的方法對(duì)公眾開(kāi)放使用時(shí)，它被稱(chēng)為公有云，當(dāng)一個(gè)云屬于企業(yè)或組織，不對(duì)公眾開(kāi)放使用時(shí)，被稱(chēng)為私有云，云環(huán)境包含大量獨(dú)立、異構(gòu)的私有云和公有云，這些彼此沒(méi)有聯(lián)系的云構(gòu)成了單云環(huán)境。隨著計(jì)算需求的逐漸增大，單云環(huán)境無(wú)法滿(mǎn)足龐大的計(jì)算需求，為了集成聚合云服務(wù)以實(shí)現(xiàn)無(wú)縫的基礎(chǔ)設(shè)施，提出了跨云環(huán)境，包括混合云（Hybrid Cloud）、聯(lián)盟云（Federated Cloud）和多云（Multi Cloud）。

已存在一些相關(guān)的研究調(diào)度[2-6]，但并不完全針對(duì)任務(wù)調(diào)度，往往和資源調(diào)度合并闡述，而且著重點(diǎn)并不是任務(wù)調(diào)度自身的特點(diǎn)和環(huán)境適應(yīng)性特征。本文針對(duì)獨(dú)立任務(wù)和科學(xué)工作流對(duì)任務(wù)調(diào)度按照單云環(huán)境與跨云環(huán)境進(jìn)行分類(lèi)討論，在單云環(huán)境中梳理了現(xiàn)有的不同種類(lèi)的任務(wù)調(diào)度算法類(lèi)型，并選取相關(guān)代表文獻(xiàn)進(jìn)行總結(jié)分析；在跨云環(huán)境中，結(jié)合跨云環(huán)境的特征，探討任務(wù)調(diào)度算法在不同云環(huán)境下的適應(yīng)性特征，并對(duì)部分跨云環(huán)境下的任務(wù)算法文獻(xiàn)進(jìn)行總結(jié)分析；最后，討論任務(wù)調(diào)度算法研究中存在的不足和未來(lái)研究趨勢(shì)，為云計(jì)算環(huán)境下任務(wù)調(diào)度的進(jìn)一步研究提供參考。

1 單云任務(wù)調(diào)度

單云任務(wù)調(diào)度的主要流程為用戶(hù)通過(guò)服務(wù)接口向云計(jì)算系統(tǒng)提交作業(yè)請(qǐng)求，任務(wù)管理器收到作業(yè)請(qǐng)求后，對(duì)其進(jìn)行分類(lèi)、排序等預(yù)處理，分為獨(dú)立任務(wù)隊(duì)列和工作流任務(wù)隊(duì)列，并根據(jù)成本、執(zhí)行時(shí)間、截止時(shí)間等參數(shù)對(duì)任務(wù)進(jìn)行排序，任務(wù)調(diào)度器收到處理過(guò)的任務(wù)集后，通過(guò)考慮了各類(lèi)QoS參數(shù)的算法按要求得出從任務(wù)到資源的分配方案，資源信息服務(wù)器（RIS）根據(jù)分配方案將任務(wù)分配到指定的虛擬機(jī)資源上執(zhí)行，同時(shí)會(huì)監(jiān)視和收集所有任務(wù)和資源的信息，并將其發(fā)送給任務(wù)調(diào)度器，以便任務(wù)調(diào)度器優(yōu)化后續(xù)任務(wù)分配，負(fù)載均衡器負(fù)責(zé)對(duì)已經(jīng)分配給資源上的任務(wù)進(jìn)行二次分配，以防資源負(fù)載過(guò)重，流程如圖1所示。而云內(nèi)任務(wù)調(diào)度算法主要分為啟發(fā)式、元啟發(fā)式和混合式三大類(lèi)。

圖1 單云環(huán)境任務(wù)調(diào)度流程

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

啟發(fā)式任務(wù)調(diào)度分為靜態(tài)調(diào)度和動(dòng)態(tài)調(diào)度兩大類(lèi)。在靜態(tài)調(diào)度中，所有任務(wù)在調(diào)度之前都是已知的，并將它們靜態(tài)分配給虛擬資源；在動(dòng)態(tài)調(diào)度方法中，任務(wù)本質(zhì)上是動(dòng)態(tài)的，在這里，任務(wù)在不同的時(shí)間點(diǎn)到達(dá)，動(dòng)態(tài)調(diào)度可分為在線(xiàn)模式和批處理模式，在線(xiàn)模式下，任務(wù)一經(jīng)到達(dá)系統(tǒng)就會(huì)立即分配，批處理模式下，任務(wù)被作為一個(gè)組進(jìn)行收集，并在預(yù)定義的時(shí)間進(jìn)行調(diào)度。啟發(fā)式算法包括min-min、max-min、先來(lái)先服務(wù)（FCFS）、最短作業(yè)優(yōu)先（SJF）、時(shí)間片輪詢(xún)（RR）、最小執(zhí)行時(shí)間（MCT）、最小完成時(shí)間（MET）、機(jī)會(huì)負(fù)載均衡（OLB）[7]、爬山算法、sufferage算法[8]、異構(gòu)最早完成時(shí)間（HEFT）[9-10]等。近年來(lái)，也出現(xiàn)了新的方法，如主成分分析[11]。

獨(dú)立任務(wù)的靜態(tài)調(diào)度算法包含一些基本簡(jiǎn)單策略，如FCFS、RR、SJF，而動(dòng)態(tài)調(diào)度算法中，min-min、maxmin 和動(dòng)態(tài)RR 是批處理模式的算法，MCT、MET、OLB屬于在線(xiàn)模式。FCFS、min-min、max-min目前一般為云仿真平臺(tái)的默認(rèn)調(diào)度算法，由于云環(huán)境異構(gòu)任務(wù)動(dòng)態(tài)的特點(diǎn)，動(dòng)態(tài)調(diào)度較為適應(yīng)于云環(huán)境，此外，HEFT是適應(yīng)于工作流調(diào)度的算法類(lèi)型。

1.2 元啟發(fā)式及混合式任務(wù)調(diào)度

云環(huán)境中存在著各式各樣的元啟發(fā)式算法，如粒子群優(yōu)化（PSO）[12-13]、蟻群優(yōu)化（ACO）[14]、差分進(jìn)化算法（DE）[15]、遺傳算法（GA）[16]、模擬退火（SA）、禁忌搜索（TSA）、人工蜂群（ABC）[17]、細(xì)菌覓食優(yōu)化（BFO）[18]、聯(lián)賽冠軍算法（LCA）[19]、蝙蝠優(yōu)化（BAT）[20]、貓群優(yōu)化（CSO）[21-22]、共生生物搜索（SOS）[23]、螢火蟲(chóng)優(yōu)化算法（FAO）[24]、布谷鳥(niǎo)搜索（CS）[25]、和聲搜索（HS）、獅子優(yōu)化（LOA）[26]、蛾類(lèi)搜索（MSA）[27]、灰狼優(yōu)化算法（GWO）[28]、引力搜索算法（GSA）[29]、智能水滴算法（IWD）[30]等。

目前元啟發(fā)式算法研究的重點(diǎn)是如何平衡局部搜索與全局搜索，有效避免局部最優(yōu)解，這些算法一般分為兩大類(lèi)：群體智能優(yōu)化與隨機(jī)搜索優(yōu)化。群體智能優(yōu)化算法主要模擬了昆蟲(chóng)、獸群、鳥(niǎo)群和魚(yú)群等群體的行為，這些群體按照一種合作方式尋找食物，群體中的每個(gè)成員通過(guò)學(xué)習(xí)它自身的經(jīng)驗(yàn)和其他成員的經(jīng)驗(yàn)來(lái)不斷地改變搜索方向，是一類(lèi)很常用的分布式問(wèn)題解決策略，在云環(huán)境中任務(wù)調(diào)度研究的有PSO、ACO、ABC、BFO、SOS、CSO、FAO、CS、LOA、MSA、GWO、GSA、BAT、IWD 等的各類(lèi)優(yōu)化。而隨機(jī)搜索優(yōu)化方向上，在傳統(tǒng)的局部搜索與全局搜索的基礎(chǔ)上，修改搜索方式的同時(shí)添加了隨機(jī)算法，試圖避免局部最優(yōu)，在云環(huán)境中任務(wù)調(diào)度研究的有GA、SA、TSA、DE、LCA、HS 等算法的優(yōu)化。元啟發(fā)式算法針對(duì)獨(dú)立任務(wù)和工作流任務(wù)都提出了性能較優(yōu)的任務(wù)調(diào)度解決方案。

由于單獨(dú)的調(diào)度算法通常無(wú)法很好地滿(mǎn)足實(shí)際任務(wù)調(diào)度需求，因此目前混合了多種算法的任務(wù)調(diào)度已成為重要的研究方法。最新提出的混合任務(wù)調(diào)度算法有文獻(xiàn)[31-34]。這些優(yōu)化算法中有啟發(fā)式算法與元啟發(fā)式算法的混合，也有兩種或兩種以上元啟發(fā)式算法的結(jié)合，經(jīng)過(guò)實(shí)驗(yàn)驗(yàn)證，這些算法在不同程度上獲得了較好的性能結(jié)果。

1.3 單云環(huán)境任務(wù)調(diào)度總結(jié)分析

表1對(duì)現(xiàn)有任務(wù)調(diào)度算法類(lèi)型進(jìn)行了梳理總結(jié)，分析了其優(yōu)點(diǎn)和不足。由于任務(wù)調(diào)度是在網(wǎng)格計(jì)算、分布式計(jì)算任務(wù)調(diào)度基礎(chǔ)上發(fā)展起來(lái)的，因此存在大量各式各樣的算法類(lèi)型優(yōu)化方法，PSO是較為熱門(mén)的一個(gè)算法類(lèi)型，其又細(xì)分為標(biāo)準(zhǔn)PSO、多目標(biāo)PSO、離散PSO、二進(jìn)制PSO、混合PSO，而B(niǎo)AT、CSO是最近比較熱門(mén)的研究方向，LOA、GWO 提出時(shí)間不久，具有較大的發(fā)展空間。通過(guò)列表可以看出，CS、LOA、IWD 目前沒(méi)有針對(duì)云環(huán)境任務(wù)調(diào)度的具體性能評(píng)估，有待進(jìn)一步驗(yàn)證，此外由于性能問(wèn)題，SA、TSA、HS多用于混合算法。

表2 對(duì)上述所列云內(nèi)任務(wù)調(diào)度算法部分典型研究文獻(xiàn)進(jìn)行分析總結(jié)。云內(nèi)任務(wù)調(diào)度算法研究比較廣泛，存在許多針對(duì)獨(dú)立任務(wù)和工作流使用不同算法類(lèi)型對(duì)QoS進(jìn)行優(yōu)化的方法，核心優(yōu)化目標(biāo)為最大完工時(shí)間和貨幣成本，此外，資源利用率、負(fù)載均衡、安全性、截止日期、能耗等指標(biāo)也成為了重點(diǎn)優(yōu)化目標(biāo)。通過(guò)列表可以看出，文獻(xiàn)[33]在減少最大完工時(shí)間和成本的同時(shí)實(shí)現(xiàn)了較好的負(fù)載均衡，文獻(xiàn)[7-8，12，33]實(shí)現(xiàn)了資源利用率的提升，文獻(xiàn)[15，33]考慮了能耗問(wèn)題，文獻(xiàn)[9]考慮了安全性問(wèn)題和任務(wù)的截止日期；由于任務(wù)調(diào)度需要同時(shí)優(yōu)化多個(gè)指標(biāo)，因此多目標(biāo)任務(wù)調(diào)度算法的研究目前已比較普遍，例如文獻(xiàn)[7-9，12，31]均采用多目標(biāo)函數(shù)進(jìn)行優(yōu)化；此外，對(duì)部分目標(biāo)建立約束也是一種優(yōu)化方法，例如文獻(xiàn)[9，16]；絕大部分研究都是在仿真環(huán)境中進(jìn)行測(cè)試的，但也有在真實(shí)環(huán)境中進(jìn)行測(cè)試的研究，如文獻(xiàn)[9，33]；同時(shí)，神經(jīng)網(wǎng)絡(luò)、強(qiáng)化學(xué)習(xí)等人工智能算法也開(kāi)始應(yīng)用于任務(wù)調(diào)度的研究，如文獻(xiàn)[10，33]。自適應(yīng)優(yōu)化也被應(yīng)用于任務(wù)調(diào)度優(yōu)化，如文獻(xiàn)[15]。目前云內(nèi)任務(wù)調(diào)度的研究在繼續(xù)關(guān)注基本QoS指標(biāo)的情況下，重點(diǎn)關(guān)注優(yōu)化負(fù)載均衡、能耗等性能指標(biāo)，并且人工智能方法已逐步應(yīng)用到任務(wù)調(diào)度排序、節(jié)點(diǎn)預(yù)測(cè)過(guò)程中，但在性能提高的同時(shí)，也提升了復(fù)雜性。

表1 云內(nèi)任務(wù)調(diào)度算法類(lèi)型總結(jié)

表2 云內(nèi)任務(wù)調(diào)度算法研究文獻(xiàn)總結(jié)

2 跨云任務(wù)調(diào)度

隨著用戶(hù)計(jì)算需求的逐漸增加，單一的云環(huán)境無(wú)法滿(mǎn)足計(jì)算需求，因此出現(xiàn)了跨云計(jì)算環(huán)境。這類(lèi)環(huán)境被定義為為了保證服務(wù)質(zhì)量，例如服務(wù)的性能和可用性，通過(guò)不同云供應(yīng)商的云系統(tǒng)之間的互操作，按需重新分配資源和轉(zhuǎn)移負(fù)載，這種互操作基于用戶(hù)對(duì)服務(wù)質(zhì)量的需求和云供應(yīng)商對(duì)SLA的協(xié)調(diào)，并且使用能夠互相通信的標(biāo)準(zhǔn)接口[35]?？缭骗h(huán)境主要分為兩大類(lèi)，聯(lián)盟云環(huán)境和多云環(huán)境。當(dāng)一組云供應(yīng)商彼此愿意互連它們的基礎(chǔ)設(shè)施以實(shí)現(xiàn)共享資源時(shí)，就構(gòu)成了聯(lián)盟云環(huán)境，當(dāng)用戶(hù)可以使用多個(gè)獨(dú)立的云，但這些云服務(wù)云供應(yīng)商彼此之間并不互連和共享它們的基礎(chǔ)設(shè)施，稱(chēng)為多云環(huán)境[36]。此外，混合云被定義為兩個(gè)或多個(gè)私有云或公有云的組合，根據(jù)部署模型連接各類(lèi)云，一般用于當(dāng)本地資源不足時(shí)使用外部資源的云爆發(fā)情況，因此也屬于多云類(lèi)型。在跨云環(huán)境中，代理（broker）是安裝在用戶(hù)端專(zhuān)門(mén)進(jìn)行資源分配管理和任務(wù)調(diào)度及部署的組件，由于跨云環(huán)境中每個(gè)云數(shù)據(jù)中心都有大量的物理資源，它們被虛擬化形成了一個(gè)虛擬資源池，為了實(shí)現(xiàn)跨云調(diào)度，使用代理與每個(gè)云供應(yīng)商進(jìn)行通信，屏蔽通信的異構(gòu)性，生成統(tǒng)一的資源描述目錄和通信接口提供給用戶(hù)，當(dāng)用戶(hù)向代理發(fā)送請(qǐng)求執(zhí)行任務(wù)時(shí)，代理首先查看資源目錄，然后根據(jù)調(diào)度算法將任務(wù)分配給不同的虛擬機(jī)，接下來(lái)，根據(jù)用戶(hù)的服務(wù)質(zhì)量要求將虛擬機(jī)分配到合適的數(shù)據(jù)中心，這里的調(diào)度分為全局調(diào)度和局部調(diào)度，全局調(diào)度由代理進(jìn)行，主要處理數(shù)據(jù)遷移，局部調(diào)度由云數(shù)據(jù)中心進(jìn)行，主要處理具體的任務(wù)分配。

2.1 混合云環(huán)境任務(wù)調(diào)度

在混合云環(huán)境中，公有云提供了一個(gè)公共接口，用于在其專(zhuān)用基礎(chǔ)設(shè)施中創(chuàng)建和管理虛擬機(jī)實(shí)例，在私有云內(nèi)部，用戶(hù)接口組件用來(lái)接收用戶(hù)應(yīng)用程序任務(wù)請(qǐng)求，任務(wù)被發(fā)送給請(qǐng)求管理器進(jìn)行管理，資源監(jiān)控組件監(jiān)視云資源池信息。任務(wù)調(diào)度算法分配任務(wù)給私有云或公有云，旨在實(shí)現(xiàn)利潤(rùn)最大化，在這個(gè)過(guò)程中，任務(wù)調(diào)度器從請(qǐng)求管理器、資源監(jiān)視器和用戶(hù)接口收集調(diào)度數(shù)據(jù)，然后決定每個(gè)任務(wù)分配給私有云還是公有云，如果任務(wù)需要分配給公有云，公有云的定價(jià)模型信息通過(guò)公共接口發(fā)送給任務(wù)調(diào)度器，以便決策選取具體的公有云[35]。由于該云環(huán)境不需要正式的跨云協(xié)議，實(shí)現(xiàn)難度較小，發(fā)展較為成熟，目前已成為企業(yè)用云的主要形式。

混合云任務(wù)調(diào)度研究雖不及傳統(tǒng)單云環(huán)境任務(wù)調(diào)度研究廣泛，但也有較多研究，如文獻(xiàn)[37-41]。文獻(xiàn)[37]針對(duì)混合云，提出了采用整數(shù)規(guī)劃模型的自適應(yīng)學(xué)習(xí)PSO 的任務(wù)調(diào)度算法，在該算法中，在速度更新階段采用四種更新策略自適應(yīng)地更新每個(gè)粒子的速度，以保證其多樣性和魯棒性，仿真實(shí)驗(yàn)表明，該算法與標(biāo)準(zhǔn)PSO相比，結(jié)果證明該算法可以提高云供應(yīng)商的利潤(rùn)。

文獻(xiàn)[38]針對(duì)混合云中時(shí)延約束的任務(wù)，在考慮私有云和公有云成本最小化的情況下，提出了一種時(shí)分任務(wù)調(diào)度算法TTSA，將任務(wù)有效地分配給公有云和私有云，在TTSA 的每次迭代中，將成本最小化問(wèn)題建模為混合整數(shù)線(xiàn)性規(guī)劃，并采用混合SA 和PSO 的調(diào)度算法進(jìn)行求解，仿真實(shí)驗(yàn)結(jié)果表明，與現(xiàn)有的調(diào)度策略相比，TTSA產(chǎn)生的最優(yōu)或近似最優(yōu)調(diào)度策略可以在滿(mǎn)足任務(wù)時(shí)延約束的同時(shí)，提高吞吐量，降低私有云成本。

文獻(xiàn)[39]針對(duì)混合云中的科學(xué)工作流多目標(biāo)調(diào)度問(wèn)題，提出了一種基于NSGAII的非支配排序遺傳算法，提出了兩種執(zhí)行模式：（1）在最大完工時(shí)間和成本之間做權(quán)衡，以提高帕累托前沿（pareto front）質(zhì)量的累加法；（2）增量式執(zhí)行，以成本為驅(qū)動(dòng)在目標(biāo)空間得到帕累托前沿解的多樣性。此外設(shè)計(jì)了一種編碼結(jié)構(gòu)，對(duì)調(diào)度解決方案進(jìn)行建模，并對(duì)其應(yīng)用的遺傳算子進(jìn)行開(kāi)發(fā)。在多個(gè)常見(jiàn)科學(xué)工作流中進(jìn)行仿真實(shí)驗(yàn)表明，與經(jīng)典的NSGAII 算法相比，該算法在成本和最大完工時(shí)間方面有顯著改進(jìn)。

文獻(xiàn)[40]針對(duì)混合云提出了兩種兼顧完工時(shí)間和貨幣成本的工作流調(diào)度算法，第一種是基于截止時(shí)間約束的成本優(yōu)化的單目標(biāo)混合云中工作流調(diào)度算法DCOH，在DCOH 的基礎(chǔ)上，提出了一種以最大完工時(shí)間和貨幣成本為目標(biāo)的混合云多目標(biāo)工作流調(diào)度優(yōu)化算法MOH，仿真結(jié)果表明，與現(xiàn)有算法相比，DCOH 可以很好地為用戶(hù)減少貨幣成本，MOH 可以提供很好的成本與完工時(shí)間協(xié)調(diào)方案。

表3 對(duì)上述所列文獻(xiàn)中研究的混合云任務(wù)調(diào)度算法進(jìn)行了總結(jié)。混合云環(huán)境中的任務(wù)調(diào)度算法研究往往是結(jié)合混合云特征對(duì)云內(nèi)經(jīng)典算法進(jìn)行修改優(yōu)化，而其優(yōu)化的QoS指標(biāo)往往集中在最大完工時(shí)間和成本，但部分文獻(xiàn)如文獻(xiàn)[38]也考慮了任務(wù)延遲約束，文獻(xiàn)[37]考慮了資源利用率，文獻(xiàn)[40]考慮了截止日期約束，此外也出現(xiàn)了基于混合云的多目標(biāo)任務(wù)調(diào)度算法研究，如文獻(xiàn)[39]，以及結(jié)合混合云特點(diǎn)對(duì)吞吐量進(jìn)行優(yōu)化，以減少最大完工時(shí)間，如文獻(xiàn)[38]。特別的，文獻(xiàn)[40]將其算法在真實(shí)云環(huán)境中進(jìn)行了測(cè)試。但也正如這些文獻(xiàn)提到的那樣，由于執(zhí)行時(shí)間變化，執(zhí)行延遲這些會(huì)影響最大完工時(shí)間的指標(biāo)尚未得到很好的解決，目前負(fù)載均衡、能耗、安全性這些指標(biāo)的優(yōu)化在混合云中研究很不充分。

表3 混合云任務(wù)調(diào)度算法研究文獻(xiàn)總結(jié)

2.2 多云環(huán)境任務(wù)調(diào)度

多云環(huán)境由多個(gè)不同的IaaS云服務(wù)供應(yīng)商組成，這些供應(yīng)商提供不同價(jià)格和性能的虛擬機(jī)，但彼此之間相互獨(dú)立互不通信，為了將其整合以利用資源，需要針對(duì)每一個(gè)云供應(yīng)商設(shè)計(jì)相應(yīng)的API接口以實(shí)現(xiàn)通信，或者用戶(hù)自行搭建工作負(fù)載管理程序以滿(mǎn)足任務(wù)調(diào)度需求。雖然這種云環(huán)境導(dǎo)致了額外的開(kāi)發(fā)成本，但可以防止數(shù)據(jù)丟失和減少局部組件故障而停機(jī)的風(fēng)險(xiǎn)，避免云供應(yīng)商鎖定，具有高可伸縮性，此外由于選擇性的增加，任務(wù)執(zhí)行成本減少了[42]。在多云環(huán)境中，每個(gè)云平臺(tái)上都有一個(gè)資源管理器實(shí)時(shí)向用戶(hù)發(fā)送當(dāng)前的虛擬機(jī)資源情況，用戶(hù)通過(guò)統(tǒng)一的API接口或外部代理獲得不同云平臺(tái)發(fā)送過(guò)來(lái)的資源信息，根據(jù)自身任務(wù)情況，將任務(wù)分段傳輸給不同的云進(jìn)行處理計(jì)算。多云環(huán)境下任務(wù)調(diào)度研究不及混合云環(huán)境廣泛，國(guó)際上存在部分質(zhì)量較高的文獻(xiàn)如文獻(xiàn)[42-45]，國(guó)內(nèi)研究的有文獻(xiàn)[46]，它們從不同的角度進(jìn)行了優(yōu)化。

文獻(xiàn)[42]針對(duì)多云環(huán)境，提出了三種調(diào)度算法，分別是最小完成云（MCC）、中位數(shù)最大（MEMAX）和云min-max 歸一化（CMMN），MCC 是單階段調(diào)度算法，MEMAX和CMMN是兩階段調(diào)度算法，實(shí)驗(yàn)結(jié)果表明，MCC 適用于在線(xiàn)調(diào)度，CMMN 的最大完工時(shí)間較短，MEMAX的平均資源利用率較高，這些算法在最大完工時(shí)間和資源利用率方面整體優(yōu)于已有的多云環(huán)境任務(wù)調(diào)度算法RR、CMMS。

文獻(xiàn)[43]提出了一種新的多云系統(tǒng)架構(gòu)，并設(shè)計(jì)了一種動(dòng)態(tài)調(diào)度策略，該策略結(jié)合了可分負(fù)載理論和節(jié)點(diǎn)可用性預(yù)測(cè)技術(shù)，包括使用預(yù)測(cè)方法來(lái)估計(jì)虛擬機(jī)的準(zhǔn)備時(shí)間，以及使用以前關(guān)于處理時(shí)間的數(shù)據(jù)來(lái)估計(jì)工作負(fù)載的處理時(shí)間，并允許計(jì)算節(jié)點(diǎn)估計(jì)它們接受和處理負(fù)載的準(zhǔn)備時(shí)間，將這些時(shí)間應(yīng)用于策略，以保證負(fù)載平衡和系統(tǒng)的高性能，仿真實(shí)驗(yàn)結(jié)果表明，該調(diào)度策略?xún)?yōu)于基準(zhǔn)策略，有效地減少了任務(wù)執(zhí)行最大完工時(shí)間。

文獻(xiàn)[44]針對(duì)多云環(huán)境提出了一種多目標(biāo)科學(xué)工作流調(diào)度算法，該算法在滿(mǎn)足可靠性約束的情況下，使工作流最大完工時(shí)間和成本同時(shí)最小化，該算法基于PSO，求解帕累托前沿，同時(shí)考慮了任務(wù)的執(zhí)行位置和傳輸順序，仿真結(jié)果表明，該算法與CMOHEFT 和隨機(jī)算法相比，性能得到明顯改進(jìn)。

文獻(xiàn)[45]針對(duì)多云環(huán)境中的多目標(biāo)科學(xué)工作流調(diào)度問(wèn)題，提出了同時(shí)減少最大完工時(shí)間和成本的調(diào)度算法，該方法在不同場(chǎng)景中采用了不同的數(shù)值方法，例如加權(quán)和法、本森數(shù)值法和加權(quán)min-max，此外，研究了所得解的穩(wěn)定性，提出了一種方法來(lái)分析加權(quán)和法及加權(quán)min-max 的最優(yōu)穩(wěn)定解，實(shí)驗(yàn)結(jié)果表明，本文提出的加權(quán)和法在超體積（hypervolume）方面優(yōu)于已有的算法。

表4 對(duì)上述所列多云環(huán)境中的任務(wù)調(diào)度算法進(jìn)行了總結(jié)。由于多云環(huán)境整體的結(jié)構(gòu)發(fā)生了很大的改變，基于多云環(huán)境的任務(wù)調(diào)度算法結(jié)合了該環(huán)境任務(wù)特點(diǎn)進(jìn)行優(yōu)化，如文獻(xiàn)[42]考慮了任務(wù)的執(zhí)行位置和傳輸順序，文獻(xiàn)[43]采用可用性預(yù)測(cè)技術(shù)和自適應(yīng)方法提高多云環(huán)境的負(fù)載均衡，文獻(xiàn)[45]采用整數(shù)規(guī)劃來(lái)進(jìn)行計(jì)算。此外，由于多云環(huán)境中信息發(fā)送比較頻繁，耗時(shí)較長(zhǎng)，因此任務(wù)調(diào)度算法大多數(shù)選擇時(shí)間復(fù)雜度較低的算法類(lèi)型，如文獻(xiàn)[42-43，45]皆為啟發(fā)式調(diào)度，多云環(huán)境下也存在多目標(biāo)任務(wù)調(diào)度研究，如文獻(xiàn)[44-45]，而該環(huán)境下主要優(yōu)化目標(biāo)依然是最大完工時(shí)間和成本，部分文獻(xiàn)如文獻(xiàn)[49]考慮了可靠性約束，文獻(xiàn)[47]考慮了資源利用率。目前在多云環(huán)境任務(wù)調(diào)度的研究中，主要集中在使用不同的方法降低算法時(shí)間復(fù)雜度，增加求解多樣性和精度，而不是增加優(yōu)化目標(biāo)。

2.3 聯(lián)盟云環(huán)境任務(wù)調(diào)度

當(dāng)一組云供應(yīng)商彼此合作交換資源時(shí)，就構(gòu)成了聯(lián)盟云。這類(lèi)云環(huán)境往往由政府或?qū)W術(shù)組織發(fā)起，是政府云或私有云之間的合作。這種云環(huán)境可以使用分布式實(shí)體進(jìn)行代理，或者集中使用一個(gè)中心實(shí)體進(jìn)行資源注冊(cè)、共享和代理[2]。聯(lián)盟云的代理收集各個(gè)云服務(wù)供應(yīng)商發(fā)來(lái)的資源狀態(tài)，同時(shí)根據(jù)用戶(hù)指定的SLA將用戶(hù)應(yīng)用程序任務(wù)分配到可用資源的不同虛擬機(jī)上，以實(shí)現(xiàn)完工時(shí)間，成本，資源利用率等性能的最大化。

文獻(xiàn)[47]提出了一種使用統(tǒng)計(jì)多路復(fù)用技術(shù)在聯(lián)盟云中進(jìn)行請(qǐng)求分配的方法，該方法結(jié)合統(tǒng)計(jì)多路復(fù)用和服務(wù)器整合，檢查使用的變異系數(shù)和其他相關(guān)統(tǒng)計(jì)指標(biāo)作為目標(biāo)函數(shù)，用于決定請(qǐng)求分配，并比較了使用隨機(jī)算法、爬山算法、最大提升爬山算法、模擬退火算法、后期驗(yàn)收爬山算法等啟發(fā)式算法應(yīng)用該目標(biāo)函數(shù)的結(jié)果，實(shí)驗(yàn)結(jié)果表示后期驗(yàn)收爬山算法具有更好的性能。

表4 多云任務(wù)調(diào)度算法研究文獻(xiàn)總結(jié)

文獻(xiàn)[48]基于歐洲學(xué)術(shù)組織建立的Contrail[49]聯(lián)盟云環(huán)境建立了基于遺傳算法的代理組件，該遺傳算法根據(jù)多個(gè)QoS建立了本地適應(yīng)度函數(shù)和全局適應(yīng)度函數(shù)，將任務(wù)與虛擬機(jī)一一對(duì)應(yīng)，將虛擬機(jī)分配到相應(yīng)的不同的云服務(wù)供應(yīng)商中。實(shí)驗(yàn)結(jié)果表明，此方法充分利用了本地資源和全局資源，資源利用率較高，但處理大量數(shù)據(jù)，最大完工時(shí)間并沒(méi)有降低。

文獻(xiàn)[50]為了在云環(huán)境中執(zhí)行霜凍預(yù)測(cè)應(yīng)用程序，使最大完工時(shí)間和成本最小化，在聯(lián)盟云中兩個(gè)級(jí)別設(shè)計(jì)了調(diào)度策略。在代理級(jí)別，實(shí)現(xiàn)了基于ACO 的調(diào)度和基于PSO 的調(diào)度，其目標(biāo)是在考慮網(wǎng)絡(luò)延遲、貨幣成本和數(shù)據(jù)中心計(jì)算資源可用性的前提下選擇數(shù)據(jù)中心，在基礎(chǔ)設(shè)施級(jí)別，虛擬機(jī)通過(guò)基于ACO 和PSO 的調(diào)度分配給數(shù)據(jù)中心的物理主機(jī)。實(shí)驗(yàn)結(jié)果表明，與GA相比，這兩種調(diào)度可以極大降低最大完工時(shí)間和貨幣成本。

文獻(xiàn)[51]針對(duì)聯(lián)盟云提出了一種基于多目標(biāo)列表的工作流調(diào)度算法MOHEFT，該算法擴(kuò)展了HEFT工作流調(diào)度算法，通過(guò)擁擠距離實(shí)現(xiàn)了近似最優(yōu)帕累托前沿，降低了成本和最大完工時(shí)間，并使用實(shí)際工作流和合成工作流評(píng)估了MOHEFT，與HEFT 和SPEA2 相比，該算法能獲得較好的完工時(shí)間和成本，此外，還用GoGrid和Amazon EC2進(jìn)行實(shí)際測(cè)試，結(jié)果表明當(dāng)數(shù)據(jù)傳輸支配時(shí)間的情況下，工作流不會(huì)從聯(lián)盟云中獲益，反而在單個(gè)供應(yīng)商的配置中表現(xiàn)更好。

表5 對(duì)上述所列聯(lián)盟云環(huán)境中的任務(wù)調(diào)度算法進(jìn)行了總結(jié)。聯(lián)盟云作為學(xué)術(shù)云的常見(jiàn)形式，存在許多結(jié)合不同科學(xué)應(yīng)用程序進(jìn)行優(yōu)化的調(diào)度研究，如文獻(xiàn)[50]；針對(duì)任務(wù)分配的優(yōu)化問(wèn)題，也出現(xiàn)了許多適應(yīng)聯(lián)盟云的新方法，如文獻(xiàn)[47]使用的統(tǒng)計(jì)多路復(fù)用技術(shù)；此外，結(jié)合實(shí)際的聯(lián)盟云環(huán)境，設(shè)計(jì)符合要求的仿真環(huán)境和相匹配的任務(wù)調(diào)度算法也是聯(lián)盟云任務(wù)調(diào)度研究的一大類(lèi)型，如文獻(xiàn)[48]，多目標(biāo)優(yōu)化也是聯(lián)盟云任務(wù)調(diào)度建立目標(biāo)函數(shù)常用的方法，如文獻(xiàn)[51]。目前，聯(lián)盟云任務(wù)調(diào)度研究是以?xún)?yōu)化最大完工時(shí)間和成本為目標(biāo)，充分考慮聯(lián)盟云特征，盡可能多地考慮影響指標(biāo)，如跨云帶寬、網(wǎng)絡(luò)延遲、成本等來(lái)達(dá)到優(yōu)化的目的。用戶(hù)對(duì)聯(lián)盟云擁有海量的計(jì)算需求，但目前聯(lián)盟云任務(wù)調(diào)度研究尚不充分，對(duì)數(shù)據(jù)密集且計(jì)算密集型的應(yīng)用程序并沒(méi)有充分研究。

3 任務(wù)調(diào)度優(yōu)化方法分析

通過(guò)對(duì)云計(jì)算各類(lèi)環(huán)境下任務(wù)調(diào)度算法研究文獻(xiàn)進(jìn)行總結(jié)分析可以看出，目前任務(wù)調(diào)度算法的優(yōu)化方法是在已有的啟發(fā)式、元啟發(fā)式以及混合式算法類(lèi)型的基礎(chǔ)上結(jié)合單/多目標(biāo)函數(shù)及QoS 約束，進(jìn)行諸如任務(wù)排序、解集篩選、節(jié)點(diǎn)預(yù)測(cè)策略，對(duì)已有的各類(lèi)標(biāo)準(zhǔn)調(diào)度算法進(jìn)行改進(jìn)，如模糊排序方法[7，33]、整數(shù)規(guī)劃[37-38，45]、帕累托權(quán)衡[39，45，51]、節(jié)點(diǎn)預(yù)測(cè)技術(shù)[11，33，43]、統(tǒng)計(jì)多路復(fù)用[47]、人工智能[10，33]、多目標(biāo)優(yōu)化[39，44，51]、自適應(yīng)優(yōu)化[37，43]。表6對(duì)文獻(xiàn)中使用的優(yōu)化策略進(jìn)行分析，并給出了相應(yīng)的部分文獻(xiàn)研究類(lèi)型。可以看到這些方法使用建模、任務(wù)排序、節(jié)點(diǎn)預(yù)測(cè)、請(qǐng)求合并、方案排序等對(duì)任務(wù)調(diào)度算法進(jìn)行優(yōu)化，從而簡(jiǎn)化模型，方便分配，整理需求，減少可分配計(jì)算節(jié)點(diǎn)，尋找可行解，從各個(gè)角度實(shí)現(xiàn)提高分配效率與精度的目標(biāo)。未來(lái)可以在不同云環(huán)境任務(wù)調(diào)度的研究中充分應(yīng)用這些方法來(lái)達(dá)到性能優(yōu)化目的。

4 總結(jié)與展望

本文根據(jù)環(huán)境類(lèi)型對(duì)云計(jì)算任務(wù)調(diào)度算法進(jìn)行了總結(jié)分析，討論了云內(nèi)、混合云、多云、聯(lián)盟云的環(huán)境特點(diǎn)和任務(wù)調(diào)度特征，歸納出27 種不同算法類(lèi)型的任務(wù)調(diào)度方法、結(jié)合啟發(fā)式、元啟發(fā)式及混合式調(diào)度類(lèi)型對(duì)獨(dú)立任務(wù)和工作流最新及代表性研究文獻(xiàn)的具體實(shí)現(xiàn)過(guò)程、優(yōu)化指標(biāo)、仿真環(huán)境及優(yōu)缺點(diǎn)進(jìn)行分析探討，并對(duì)相關(guān)優(yōu)化方法進(jìn)行描述分析，呈現(xiàn)了云任務(wù)調(diào)度領(lǐng)域的最新重要研究進(jìn)展。

云內(nèi)任務(wù)調(diào)度研究充分，存在大量?jī)?yōu)化性能較好的調(diào)度算法，為了應(yīng)對(duì)逐漸增加的用戶(hù)計(jì)算任務(wù)，提供安全穩(wěn)定的計(jì)算環(huán)境，跨云環(huán)境任務(wù)調(diào)度研究逐步發(fā)展，由于跨云環(huán)境具有一些獨(dú)特且復(fù)雜的特征，使得任務(wù)調(diào)度研究在傳統(tǒng)任務(wù)調(diào)度算法類(lèi)型的基礎(chǔ)上進(jìn)行了許多環(huán)境針對(duì)性?xún)?yōu)化，出現(xiàn)了使得獨(dú)立任務(wù)和科學(xué)工作流在各類(lèi)環(huán)境下能夠有效調(diào)度的算法和框架。

表5 聯(lián)盟云任務(wù)調(diào)度算法研究文獻(xiàn)總結(jié)

表6 任務(wù)調(diào)度優(yōu)化方法分析

雖然任務(wù)調(diào)度的研究已取得了許多進(jìn)展，但也存在一些需要重點(diǎn)關(guān)注研究的方面。

（1）隨著用戶(hù)計(jì)算任務(wù)的增加，在跨全球云服務(wù)供應(yīng)商環(huán)境中執(zhí)行用戶(hù)任務(wù)將成為未來(lái)重要的發(fā)展方向，目前跨云環(huán)境任務(wù)調(diào)度算法研究很不充分，QoS指標(biāo)優(yōu)化較少，特別是超大規(guī)?？缭骗h(huán)境下的數(shù)據(jù)計(jì)算密集型任務(wù)調(diào)度算法研究尚處于初始階段。

（2）目前云內(nèi)任務(wù)調(diào)度研究出現(xiàn)了許多新方法，諸如人工智能相關(guān)算法、模糊排序，都是非常有前景的方法，但這些方法目前尚未大量應(yīng)用到跨云任務(wù)調(diào)度的研究中，未來(lái)可作為一個(gè)重點(diǎn)研究方向。