云計(jì)算環(huán)境下任務(wù)調(diào)度研究綜述

申倩等

摘 要：云計(jì)算是一種新的商業(yè)計(jì)算模型。它將計(jì)算任務(wù)分布在大量計(jì)算機(jī)構(gòu)成的資源池上，使各種應(yīng)用系統(tǒng)能夠根據(jù)需要獲取計(jì)算資源、數(shù)據(jù)資源、存儲(chǔ)資源和應(yīng)用服務(wù)資源等。大數(shù)據(jù)時(shí)代，云計(jì)算的另一個(gè)特點(diǎn)是它將處理大規(guī)模的任務(wù)。如何實(shí)現(xiàn)在滿足用戶(hù)QoS的前提條件下，對(duì)海量任務(wù)進(jìn)行高效調(diào)度并對(duì)大量云資源進(jìn)行合理的分配，使得云任務(wù)占用盡量少的云資源是云計(jì)算領(lǐng)域的一個(gè)研究熱點(diǎn)。主要論述了云計(jì)算環(huán)境下任務(wù)調(diào)度的目標(biāo)和新特性，分析總結(jié)了云計(jì)算任務(wù)調(diào)度的研究現(xiàn)狀并以調(diào)度目標(biāo)為側(cè)重點(diǎn)歸納總結(jié)了四類(lèi)調(diào)度策略，即側(cè)重性能的調(diào)度、側(cè)重服務(wù)質(zhì)量的調(diào)度、側(cè)重經(jīng)濟(jì)原則的調(diào)度和側(cè)重能耗優(yōu)化的調(diào)度，給出了云任務(wù)調(diào)度的研究展望，為下一步更深入的研究指出方向。

關(guān)鍵詞：云計(jì)算；任務(wù)調(diào)度；能耗優(yōu)化；用戶(hù)行為

中圖分類(lèi)號(hào)：TP3 文獻(xiàn)標(biāo)識(shí)號(hào)：A 文章編號(hào)：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 引 言

云計(jì)算是近年來(lái)廣受關(guān)注的研究熱點(diǎn)之一。云計(jì)算是一個(gè)較為抽象的概念，最初起源于電話通訊行業(yè)。20世紀(jì)，電話已經(jīng)普及、并演變?yōu)橐环N公共事業(yè)，借助公共電話網(wǎng)，兩個(gè)電話可以實(shí)現(xiàn)直接通訊。但是若要在兩個(gè)用戶(hù)之間建立一條私密的、專(zhuān)用通道，則必須架設(shè)一條新的物理專(zhuān)線，這將導(dǎo)致昂貴的費(fèi)用開(kāi)銷(xiāo)。90年代，VPN（虛擬專(zhuān)用網(wǎng)絡(luò)）技術(shù)出現(xiàn)，憑其即可通過(guò)公用網(wǎng)絡(luò)隨時(shí)為兩個(gè)用戶(hù)建立專(zhuān)線連接，這就大大節(jié)省了通訊的開(kāi)支。為了描述這種可以為個(gè)人提供專(zhuān)用資源，而且又可以隨時(shí)使用的網(wǎng)絡(luò)服務(wù)，“云”概念應(yīng)運(yùn)而生了?！坝?jì)算”，指的是計(jì)算機(jī)的計(jì)算能力，其速度取決于計(jì)算機(jī)的硬件配置。1963年，斯坦福大學(xué)的約翰·麥卡錫教授就預(yù)見(jiàn)說(shuō)“計(jì)算的能力，有一天會(huì)被組織起來(lái)，成為一種公共資源和公共事業(yè)?！盵1]；也就是說(shuō)，將計(jì)算的能力放在網(wǎng)絡(luò)上，而不是個(gè)人電腦上。所有的硬件計(jì)算能力、

存儲(chǔ)能力、軟件執(zhí)行能力，全部都由互聯(lián)網(wǎng)來(lái)提供。1997年，南加州大學(xué)的一位印度裔教授切諾柏將“云”

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

云的運(yùn)營(yíng)商把計(jì)算能力作為一種資源，集中在一起組成資源池，再通過(guò)網(wǎng)絡(luò)，配送給有需要的客戶(hù)。而且，服務(wù)商的供應(yīng)量將隨客戶(hù)的需求量高低而進(jìn)行調(diào)整與變動(dòng)。客戶(hù)購(gòu)買(mǎi)預(yù)制服務(wù)后就不需要再購(gòu)買(mǎi)昂貴的軟件和硬件。這對(duì)于小型創(chuàng)業(yè)公司而言，在相當(dāng)程度上減少了因購(gòu)買(mǎi)服務(wù)器和軟件帶來(lái)的開(kāi)銷(xiāo)，只要通過(guò)租用就可以獲得在網(wǎng)上超高強(qiáng)配置的軟硬件能力。也就是說(shuō)，正如自來(lái)水管道供水、電力網(wǎng)供電一樣，云計(jì)算亦將計(jì)算從有形的產(chǎn)品變成了無(wú)形的服務(wù)。

云計(jì)算提供的資源服務(wù)從具體應(yīng)用角度可分為三個(gè)層次，具體來(lái)說(shuō)就是基礎(chǔ)設(shè)施即服務(wù)（IaaS）、平臺(tái)即服務(wù)（PaaS）和軟件即服務(wù)（SaaS）。這三個(gè)層次各自側(cè)重于不同的應(yīng)用，但是卻包含著相同的問(wèn)題，即資源、任務(wù)調(diào)度問(wèn)題。調(diào)度問(wèn)題直接關(guān)系到云服務(wù)的穩(wěn)定性、用戶(hù)的滿意度、資源的利用率以及運(yùn)營(yíng)成本等。因此，對(duì)云計(jì)算的調(diào)度問(wèn)題展開(kāi)研究具有非常重要的現(xiàn)實(shí)意義及理論價(jià)值。

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

1.1 云環(huán)境下用戶(hù)獲取服務(wù)的流程

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

1.2 云環(huán)境下任務(wù)調(diào)度的新特性

云計(jì)算是在網(wǎng)格計(jì)算、并行計(jì)算、集群計(jì)算的基礎(chǔ)上發(fā)展起來(lái)的，因此他們的任務(wù)調(diào)度策略具有很大的相似性。但是，與網(wǎng)格計(jì)算等相比，云計(jì)算還表現(xiàn)了一些新的專(zhuān)有特性，可具體描述為：

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

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

（3） 云計(jì)算環(huán)境下的有效調(diào)度需要保證云計(jì)算服務(wù)商提供的云資源能夠得到充分利用并獲得最大收益。傳統(tǒng)的調(diào)度策略往往卻只是考慮如何滿足各用戶(hù)的QoS要求，而很少考慮資源服務(wù)商的經(jīng)濟(jì)效益。

（4） 用戶(hù)需求的多樣性和應(yīng)用類(lèi)型的復(fù)雜性使得云計(jì)算系統(tǒng)中能源成本成為一個(gè)重點(diǎn)關(guān)聯(lián)因素。云計(jì)算環(huán)境的商業(yè)化特點(diǎn)決定了必須引入能耗開(kāi)銷(xiāo)等因素來(lái)建立問(wèn)題模型，并藉此全面研究相應(yīng)的調(diào)度策略。

1.3 云環(huán)境下任務(wù)調(diào)度的目標(biāo)

云環(huán)境下，任務(wù)調(diào)度的目標(biāo)就是對(duì)用戶(hù)提交的所有任務(wù)實(shí)現(xiàn)最優(yōu)調(diào)度，并盡量提高云計(jì)算系統(tǒng)的總體吞吐率。具體的目標(biāo)包括：服務(wù)質(zhì)量（Quality of Service， QoS）、負(fù)載均衡、經(jīng)濟(jì)原則和節(jié)能減排等。具體分析如下：

（1） QoS。云環(huán)境下的任務(wù)調(diào)度系統(tǒng)必須滿足用戶(hù)的QoS。一方面，要根據(jù)應(yīng)用的特征提高資源的發(fā)現(xiàn)率和準(zhǔn)確性系數(shù)，保證用戶(hù)服務(wù)的性能QoS；另一方面，則需針對(duì)用戶(hù)的狀態(tài)變遷，動(dòng)態(tài)進(jìn)行資源選擇以及重定向，滿足用戶(hù)的經(jīng)濟(jì)QoS，有效地提高用戶(hù)滿意度。

（2） 負(fù)載均衡。由于云環(huán)境下計(jì)算資源是由大量計(jì)算機(jī)節(jié)點(diǎn)組成，復(fù)雜且異構(gòu)，這就使得負(fù)載均衡的實(shí)現(xiàn)具有相當(dāng)難度。

（3） 經(jīng)濟(jì)效益。由于云計(jì)算是一種新型的商業(yè)模式，其中的經(jīng)濟(jì)效益必然成為著重關(guān)注的調(diào)度指標(biāo)。該指標(biāo)的切實(shí)完善的真正實(shí)現(xiàn)將直接關(guān)系著云計(jì)算這一面向普適商業(yè)應(yīng)用計(jì)算模式的有效運(yùn)營(yíng)周期。

（4） 節(jié)能減排。云計(jì)算是超大規(guī)模的計(jì)算，每個(gè)數(shù)據(jù)中心的電力消耗均堪稱(chēng)巨大，在提倡綠色計(jì)算的背景環(huán)境下，云計(jì)算也必須將節(jié)能減排作為一個(gè)重要的追求目標(biāo)。

2 云環(huán)境下任務(wù)調(diào)度技術(shù)研究現(xiàn)狀

2.1側(cè)重性能的調(diào)度

作為任務(wù)調(diào)度研究的核心熱點(diǎn)，側(cè)重性能的任務(wù)調(diào)度的最終目標(biāo)就是性能，例如最優(yōu)跨度，任務(wù)最早完成時(shí)間等。目前使用比較廣泛的算法包括Min-Min算法、Max-Min算法、遺傳算法、貪心算法、蟻群算法和模擬退火算法等。

具體來(lái)說(shuō)，IBM公司的云計(jì)算平臺(tái)采用的就是以性能為中心的調(diào)度策略。而且，李建峰等人[2]基于MapReduce模型，提出了一種具有雙適應(yīng)度的遺傳算法（DFGA），該算法不僅能夠使總?cè)蝿?wù)的完成時(shí)間最短還能使任務(wù)的平均完成時(shí)間較短；湯小春等人[3]則提出了一種基于元區(qū)間的最佳分配決策算法，并取得了良好效果；還有，華夏渝等人[4]提出了一種基于蟻群優(yōu)化的資源分配算法，該算法適應(yīng)于具有最小響應(yīng)時(shí)間和最好服務(wù)質(zhì)量為其指標(biāo)要求的任務(wù)調(diào)度。另外，周文俊等人[5]針對(duì)靜態(tài)資源調(diào)度中只考慮任務(wù)完成時(shí)間最小化問(wèn)題，提出了一種基于預(yù)測(cè)的蟻群算法來(lái)滿足云環(huán)境下資源的動(dòng)態(tài)分配。

2.2側(cè)重服務(wù)質(zhì)量的調(diào)度

云計(jì)算是一種商業(yè)模型，其中的用戶(hù)QoS不僅關(guān)系到用戶(hù)的實(shí)際體驗(yàn)，而且將實(shí)際影響著云計(jì)算的良性發(fā)展。因此，基于QoS的任務(wù)調(diào)度算法研究也獲得蓬勃發(fā)展。一般情況下，算法研發(fā)框架除了要考慮最小完成時(shí)間或是最優(yōu)跨度，還有考慮服務(wù)質(zhì)量等問(wèn)題。

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

2.3側(cè)重經(jīng)濟(jì)原則的調(diào)度

除服務(wù)質(zhì)量外，云計(jì)算的商業(yè)運(yùn)行模式則使得經(jīng)濟(jì)因素也成為任務(wù)調(diào)度的重要指標(biāo)之一?；萜盏脑茢?shù)據(jù)中心采用的就是成本優(yōu)先調(diào)度策略。鄧見(jiàn)光等人[11]，在滿足QoS的前提條件下，從云服務(wù)提供商的角度出發(fā)，給出了一種基于成本的云任務(wù)調(diào)度策略。Buyya等人[12]進(jìn)而提出了面向市場(chǎng)的云計(jì)算以及面向市場(chǎng)的云計(jì)算構(gòu)架。葛新等人[13]再次提出了一種基于計(jì)算強(qiáng)度的調(diào)度策略，并且具有低成本的特點(diǎn)。該策略的主要思想是將計(jì)算量大的任務(wù)分配給計(jì)算能力強(qiáng)的集群調(diào)度，而將計(jì)算量小的任務(wù)則分配給計(jì)算能力弱的集群調(diào)度。另外，對(duì)于那些經(jīng)濟(jì)效益要求高而時(shí)間需求相對(duì)寬松的應(yīng)用，即可選擇計(jì)算能力弱的集群調(diào)度；但針對(duì)有嚴(yán)格時(shí)間要求的應(yīng)用將可申請(qǐng)計(jì)算能力強(qiáng)的集群調(diào)度，如此即能達(dá)到降低成本的目的。

2.4側(cè)重能耗優(yōu)化的調(diào)度

在提倡綠色計(jì)算的浪潮下，已有更多的學(xué)者正致力研究側(cè)重于能耗優(yōu)化的調(diào)度算法，并取得了可觀的成就。

文獻(xiàn)[14]中設(shè)計(jì)了基于動(dòng)態(tài)定價(jià)策略的數(shù)據(jù)中心能耗成本優(yōu)化方案，為研究基于能耗優(yōu)化的任務(wù)調(diào)度提供了基礎(chǔ)。該調(diào)度算法可以根據(jù)動(dòng)態(tài)的服務(wù)價(jià)格進(jìn)行調(diào)度，達(dá)到優(yōu)化能耗的目的。文獻(xiàn)[15]中則提出了兩種具有能量感知的任務(wù)調(diào)度算法，分別利用能耗時(shí)間歸一及能耗時(shí)間來(lái)定義適應(yīng)度函數(shù)，實(shí)驗(yàn)結(jié)果表明，與單獨(dú)考慮能耗或是時(shí)間相比，這兩種算法能夠有效降低能耗并縮短任務(wù)執(zhí)行時(shí)間。曹潔等人[16]也提出了兩種滿足并行任務(wù)截止時(shí)間要求和并行任務(wù)執(zhí)行能耗要求的調(diào)度方法Ssef和Egsa。實(shí)驗(yàn)結(jié)果表明，該算法在保證并行任務(wù)截止完成時(shí)間要求的前提下能夠有效降低并行任務(wù)的能源消耗，從而降低了云計(jì)算系統(tǒng)的能耗開(kāi)銷(xiāo)。

3 云環(huán)境下任務(wù)調(diào)度技術(shù)的研究展望

目前，根據(jù)云環(huán)境任務(wù)調(diào)度技術(shù)的研究進(jìn)程和現(xiàn)存問(wèn)題，給出了建議和設(shè)想，期望對(duì)任務(wù)調(diào)度的進(jìn)一步研究提供有益的借鑒。

3.1 基于用戶(hù)行為特征的調(diào)度策略研究

云計(jì)算環(huán)境中，用戶(hù)提交的任務(wù)數(shù)目將是海量，那么如何在資源有限的情況下，對(duì)海量任務(wù)進(jìn)行有效調(diào)度，同時(shí)資源也得到有效利用即已成為研究重點(diǎn)。針對(duì)此一問(wèn)題，可以從用戶(hù)的行為特征出發(fā)，通過(guò)統(tǒng)計(jì)用戶(hù)的行為習(xí)慣和預(yù)期的完成時(shí)間，來(lái)合理安排任務(wù)的科學(xué)調(diào)度，由此而提高資源利用率和用戶(hù)滿意度。

另一方面，當(dāng)用戶(hù)刪除、撤銷(xiāo)任務(wù)時(shí)，調(diào)度系統(tǒng)將相應(yīng)地采取一定的調(diào)度策略來(lái)適應(yīng)這種變化，從而避免了資源不必要的浪費(fèi)。

3.2 基于云任務(wù)多維屬性的節(jié)能的任務(wù)調(diào)度策略

綠色計(jì)算提出后，云環(huán)境下節(jié)能的任務(wù)調(diào)度的研究隨即也成為熱點(diǎn)問(wèn)題。已有的大部分研究均以數(shù)據(jù)中心的節(jié)能為其優(yōu)化目的，但迄今仍然少有根據(jù)任務(wù)的多維屬性來(lái)進(jìn)行任務(wù)調(diào)度從而達(dá)到節(jié)能效果的。云任務(wù)是海量的、差異性大的、偏好性強(qiáng)的，針對(duì)不同的任務(wù)需求給出相應(yīng)的資源分配方案，將能有效降低任務(wù)能耗。

4 結(jié)束語(yǔ)

云環(huán)境下的資源具有動(dòng)態(tài)多變、按需提供、按量付費(fèi)、任務(wù)差異大、任務(wù)偏好性強(qiáng)等特點(diǎn)?，F(xiàn)有的調(diào)度算法并不能完全滿足云任務(wù)調(diào)度要求。因此，云任務(wù)的調(diào)度是云計(jì)算領(lǐng)域的研究熱點(diǎn)之一。本文介紹了云任務(wù)調(diào)度的新特性及目標(biāo)，分析了國(guó)內(nèi)外云任務(wù)調(diào)度的研究現(xiàn)狀。盡管這些研究取得了頗豐的進(jìn)展，但也存在著一定的不足。很多工作仍需進(jìn)一步展開(kāi)深度的探討與研究。

參考文獻(xiàn)：

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

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

[3] 湯小春，劉健.基于元區(qū)間的云計(jì)算基礎(chǔ)設(shè)施服務(wù)的資源分配算研究[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（34）：237-241.

[4] 華夏渝，鄭俊，胡文心.基于云計(jì)算環(huán)境的蟻群優(yōu)化計(jì)算資源分配算法[J].華東師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，1（1）：127-134.

[5] 周文俊，曹鍵.基于預(yù)測(cè)及蟻群算法的云計(jì)算資源調(diào)度策略.計(jì)算機(jī)仿真[J].計(jì)算機(jī)仿真，2012（9）： 239-242+246.

[6] 李文娟，張啟飛，平玲娣，潘雪增.基于模糊聚類(lèi)的云任務(wù)調(diào)度算法[J].通信學(xué)報(bào)，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云資源調(diào)度優(yōu)化算法[J].電子學(xué)報(bào)，2011，39（8）：1824-1830.

[11] 鄧見(jiàn)光，趙躍龍，袁華強(qiáng)，等. 一種成本驅(qū)動(dòng)的云計(jì)算任務(wù)調(diào)度策略[J]. 江蘇大學(xué)學(xué)報(bào)： 自然科學(xué)版，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ì)算集群擴(kuò)展中的調(diào)度策略研究[J].計(jì)算機(jī)應(yīng)用研究，2011，28（3）： 995-997+100.

[14] 王魏，羅軍舟，宋愛(ài)波.基于動(dòng)態(tài)定價(jià)策略的數(shù)據(jù)中心能耗成本優(yōu)化[J].計(jì)算機(jī)學(xué)報(bào)，2013，36（3）：599-612.

[15] 英昌甜，于炯，楊興耀.云計(jì)算環(huán)境下能量感知的任務(wù)調(diào)度算法[J].微電子學(xué)與計(jì)算機(jī)，2012，29（5）：188-192.

[16] 曹潔，曾國(guó)蓀.云環(huán)境下計(jì)算資源動(dòng)態(tài)能耗感知的并行任務(wù)調(diào)度方法[J].計(jì)算機(jī)科學(xué)，2013，40（10）：39-44.