云計算環境下任務調度研究綜述

申倩等

摘 要：云計算是一種新的商業計算模型。它將計算任務分布在大量計算機構成的資源池上，使各種應用系統能夠根據需要獲取計算資源、數據資源、存儲資源和應用服務資源等。大數據時代，云計算的另一個特點是它將處理大規模的任務。如何實現在滿足用戶QoS的前提條件下，對海量任務進行高效調度并對大量云資源進行合理的分配，使得云任務占用盡量少的云資源是云計算領域的一個研究熱點。主要論述了云計算環境下任務調度的目標和新特性，分析總結了云計算任務調度的研究現狀并以調度目標為側重點歸納總結了四類調度策略，即側重性能的調度、側重服務質量的調度、側重經濟原則的調度和側重能耗優化的調度，給出了云任務調度的研究展望，為下一步更深入的研究指出方向。

關鍵詞：云計算；任務調度；能耗優化；用戶行為

中圖分類號：TP3 文獻標識號：A 文章編號：2095-2163（2014）06-

Abstract： Cloud computing is a new business computing model. It distributed computing tasks in a large resource pool consisting of many computers， make a variety of applications can obtain computing resources， data resources， storage resources and application services and other resources as needed. Big Data era， another characteristic of cloud computing is that it will deal with a massive task. How to achieve massive task for efficient scheduling and rational allocation of cloud resources under the precondition user QoS， making the task of occupying as little cloud computing resources is a research hotspot. The paper discusses the objectives and new features of task scheduling under the cloud computing environment ，analyzes and summarizes the research status of cloud computing task scheduling and summarizes four scheduling policy according to schedule objectives. Simultaneously， the paper gives prospect of cloud task scheduling for the next direction of more in-depth study noted.

Key words： Cloud Computing； Task Scheduling； Energy Optimization； User Behavior

0 引 言

云計算是近年來廣受關注的研究熱點之一。云計算是一個較為抽象的概念，最初起源于電話通訊行業。20世紀，電話已經普及、并演變為一種公共事業，借助公共電話網，兩個電話可以實現直接通訊。但是若要在兩個用戶之間建立一條私密的、專用通道，則必須架設一條新的物理專線，這將導致昂貴的費用開銷。90年代，VPN（虛擬專用網絡）技術出現，憑其即可通過公用網絡隨時為兩個用戶建立專線連接，這就大大節省了通訊的開支。為了描述這種可以為個人提供專用資源，而且又可以隨時使用的網絡服務，“云”概念應運而生了。“計算”，指的是計算機的計算能力，其速度取決于計算機的硬件配置。1963年，斯坦福大學的約翰·麥卡錫教授就預見說“計算的能力，有一天會被組織起來，成為一種公共資源和公共事業。”[1]；也就是說，將計算的能力放在網絡上，而不是個人電腦上。所有的硬件計算能力、

存儲能力、軟件執行能力，全部都由互聯網來提供。1997年，南加州大學的一位印度裔教授切諾柏將“云”

與“計算”組合成一個新單詞，從而正式提出了“云計算”概念。

云的運營商把計算能力作為一種資源，集中在一起組成資源池，再通過網絡，配送給有需要的客戶。而且，服務商的供應量將隨客戶的需求量高低而進行調整與變動。客戶購買預制服務后就不需要再購買昂貴的軟件和硬件。這對于小型創業公司而言，在相當程度上減少了因購買服務器和軟件帶來的開銷，只要通過租用就可以獲得在網上超高強配置的軟硬件能力。也就是說，正如自來水管道供水、電力網供電一樣，云計算亦將計算從有形的產品變成了無形的服務。

云計算提供的資源服務從具體應用角度可分為三個層次，具體來說就是基礎設施即服務（IaaS）、平臺即服務（PaaS）和軟件即服務（SaaS）。這三個層次各自側重于不同的應用，但是卻包含著相同的問題，即資源、任務調度問題。調度問題直接關系到云服務的穩定性、用戶的滿意度、資源的利用率以及運營成本等。因此，對云計算的調度問題展開研究具有非常重要的現實意義及理論價值。

1云計算環境下的任務調度

1.1 云環境下用戶獲取服務的流程

云計算系統是由海量的商用機和高性能服務器組成，其中的數據中心向用戶分配虛擬機來運行其所提交的任務，而任務調度則決定虛擬機的分配數量及任務執行次序，如圖1所示。

1.2 云環境下任務調度的新特性

云計算是在網格計算、并行計算、集群計算的基礎上發展起來的，因此他們的任務調度策略具有很大的相似性。但是，與網格計算等相比，云計算還表現了一些新的專有特性，可具體描述為：

（1） 云資源的差異較大，云環境下的資源可能是高性能的服務器、普通PC機，或者是各種硬件設備上的虛擬環境。這就使得資源的計算能力和存儲能力必然具有明顯差異。

（2） 用戶對云資源的需求具有多樣性和偏好性，因此需要考慮更加復雜的QoS約束，最大限度地滿足用戶的QoS要求。

（3） 云計算環境下的有效調度需要保證云計算服務商提供的云資源能夠得到充分利用并獲得最大收益。傳統的調度策略往往卻只是考慮如何滿足各用戶的QoS要求，而很少考慮資源服務商的經濟效益。

（4） 用戶需求的多樣性和應用類型的復雜性使得云計算系統中能源成本成為一個重點關聯因素。云計算環境的商業化特點決定了必須引入能耗開銷等因素來建立問題模型，并藉此全面研究相應的調度策略。

1.3 云環境下任務調度的目標

云環境下，任務調度的目標就是對用戶提交的所有任務實現最優調度，并盡量提高云計算系統的總體吞吐率。具體的目標包括：服務質量（Quality of Service， QoS）、負載均衡、經濟原則和節能減排等。具體分析如下：

（1） QoS。云環境下的任務調度系統必須滿足用戶的QoS。一方面，要根據應用的特征提高資源的發現率和準確性系數，保證用戶服務的性能QoS；另一方面，則需針對用戶的狀態變遷，動態進行資源選擇以及重定向，滿足用戶的經濟QoS，有效地提高用戶滿意度。

（2） 負載均衡。由于云環境下計算資源是由大量計算機節點組成，復雜且異構，這就使得負載均衡的實現具有相當難度。

（3） 經濟效益。由于云計算是一種新型的商業模式，其中的經濟效益必然成為著重關注的調度指標。該指標的切實完善的真正實現將直接關系著云計算這一面向普適商業應用計算模式的有效運營周期。

（4） 節能減排。云計算是超大規模的計算，每個數據中心的電力消耗均堪稱巨大，在提倡綠色計算的背景環境下，云計算也必須將節能減排作為一個重要的追求目標。

2 云環境下任務調度技術研究現狀

2.1側重性能的調度

作為任務調度研究的核心熱點，側重性能的任務調度的最終目標就是性能，例如最優跨度，任務最早完成時間等。目前使用比較廣泛的算法包括Min-Min算法、Max-Min算法、遺傳算法、貪心算法、蟻群算法和模擬退火算法等。

具體來說，IBM公司的云計算平臺采用的就是以性能為中心的調度策略。而且，李建峰等人[2]基于MapReduce模型，提出了一種具有雙適應度的遺傳算法（DFGA），該算法不僅能夠使總任務的完成時間最短還能使任務的平均完成時間較短；湯小春等人[3]則提出了一種基于元區間的最佳分配決策算法，并取得了良好效果；還有，華夏渝等人[4]提出了一種基于蟻群優化的資源分配算法，該算法適應于具有最小響應時間和最好服務質量為其指標要求的任務調度。另外，周文俊等人[5]針對靜態資源調度中只考慮任務完成時間最小化問題，提出了一種基于預測的蟻群算法來滿足云環境下資源的動態分配。

2.2側重服務質量的調度

云計算是一種商業模型，其中的用戶QoS不僅關系到用戶的實際體驗，而且將實際影響著云計算的良性發展。因此，基于QoS的任務調度算法研究也獲得蓬勃發展。一般情況下，算法研發框架除了要考慮最小完成時間或是最優跨度，還有考慮服務質量等問題。

基于QoS的研究，目前已推出豐碩成果。文獻[6]提出了一種基于模糊聚類的云任務調度算法，該算法對資源進行模糊聚類，更好地反映了任務的需求。He等人[7]對Min-Min算法進行了改進，即根據用戶是否還有QoS需求而對系統的吞吐率實現了優化。Chanhan等人[8]又根據加權平均執行時間進行資源選擇，通過將網絡帶寬作為QoS屬性，而將任務分為高QoS與低QoS需求兩類，并且對于高QoS的任務將進行優先調度。再有阿爾卡特朗訊貝爾實驗室的Hao等人[9]提出了一個網絡虛擬化架構，用來實現云服務的動態需求和遷移，而不影響服務性能，由此提高了云服務質量。另外，孫大為等人[10]則提出一種基于免疫克隆的偏好多維 QoS云計算調度優化算法，結合免疫克隆算法，對客戶應用的偏好和多維 QoS中的用戶效用進行量化，同時給出了多維 QoS優化的目標函數，以此滿足客戶的經濟 QoS和性能 QoS。

2.3側重經濟原則的調度

除服務質量外，云計算的商業運行模式則使得經濟因素也成為任務調度的重要指標之一。惠普的云數據中心采用的就是成本優先調度策略。鄧見光等人[11]，在滿足QoS的前提條件下，從云服務提供商的角度出發，給出了一種基于成本的云任務調度策略。Buyya等人[12]進而提出了面向市場的云計算以及面向市場的云計算構架。葛新等人[13]再次提出了一種基于計算強度的調度策略，并且具有低成本的特點。該策略的主要思想是將計算量大的任務分配給計算能力強的集群調度，而將計算量小的任務則分配給計算能力弱的集群調度。另外，對于那些經濟效益要求高而時間需求相對寬松的應用，即可選擇計算能力弱的集群調度；但針對有嚴格時間要求的應用將可申請計算能力強的集群調度，如此即能達到降低成本的目的。

2.4側重能耗優化的調度

在提倡綠色計算的浪潮下，已有更多的學者正致力研究側重于能耗優化的調度算法，并取得了可觀的成就。

文獻[14]中設計了基于動態定價策略的數據中心能耗成本優化方案，為研究基于能耗優化的任務調度提供了基礎。該調度算法可以根據動態的服務價格進行調度，達到優化能耗的目的。文獻[15]中則提出了兩種具有能量感知的任務調度算法，分別利用能耗時間歸一及能耗時間來定義適應度函數，實驗結果表明，與單獨考慮能耗或是時間相比，這兩種算法能夠有效降低能耗并縮短任務執行時間。曹潔等人[16]也提出了兩種滿足并行任務截止時間要求和并行任務執行能耗要求的調度方法Ssef和Egsa。實驗結果表明，該算法在保證并行任務截止完成時間要求的前提下能夠有效降低并行任務的能源消耗，從而降低了云計算系統的能耗開銷。

3 云環境下任務調度技術的研究展望

目前，根據云環境任務調度技術的研究進程和現存問題，給出了建議和設想，期望對任務調度的進一步研究提供有益的借鑒。

3.1 基于用戶行為特征的調度策略研究

云計算環境中，用戶提交的任務數目將是海量，那么如何在資源有限的情況下，對海量任務進行有效調度，同時資源也得到有效利用即已成為研究重點。針對此一問題，可以從用戶的行為特征出發，通過統計用戶的行為習慣和預期的完成時間，來合理安排任務的科學調度，由此而提高資源利用率和用戶滿意度。

另一方面，當用戶刪除、撤銷任務時，調度系統將相應地采取一定的調度策略來適應這種變化，從而避免了資源不必要的浪費。

3.2 基于云任務多維屬性的節能的任務調度策略

綠色計算提出后，云環境下節能的任務調度的研究隨即也成為熱點問題。已有的大部分研究均以數據中心的節能為其優化目的，但迄今仍然少有根據任務的多維屬性來進行任務調度從而達到節能效果的。云任務是海量的、差異性大的、偏好性強的，針對不同的任務需求給出相應的資源分配方案，將能有效降低任務能耗。

4 結束語

云環境下的資源具有動態多變、按需提供、按量付費、任務差異大、任務偏好性強等特點。現有的調度算法并不能完全滿足云任務調度要求。因此，云任務的調度是云計算領域的研究熱點之一。本文介紹了云任務調度的新特性及目標，分析了國內外云任務調度的研究現狀。盡管這些研究取得了頗豐的進展，但也存在著一定的不足。很多工作仍需進一步展開深度的探討與研究。

參考文獻：

[1]Wikipedia.Utility computing.[2010-07-12].http：//en.wikipedia.org/wiki/Utility_computing.

[2] 李建鋒，彭艦.云計算環境下基于改進遺傳算法的任務調度算法[J].計算機應用，2011，31（1）：184-186.

[3] 湯小春，劉健.基于元區間的云計算基礎設施服務的資源分配算研究[J].計算機工程與應用，2010，46（34）：237-241.

[4] 華夏渝，鄭俊，胡文心.基于云計算環境的蟻群優化計算資源分配算法[J].華東師范大學學報：自然科學版，2010，1（1）：127-134.

[5] 周文俊，曹鍵.基于預測及蟻群算法的云計算資源調度策略.計算機仿真[J].計算機仿真，2012（9）： 239-242+246.

[6] 李文娟，張啟飛，平玲娣，潘雪增.基于模糊聚類的云任務調度算法[J].通信學報，2012，33（3）： 146-154.

[7] HE Xiao-shan，SUM Xian-he，Von LASEEWSKI G.QoS guided min-min heuristic for grid task scheduling[J].Journal of Computer Science and Technology ，2003，18（4）：442-451.

[8] CHANHAN S S，JOSHI R C.A heuristic for QoS based independent task scheduling in grid environment[C]//Proc of International Conference on Industrial and Information Systems，2010：102-106.

[9] HAO Fang，LAKSHMAN T V，MUKHERJEE.Enhancing dynamic cloud-based services using network vitualization[J].Computer Communication Review，2010，40（1）：67-74.

[10] 孫大為，常桂然，李鳳云.一種基于免疫克隆的偏好多維QoS云資源調度優化算法[J].電子學報，2011，39（8）：1824-1830.

[11] 鄧見光，趙躍龍，袁華強，等. 一種成本驅動的云計算任務調度策略[J]. 江蘇大學學報： 自然科學版，2014，35（2）：214-219.

[12] BUYYA R，YEO C S，VENUGOPAL S. Market-Oriented Cloud Computing：Vision，Hype，and Reality for Delivering IT Services as Computing Utilities[C]//Proc of the 10th IEEE International Conference on High Performance Computing and Communications.2008：5-13.

[13] 葛新，陳華平，杜冰，等.基于云計算集群擴展中的調度策略研究[J].計算機應用研究，2011，28（3）： 995-997+100.

[14] 王魏，羅軍舟，宋愛波.基于動態定價策略的數據中心能耗成本優化[J].計算機學報，2013，36（3）：599-612.

[15] 英昌甜，于炯，楊興耀.云計算環境下能量感知的任務調度算法[J].微電子學與計算機，2012，29（5）：188-192.

[16] 曹潔，曾國蓀.云環境下計算資源動態能耗感知的并行任務調度方法[J].計算機科學，2013，40（10）：39-44.