摘要：雲計算中任務調度算法的好壞直接影響雲計算系統整體性能，也影響着雲計算系統處理用戶提交的任務的能力。本文歸納了雲計算調度的特點和性能指标，總結了雲計算中的任務調度算法，分析了雲計算任務調度算法的研究現狀及其進展。最後讨論了現有任務調度策略存在的問題，為雲調度研究指明了方向和思路。
關鍵詞：雲計算；任務調度；遺傳算法；蟻群算法
前言
雲計算是一種基于互聯網的新的服務模式，這種模式按使用量付費，提供可用的、便捷的、按需的網絡訪問，它将用戶需求的計算任務分布在由大量計算機構成的數據中心，數據中心采用虛拟化技術，把各種軟硬件資源抽象為虛拟化資源，再通過資源調度技術使各種應用能夠根據需要獲取計算能力、存儲空間和信息服務。
在雲計算環境中，一個大規模計算任務需要進行分布式并行處理，系統首先将邏輯上完整的一個大任務切分成多個子任務，然後根據任務的相應信息采取合适的調度算法，在不同的資源節點上運行這些子任務，所有的子任務處理完後進行彙總，最後将結果傳給用戶。雲計算任務調度的目的是給需要的用戶分配不同的資源，在某一特定的雲環境下，依據某一種規則使用資源，在不同的用戶之間平衡和調整資源，在滿足用戶需求的前提下，使得任務完成時間盡量小，且資源利用率盡量高。調度最終要實現時間跨度、服務質量、負載均衡、經濟原則最優等目标。雲計算任務調度是雲計算研究中的重點和難點。任務調度算法的優劣會影響到雲計算系統處理任務的能力。近幾年，研究者針對雲環境下的資源調度做了很多研究，主要體現在以提高雲計算數據中資源利用率為宗旨的資源管理與調度、以降低雲計算數據中心的能耗為目标的資源分配與調度、經濟學的雲資源管理模型研究等方面。
本文綜述了雲環境下的任務調度算法，分析了近幾年來典型的雲計算任務調度算法的發展趨勢，為相關領域的研究人員提供參考。
1、網格任務調度與雲計算任務調度的比較
在網格計算和雲計算中，雖然系統資源都是以數據池的形式呈現給用戶，但它們之間的區别是網格用戶的任務是通過實際的物理資源來執行，而雲計算環境下的用戶任務是通過邏輯意義上的虛拟資源來執行。對于以上兩種計算方式，都是由用戶将任務提交給計算中心，系統通過對任務的需求進行分析，然後來尋找合适的資源節點執行，此時的用戶并不關心執行任務的是哪個節點。網格系統通過用戶預先設定的任務并行執行算法，并結合自己的調度系統使用戶任務實現跨物理節點并行執行[1]，雲計算任務調度通常情況不會跨虛拟機并行調度。盡管雲計算是在網格計算、分布式計算及并行計算的基礎上發展起來的，但是雲環境比較複雜，任務呈現多樣性，而且是以商業服務作為宗旨。雲計算任務調度策略不能照搬傳統調度策略來滿足用戶提出的各種任務要求，必須考慮怎樣在高效任務調度與資源分配同時提高經濟效益、資源利用率以及用戶體驗等各方面的因素。可靠的雲服務和各層次的用戶公平使用資源的機會是雲計算調度策略必須考慮的問題，此外還需要有一個調度策略來提供系統可以使用的資源，以便滿足多樣化的用戶需求。因此虛拟化技術在雲計算中的廣泛應用、中間層與資源節點以及用戶與中間層之間的關系發生了很大變化，雲計算應該研究新的任務調度策略來滿足用戶的要求。
2、雲計算任務調度算法
2.1傳統任務調度算法
傳統任務調度算法主要有Min-Min算法、Max-Min算法、Sufferage算法等。Min-Min算法是将任務分配給執行效率最高的資源，這種算法容易導緻負載大多集中在能力較強的資源節點上，使得資源負載極度不均衡。Max-Min算法首先要計算每一個任務在任一個可用資源上的最早完成時間，然後将具有最早執行時間的計算資源分配給最大的任務，随後更新資源的最早可用時間和任務集，直到全部任務調度完成。Min-Min算法是将小的任務分配到執行效率高的資源上進行，有很好的負載均衡性。當可執行任務的資源發生變化時，Max-Min算法的優勢就不存在。Sufferage算法是以任務最小完成時間為調度目标。Sufferage算法的缺點是負載的平衡性能不高。基于傳統調度算法進行改進的研究已有很多。王文豪[2]為了解決Min-Min調度算法中存在的負載不平衡問題，改善系統負載的均衡性，提出基于Min-Min極限下壓算法的負載模糊分類及局部重調度的算法。引入模糊分類的思想，根據各節點的負載大小，将節點分成三種類型：重負載、中負載和輕負載；對負載較重和較輕的節點進行重新調度，通過使用Min-Min極限下壓算法來壓縮資源節點完成任務的時間，改善算法的負載失衡問題。何麗[3]提出将優化能耗的調度方法應用到min-min任務調度算法中，它通過系統對任務結束時間的要求，先選取任務隊列中的最小任務，然後分配到所需能耗最小的服務器上執行，結果表明能夠較好地滿足任務結束時間的要求，同時降低了雲計算系統的總能耗。周舟[4]提出一種Min-Max算法。該算法對時間貪心，将小任務和大任務“捆綁”在一起執行調度，從而有效地解決了負載不均衡的問題。
2.2基于智能啟發式任務調度算法
傳統調度算法一般都把效率作為追求的首要目标，且由于調度算法普遍适應性不強，局限性較大，如：最小完成時間的任務調度方法，雖具有較好的完成效率，但是系統負載均衡達不到理想要求，計算效率高的虛拟機資源長期超負荷運行；最終還不一定能滿足用戶任務的服務質量要求。因此，基于智能啟發式任務調度算法有了很快的發展，主要有遺傳算法、蟻群優化算法、粒子群優化算法以及模拟退火算法等，現階段這些智能啟發式算法經過許多學者的改進已經廣泛應用到雲計算系統中，它們通過疊代對解進行了優化，最終得到近似解。
（1）遺傳算法
遺傳算法的原理是生物界中的自然選擇學說和種群遺傳學，它是一種利用繁衍、監測和評價來進行疊代、進化的搜索方法，具有求解問題的高度并行性及很強的全局性空間搜索能力。在搜索的過程中它能自動獲取相關搜索空間的知識，并能自适應地控制搜索的過程從而得到滿意解。但遺傳算法也有不足之處：收斂速度慢、易于陷入局部最優的問題[5]。李韪韬等[5]提出用N進制的浮點數來表示每個基因值，然後将其分為兩部分及整數部分和小數部分，重新編碼組成染色體的新的基因值，提高算法在早期的全局搜索能力，避免陷入局部極值。張愛科[6]結合遺傳算法的優點，提出一種公平均衡遺傳調度算法FBGSA。該算法充分考慮到任務調度過程中資源和任務的公平性問題，以及資源的負載均衡等因素。
（2）蟻群算法和粒子群優化算
蟻群算法是一種用來尋求最優化路徑的群體智能算法。由于蟻群算法的并發性和可擴展性，所以其很适用于雲計算環境下的資源調度。粒子群優化算法是根據交互粒子群之間的信息來尋找全局最優解的算法[7]。它的特點是原理簡單、參數設置較少，所以與其他多數智能算法相比，粒子群優化算法已廣泛應用于神經網絡、函數優化、智能控制等領域。孟凡超[8]提出了一種基于蟻群優化算法的資源調度算法，主要針對雲數據中心虛拟機分配物理機時，存在負載不均衡的問題。通過對問題場景進行分析，提出了數據中心負載不均衡度，以及物理機與虛拟機之間不匹配度的概念，并給出了問題的形式化描述。在蟻群算法選擇概率規則中參考了用戶對虛拟機資源的需求，盡量避免對相同類型虛拟機部署在一台物理機上，同時對信息素的初始化、信息素的更新進行了改進。文曉棠[9]通過對蟻群算法和粒子群算法的理論進行了研究，根據這兩種算法本身存在的缺點，對算法進行了一些改進。通過取長補短對兩種算法進行融合改進後的算法，比之前基于一種算法的調度策略有更好的執行時間和效率。
王登科[10]将粒子群優化算法中的快速收斂和蟻群算法的尋優能力相結合，提出了一種新的任務調度算法，該算法縮短了系統處理調度問題的時間，提高了雲計算任務調度的效率。封良良[11]提出的任務調度算法在考慮總任務完成時間和任務平均完成時間的同時，也考慮了總任務完成成本，在傳統粒子群優化算法的基礎上，選取雙适應度的原則實現最小執行時間的同時兼顧成本最小。
（3）模拟退火算法
模拟退火算法最早是在1953年由Metropolis等人在研究二維變相時發現的，1983年由kirkpatrick等成功地引入到組合優化領域中，從此模拟退火算法開始被大規模、廣泛地應用于組合優化求解的問題中。模拟退火算法是一種可以廣泛應用于實際工程中的全局最優算法，也是局部搜索算法的擴展。徐潔[12]針對現有的雲計算任務調度算法提出一種雙适應度遺傳退火任務調度算法(DFG2A)，基于該任務調度算法的任務調度策略能夠有效平衡用戶對任務各項屬性的需求，提高雲計算平台的用戶滿意度。張浩榮[13]提出一種融合蟻群算法和模拟退火算法的混合調度算法(ACOSA)，該算法以最小化調度時間為目标，引入了任務與資源的匹配因子和負載均衡度，先利用蟻群算法得到一組任務到資源的優化解，然後通過模拟退火算法對解進行路徑的優化和信息素的更新。
3、存在的問題及展望
目前，許多學者對雲計算資源調度的問題進行了大量的研究和改進，有了一定的研究成果，但在調度策略方面還存在許多問題，要想雲計算能被更多的用戶接受，有持續快速的發展，還需要對雲計算的任務調度有更深入的研究。
1）既能滿足用戶的服務需求同時又能兼顧系統整體性能和經濟成本方面還需深入研究。調度策略要注意到雲計算面向服務的特點，滿足用戶的費用低廉的目的又能給用戶提供實時性保證。
2）現階段的雲計算任務調度算法主要通過任務的響應時間、可靠性及成本等方面來考慮用戶的QoS；而對于雲計算服務提供商來說，主要是從如何降低能耗，減少花費，提高系統資源的利用效率等方面來考慮。如何才能讓雲服務提供商和用戶雙方達到互利共赢是一個有待解決的問題，在以後可以進行更加深入的研究。
3）加強雲計算任務調度算法性能檢測模型的研究，對于衡量雲計算調度算法性能的模型很少，而且多是利用一些數學模型或是采用分布式系統中的任務調度模型的問題，迫切需要設計出合理的任務模型來檢測雲計算任務調度算法性能。
4、結束語
雲計算任務調度問題是雲計算系統的核心技術之一，是雲計算應用的關鍵問題，好的任務調度策略，能夠提高系統資源的利用率，平衡系統負載，提高雲計算服務質量。本文介紹了雲計算任務調度的概念以及其特點，并系統綜述了雲計算中幾個比較常見的任務調度算法近年來的研究進展，最後對雲計算任務調度中當前存在的問題進行了概括說明。
參考文獻
[1]羅紅,慕德俊,鄧智群,王曉東.網格計算中任務調度研究綜述.計算機應用研究,2015,5:16-19.
[2]ZehuaZhang,XuejieZhang.ALoadBalancingMechanismBasedonAntColowandComplexNetworkTheoryinOpenCloudComputingFederation.20102ndInternationalConferenceonIndustrialMechatroniCSandAutomation.2010.
[3]何麗,饒俊,趙富強.一種基于能耗優化的雲計算系統任務調度方法.計算機工程與應用，2013,49(20):19-22,111.
[4]周舟,胡志剛.雲計算中融入貪心策略的調度算法研究.小型微型計算機系統，2015,36(5):1024-1027.
[5]吳玫,陸金桂.遺傳算法的研究進展綜述.機床與液壓,2008,36:176-179.
[6]張愛科,謝翠蘭.基于公平性和負載均衡的雲計算任務調度算法.計算機應用與軟件,2015,32(2):268-271.
[7]王洪濤.粒子群優化算法的改進及應用：西安科技大學碩士學位論文，2011.
[8]孟凡超,張海洲,初佃輝.基于蟻群優化算法的雲計算資源負載均衡研究.華中科技大學學報，2013,41:57-62.
[9]文曉棠.雲計算環境下基于蟻群粒子群優化算法的資源調度策略研究:江西師範大學碩士學位論文，2013.
[10]王登科,李忠.基于粒子群優化與蟻群優化的雲計算任務調度算法.計算機應用與軟件，2013,30(1):290-293.
[11]封良良,張陶,賈振紅等.雲計算環境下基于改進粒子群的任務調度算法.計算機工程，2013(5)：183-186.
[12]徐潔,朱健琛,魯珂基于雙适應度遺傳退火的雲任務調度算法.電子科技大學學報,2013,42(6):900-904.
[13]張浩榮,陳平華,熊建斌.基于蟻群模拟退火算法的雲環境任務調度.廣東工業大學學報,2014,31(3):77-82.
作者簡介：張豔敏，山西大學商務學院講師，碩士研究生，主要研究方向為雲計算。