面向大規(guī)模云資源調(diào)度的可擴展分布式調(diào)度方法＊

林偉偉，朱朝悅

（華南理工大學計算機科學與工程學院，廣東 廣州510640）

1 引言

云計算技術(shù)［1，2］是分布式計算、并行計算、效用技術(shù)、網(wǎng)絡存儲等傳統(tǒng)計算機網(wǎng)絡技術(shù)發(fā)展和融合的產(chǎn)物，云服務模式基于互聯(lián)網(wǎng)為客戶提供動態(tài)的、易擴展的虛擬化的資源。云基礎(chǔ)設施不斷增長的需求大幅增加了云計算數(shù)據(jù)中心的能量消耗，高能耗不僅意味著高的運營成本，并且降低了云供應商的利潤率，同時也導致了高碳排放量，這是很不環(huán)保的。而對于云計算資源供應商來說，成本最小化和利潤最大化一直以來都是追求的目標，因此減少能源的消耗顯得非常重要［3，4］。如何高效利用能源已經(jīng)成為現(xiàn)代計算機系統(tǒng)（云計算中心）的一個非常重要的研究內(nèi)容［5］，從而實現(xiàn)高效節(jié)能、綠色、環(huán)保、低炭的云計算。在云計算環(huán)境中，云資源往往是異構(gòu)的、動態(tài)的［6］，有效地分配云計算資源是決定整個云計算系統(tǒng)的性能和效率的關(guān)鍵所在。云計算資源調(diào)度算法數(shù)學模型是整數(shù)規(guī)劃問題，很多資源調(diào)度算法以最短任務完成時間為調(diào)度目標，使用了啟發(fā)式算法求解次優(yōu)解［7］。隨著云計算的快速普及，經(jīng)濟效益成為資源調(diào)度的一個重要考慮因素，因此在模型中增加了經(jīng)濟度量參數(shù)，如能耗、機器價格、最遲完工時間等［8］。

云資源調(diào)度是云計算的重要研究內(nèi)容之一［9］。Beloglazov A 等人［10］提出了一個節(jié)能的云計算框架，他們利用啟發(fā)式的方法為客戶端應用程序提供數(shù)據(jù)中心資源，提高了數(shù)據(jù)中心的能源效率。Garg S K 等人［11］考慮了很多影響能源效率的因素（例如，能源消耗、CPU 功耗效率、工作量等等），他們提出一種接近最優(yōu)的調(diào)度策略，該策略利用橫跨不同數(shù)據(jù)中心之間的數(shù)據(jù)為云提供者服務。文獻［12］針對云計算的高能耗問題，從系統(tǒng)級節(jié)能角度，提出了一種節(jié)能的資源調(diào)度算法。作者建立云計算的兩級資源調(diào)度模型，綜合考慮主機的工作、空閑和休眠等多種狀態(tài)建立能耗模型，根據(jù)云任務的服務質(zhì)量需求產(chǎn)生初始種群，以系統(tǒng)能耗最小為調(diào)度目標設計適應度函數(shù)，并根據(jù)染色體適應度的正態(tài)分布函數(shù)和種群的進化代數(shù)設計遺傳算子。然而，云數(shù)據(jù)中心的服務器往往是異構(gòu)的，并且當云數(shù)據(jù)中心資源分配的問題規(guī)模比較大時，資源分配復雜度比較高，上面提到的云資源分配算法無法在可接受的時間范圍內(nèi)得出結(jié)果。米海波等人［13］為了提高大規(guī)模虛擬化集群環(huán)境的資源利用率，提出了一種面向數(shù)據(jù)中心的集群資源按需動態(tài)配置方法，利用了布爾二次指數(shù)平滑法預測用戶請求，這個方法能夠根據(jù)不斷變化的需求高效實時地調(diào)整集群中節(jié)點運行的數(shù)量，實現(xiàn)資源快速動態(tài)配置，從而提高集群利用率和降低能耗。Addis B 等人［14］提出了一個在多個時間范疇中基于混合整數(shù)非線性優(yōu)化資源管理的可伸縮分布式分層框架，目的是給出一個用于虛擬化云環(huán)境的資源分配策略，該策略能在滿足性能、可用性情況下最小化規(guī)模云服務中心的能耗開銷。文獻［15］提出了一種基于動態(tài)重配置虛擬資源的云計算資源調(diào)度方法，該方法以云應用監(jiān)視器收集的云應用信息為依據(jù)，基于運行云應用的虛擬資源的負載能力和云應用當前的負載進行動態(tài)決策，然后根據(jù)決策的結(jié)果為云應用動態(tài)重配置虛擬資源。通過云應用重配置虛擬資源的方法實現(xiàn)資源的動態(tài)調(diào)整，不需要動態(tài)重新分配物理機資源和停止云應用為執(zhí)行。該方法能根據(jù)云應用負載變化動態(tài)重置虛擬資源，優(yōu)化云計算資源分配，實現(xiàn)云計算資源的高效使用和滿足云應用動態(tài)可伸縮性的需要。文獻［16］中提出了一個在云計算環(huán)境中面向作業(yè)的資源調(diào)度模型，在這個調(diào)度模型中，資源分配任務分配到具有可用的資源和用戶首選項的進程中，根據(jù)作業(yè)的排名來分配計算機資源。文獻［17］為了實現(xiàn)云計算虛擬資源的有效調(diào)度和滿足用戶的QoS需求，提出了基于多維QoS滿足負載平衡的云資源調(diào)度方法。該調(diào)度算法首先建立一個云資源調(diào)度的數(shù)學模型和基于蟻群算法的虛擬資源調(diào)度算法，該方法能在一定程度上解決虛擬資源調(diào)度問題，可以減少負載平衡偏差，滿足云計算環(huán)境的需要。文獻［18］提出了利用約束滿足問題對異構(gòu)云數(shù)據(jù)中心的能耗優(yōu)化資源調(diào)度問題進行建模，通過求解建立的約束模型可以獲得能耗最優(yōu)的資源分配方式，并在此基礎(chǔ)上提出了能耗優(yōu)化的資源分配算法DYnamicpower（DY）。

然而，本質(zhì)上，云數(shù)據(jù)中心異構(gòu)物理服務器的能耗優(yōu)化資源分配問題是NP難的組合優(yōu)化問題，在問題規(guī)模較小時，可以使用分支定界法或動態(tài)規(guī)劃方法等最優(yōu)化方法來求解；當問題規(guī)模較大時，解的空間比較大，要在合理時間內(nèi)求得最優(yōu)解非常困難。為了解決當云服務器規(guī)模大而導致資源分配算法求解時間過長的問題，本文從調(diào)度模式方面提出一種可擴展分布式調(diào)度方法，并設計和實現(xiàn)面向異構(gòu)云環(huán)境的能耗高效的資源分配算法。當云數(shù)據(jù)中心待調(diào)度的物理服務器的數(shù)量比較大時，將所有待調(diào)度的服務器自動劃分為若干個服務器集群，然后在每個服務器集群中建立能耗優(yōu)化的資源分配約束模型，并利用Choco求解模型獲得能耗優(yōu)化的資源分配方式，通過分而治之的方法大大降低資源分配的復雜度，實現(xiàn)了能耗優(yōu)化和高能效的資源分配。

2 云資源可擴展分布式調(diào)度方法

2.1 問題描述

Hadoop資源調(diào)度是云計算研究的關(guān)鍵問題之一，調(diào)度算法的好壞決定了云計算服務的很多方面，比如計算效率、能耗等等。其中，資源調(diào)度算法在合理的時間內(nèi)決定分配的云資源顯得十分重要。以往的資源調(diào)度算法都是把物理機資源和虛擬機資源歸并在一起進行計算分配。圖1為傳統(tǒng)云數(shù)據(jù)中心資源分配算法的示意圖，所有的物理機和虛擬機都是在一次分配算法的運行中實現(xiàn)，這個時候的云資源分配便成了一個約束滿足問題的解決，先建立一個約束滿足問題模型，然后根據(jù)模型的優(yōu)化目標對模型進行求解，當云數(shù)據(jù)中心云服務器規(guī)模較小時，可以使用分支定界法或動態(tài)規(guī)劃方法等最優(yōu)化方法來求解。然而，由于基于約束滿足的資源分配模型的求解復雜度為服務器個數(shù)的指數(shù)復雜度，當云數(shù)據(jù)中心資源分配的問題規(guī)模非常大時（即當待調(diào)度的服務器數(shù)量非常大，例如數(shù)量為1 000），則不能在短時間內(nèi)求得最優(yōu)解。

Figure 1 Resources allocation of traditional cloud data centers圖1 傳統(tǒng)云數(shù)據(jù)中心的資源分配

2.2 基于服務器集群劃分的可擴展分布式調(diào)度方法設計

當云數(shù)據(jù)中心資源分配的問題規(guī)模比較大時，資源分配復雜度比較高。為此，本文提出的基于服務器集群劃分的可擴展分布式調(diào)度方法采用了分而治之的方法，將所有待調(diào)度的服務器劃分為若干個服務器集群，針對每個服務器集群建立能耗優(yōu)化的資源分配模型，求解模型和進行資源優(yōu)化分配，如圖2所示。將所有待調(diào)度的服務器劃分為若干個服務器集群，然后在每個服務器集群中利用約束編程框架Choco模擬實現(xiàn)約束滿足問題對異構(gòu)云數(shù)據(jù)中心的能耗優(yōu)化資源調(diào)度問題建模，通過求解建立的約束模型可以獲得能耗最優(yōu)的資源分配方式，從而大大降低資源分配的復雜度，實現(xiàn)能耗優(yōu)化和高能效的資源分配。

結(jié)合數(shù)據(jù)中心的實際情況，將數(shù)量很多的一個服務器集群分割成多個服務器集群要遵循一定的規(guī)則。也就是說按照一定的規(guī)則分割服務器集群，能夠最大化地利用服務器集群資源和虛擬機資源，避免不必要的資源浪費。而在每個分割好的小集群內(nèi)要實現(xiàn)局部的資源分配的最優(yōu)求解，也就是在小集群中使用最優(yōu)能耗資源調(diào)度算法，以能耗最優(yōu)為目標為分配的虛擬機搜索物理主機分配向量［18］。將最優(yōu)能耗資源調(diào)度算法表示成CSP 問題，采用最佳優(yōu)先和剪枝的策略來對其進行求解。首先需要將虛擬機分配向量重新整理，使之成為包含所有待分配虛擬機的簡單向量，整個過程實際上是一個搜索過程，搜索最優(yōu)的資源分配路徑，該過程使用開源的Choco工具模擬實現(xiàn)，求解在每個集群中以最優(yōu)能耗為目標的最優(yōu)調(diào)度方案。

Figure 2 Server cluster partitioning圖2 服務器集群劃分

3 算法設計

本文提出的可擴展分布式調(diào)度方法SDSM（Scalable Distributed Scheduling Method）具體由兩個算法部分組成：集群劃分算法SCA（Splitting Cluster Algorithm）和可擴展的能耗優(yōu)化調(diào)度算法SOECSA（Scalable Optimal Energy Consumption Scheduling Algorithm）。在可擴展分布式調(diào)度方法SDSM 中，首先是SCA 算法將待分配的服務器總資源和虛擬機總資源使用一定的規(guī)則分割成資源合適的各個小集群；然后使用SOECSA 算法將各個小集群分配好的資源進行能耗最優(yōu)的約束滿足求解，實現(xiàn)集群資源分配。

3.1 集群劃分算法

3.1.1 算法描述

圖3所示為集群劃分算法流程圖。

Figure 3 Process of cluster partitioning圖3 集群劃分流程

（1）首先輸入物理機、虛擬機資源（CPU、RAM）。

（2）設定分組大小Threshold，判斷物理機數(shù)是否大于Threshold，如果總的物理機數(shù)大于Threshold，則將所有的物理機分割成不同的等份或集群，每個等份最多包含個數(shù)為Threshold的物理機，最后一個集群的物理機數(shù)大于或小于Threshold，集 群 個 數(shù)groupNum＝PMN/Threshold，其中PMN為總的物理機數(shù)。

（3）對每個集群上的物理機資源進行統(tǒng)計，將各個集群累加起來的資源進行排序，每個集群資源越多，排序越前。

（4）在上一步驟中可以得知集群的個數(shù)為groupNum，故需要把虛擬機分割成groupNum等份，可以計算出每份虛擬機的個數(shù)為：cluster－Num＝VMN＊Threshold/PMN，其中VMN為總的虛擬機數(shù)。

（5）同樣，將每份虛擬機資源進行統(tǒng)計，對每份虛擬機資源進行排序。

（6）根據(jù)（3）和（5）統(tǒng)計得到各個物理機集群和各份虛擬機資源總和的排序，將虛擬機資源總和排序高的分配到物理機資源總和排序高的集群，也就是說將虛擬機資源多的那份分配到資源多的物理機集群上。

3.1.2 算法偽代碼

算法1 集群劃分算法

3.2 可擴展的能耗優(yōu)化調(diào)度算法

3.2.1 算法描述

將所有待調(diào)度的服務器按照上一節(jié)提到的集群劃分算法劃分為若干個服務器集群，然后在每個服務器集群中實現(xiàn)最優(yōu)能耗資源調(diào)度算法。最優(yōu)能耗資源調(diào)度算法的基本思想是以能耗最優(yōu)為目標為分配的虛擬機搜索物理主機分配向量［18］。將最優(yōu)能耗資源調(diào)度算法表示成CSP 問題，采用最佳優(yōu)先和剪枝的策略來對其進行求解。首先需要將虛擬機分配向量重新整理，使之成為包含所有待分配虛擬機的簡單向量。在搜索中，對于任一待擴展節(jié)點，如果到達該節(jié)點的路徑對應的能耗大于或等于最小能耗值，則停止對該節(jié)點的擴展；否則，繼續(xù)擴展該節(jié)點，若該節(jié)點是最后的葉節(jié)點，則更新最小能耗的值，最終返回使能耗最小的虛擬機放置向量。該過程使用開源的Choco工具模擬實現(xiàn)，求解在每個集群中后最優(yōu)能耗為目標的最優(yōu)調(diào)度方案。如圖4所示。

Figure 4 Optimal resource scheduling algorithm of energy consumption圖4 最優(yōu)能耗資源調(diào)度算法

3.2.2 算法偽代碼

算法２ 最優(yōu)能耗資源調(diào)度算法

3.2.3 算法性能分析

在最優(yōu)能耗資源調(diào)度算法中，假設要被分配的虛擬機數(shù)為p，物理機數(shù)為n，因此，最多只能部署p個要被分配的虛擬機在一個物理機。根據(jù)式（1）～式（4）可知，一共有3n個約束條件，根據(jù)Rivin I等人［19］關(guān)于CSP 代數(shù)求解的研究，對于一個有n個變量、每個變量取值數(shù)為m以及M個約束條件的CSP問題，其算法復雜度為O（nm·2M－n），故在最優(yōu)能耗資源調(diào)度中的算法復雜度為O（pn·4n）。

4 實驗與結(jié)果分析

本文的實驗將對SDSM 與非可擴展分布式調(diào)度方法進行對比。非可擴展分布式調(diào)度方法實際上只是實現(xiàn)了可擴展分布式調(diào)度方法（SDSM）中包含的兩個算法中的第二個算法（SOECSA），也就是說在非可擴展分布式調(diào)度方法中并不需要實現(xiàn)第一個集群劃分算法SCA，而只是單純地將所有的物理機資源和虛擬機資源匯總在一起實現(xiàn)能耗最優(yōu)的資源調(diào)度分配。

4.1 算法實現(xiàn)

為了驗證本文提出的面向能耗優(yōu)化的大規(guī)模云資源可擴展分布式調(diào)度方法，我們進行了相關(guān)的模擬實驗。首先是對所有待調(diào)度的服務器按照本文提到的集群劃分算法劃分為若干個服務器集群，然后在每個服務器集群中實現(xiàn)最優(yōu)能耗資源調(diào)度算法。最優(yōu)能耗資源調(diào)度算法可以被看作成一個約束滿足問題，利用基于Java的約束編程Choco對它們進行建模和求解，步驟如下：

（1）將所有的物理機分割成不同的等份或集群，每個等份最多包含個數(shù)為Threshold的物理機，最后一個集群的物理機數(shù)大于或小于Threshold，集群個數(shù)GroupNum＝PMN/Threshold。對每個集群上的物理機資源進行統(tǒng)計，將各個集群累加起來的資源進行排序，每個集群資源越多，排序越前。

（2）在上一步驟中可以得知集群的個數(shù)為GroupNum，故需要把虛擬機分割成GroupNum等份，可以計算出每份虛擬機的個數(shù)為：Cluster－Num＝VMN＊Threshold/PMN。同樣，將每份虛擬機資源進行統(tǒng)計，對每份虛擬機資源進行排序。

（3）根據(jù)（1）和（2），統(tǒng)計得到各個物理機集群和各份虛擬機資源總和的排序，將虛擬機資源總和排序高的分配到物理機資源總和排序高的集群，也就是說將虛擬機資源多的那份分配到資源多的物理機集群上。

（4）在每個服務器集群中實現(xiàn)最優(yōu)能耗資源調(diào)度算法，通過Choco工具包提供的方法和接口來定義CSP問題中的X（有限變量）、D（變量的有限域）、C（約束），具體如下：

①設定變量（列出主要變量）及其作用域：

其中，變量pos是一個橫坐標為虛擬機編號、縱坐標為物理機編號的表示虛擬機在物理機上分配向量的二維數(shù)組；變量dualpos與變量pos相反，橫坐標為物理機編號，縱坐標為虛擬機編號；power為本次分配所產(chǎn)生的總能耗；DYAPOWER是本次分配產(chǎn)生的動態(tài)總能耗；STAPOWER是本次分配所產(chǎn)生的靜態(tài)總能耗；pmsum為本次分配總共開啟的物理機總數(shù)。

②約束。由之前的資源約束條件可知有如下約束：

③目標函數(shù)。

s.minimize（false）；

s.setObject（power）；

即將power作為目標變量，以求解其最小數(shù)值（最小能耗）為最終目標來運行求解器的搜索循環(huán)。

4.2 實驗環(huán)境與實驗數(shù)據(jù)

云數(shù)據(jù)中心服務器的資源總是有限的，而虛擬機所需的資源也不可能是無限大的，因此本文對物理機和虛擬機資源測試數(shù)據(jù)進行了一定的限制，如表1所示。

Table 1 Related parameters of physical machines and virtual machines表1 物理機和虛擬機資源相關(guān)參數(shù)

在本文實驗中，能耗是一種能源消耗的數(shù)據(jù)表現(xiàn)，是一種量的表達，實際上電腦的平均功率是大概150 W 左右，當然電腦性能的不同也導致功率的不同，因此本文采用一種比較直觀的方式對能耗進行描述。所有能耗都是以整數(shù)的形式表示出來，這些能耗表示了每小時的能耗值，并且這些能耗都在一個可控制的范圍之內(nèi)。因此，有以下的能耗假設：每臺物理機的靜態(tài)能耗（Static Power）都與它的CPU 和RAM 資源大小有關(guān)，資源越大，靜態(tài)能耗越大，根據(jù)上面提到的計算方法對靜態(tài)能耗進行分配得到每臺物理機在空閑狀態(tài)時產(chǎn)生的靜態(tài)能耗在60～640。而每臺虛擬機在物理機上的動態(tài)能耗主要與虛擬機的CPU 和RAM 資源大小有關(guān)，因此根據(jù)上面提到的計算方法得到每臺虛擬機所產(chǎn)生的動態(tài)能耗限定在20～160。同時，物理機數(shù)為10～200個和虛擬機數(shù)為20～400個。

4.3 實驗結(jié)果

為了驗證本文提出的可擴展分布式調(diào)度方法SDSM 的可行性，本文的實驗分成兩個部分：實驗1中將Threshold設定為50，在不同的物理機數(shù)量下，SDSM 與非可擴展分布式調(diào)度方法進行對比；實驗2中將Threshold分別設置為20和50，對比可擴展分布式調(diào)度方法（SDSM）在不同Threshold的實驗數(shù)據(jù)。

4.3.1 實驗1

在可擴展分布式調(diào)度方法中，設置Threshold為50，與非可擴展分布式調(diào)度方法進行資源分配得到的運行時間、能耗總量、啟用的物理機數(shù)量進行比較，如表2所示。

由表2可以看出，非可擴展分布式調(diào)度方法在運行時間方面遠遠大于可擴展分布式調(diào)度方法。原因在于當物理機數(shù)量規(guī)模較大時，基于約束滿足的資源分配模型的求解復雜度為服務器個數(shù)的指數(shù)復雜度，如果一次性進行約束求解，求解的空間比較大，因此導致求解的時間會很大。然而，將較大規(guī)模的物理機集群分割成幾個較小規(guī)模的集群，再對各個小集群進行約束求解，由于問題規(guī)模比較小時，約束求解的空間會很小，這樣每個小集群約束求解運行時間相對來說小很多，各個小集群的求解時間匯總之后也是遠遠比沒有分割之前的運行時間短。

Table 2 Running time comparison of the two scheduling methods（Threshold＝50）表2 兩種調(diào)度方法（Threshold＝50）運行時間對比

由圖5可以看出，非可擴展分布式調(diào)度方法在能耗優(yōu)化方面稍微比可擴展分布式調(diào)度方法好一點。因為將服務器分割成了各個小集群之后，分配到每個小集群對應的虛擬機資源只能分配到對應的物理機集群中，也就是說，在Choco約束求解的過程中，如果將最少能源消耗作為目標進行約束求解，每個小集群只能求解其集群的最優(yōu)解，相對所有的服務器來說，每個小集群的最優(yōu)解只是局部最優(yōu)解而已，無法做到全局最優(yōu)。所以，匯總所有的求解結(jié)果，非可擴展分布式調(diào)度方法在能耗優(yōu)化方面會比可擴展分布式調(diào)度方法好，但是隨著服務器數(shù)量的大大增加，能源優(yōu)化方面的差距會越來越少。

Figure 5 Energy consumption comparison圖5 能耗比較

圖6顯示了非可擴展分布式調(diào)度方法在啟用的服務器數(shù)量方面比可擴展分布式調(diào)度方法要好，原因跟能耗優(yōu)化方面相類似，當服務器分割成各個小集群，只能在各自的小集群中進行約束求解，這樣導致要啟用的服務器總數(shù)相對增加。但是，隨著服務器數(shù)量的大大增加，啟用的服務器總數(shù)方面的差距也會縮小。

Figure 6 Comparison of the numbers of running physical machines圖6 啟用的物理機數(shù)量比較

4.3.2 實驗2

在可擴展分布式調(diào)度方法實驗中，將Threshold分別設置為20和50進行實驗數(shù)據(jù)比較。

由圖7可以看出，Threshold為20 時的運行時間比Threshold為50時的相對快很多。原因在于當Threshold越小時，服務器集群被分割得越細，因此每個集群的求解空間將會大大減少，所以求解時間相對來說很小，就算匯總所有小集群的運行時間，優(yōu)勢也會很明顯。從圖8 可以看出，Threshold越小時，各個集群總的能源消耗相對增多，因為Threshold越小，被分割的集群數(shù)越多，所有的集群只能采用各自分配好的虛擬機資源進行約束求解，因此，總的能耗會相對多一點。圖9顯示了不同Threshold求解之后啟用的物理機總數(shù)的不同，Threshold越小，啟用的物理機數(shù)量越多，原因跟Threshold影響總能耗類似。

Figure 7 Comparison of running time under different Thresholds圖7 不同Threshold 下運行時間對比

Figure 8 Comparison of energy consumption under different Thresholds圖8 不同Threshold 下能耗對比

Figure 9 Comparison of the numbers of running machines under different Thresholds圖9 不同Threshold 下啟用物理機數(shù)量對比

總的來說，當Threshold越小時，集群被分得越細，集群數(shù)越多，可以在服務器數(shù)量很龐大時明顯地縮小資源分配的時間。但是，這樣做也有一定的缺點，那就是會導致能耗優(yōu)化和啟用服務器數(shù)量方面比不上Threshold比較大的情況。雖然這種將服務器集群劃分的可擴展分布式調(diào)度方法在一定程度上影響了資源分配優(yōu)化的結(jié)果，然而，當待調(diào)度的服務器數(shù)量非常大時，對資源分配優(yōu)化結(jié)果的影響會變得越來越小。

5 結(jié)束語

本文研究了在云數(shù)據(jù)服務器數(shù)量規(guī)模比較大的情況下能耗優(yōu)化和資源分配效率問題。當云數(shù)據(jù)中心待調(diào)度的物理服務器的規(guī)模比較大時，資源分配算法的求解空間很大，導致很難在合理的時間內(nèi)求出能耗優(yōu)化的資源分配方案。針對該問題，本文從調(diào)度模式方面提出可擴展分布式調(diào)度方法SDSM，并設計和實現(xiàn)了面向大規(guī)模云環(huán)境的能耗高效的資源分配算法。當服務器的規(guī)模比較大時，將所有待調(diào)度的服務器劃分為若干個服務器集群，然后在每個服務器集群中利用約束編程框架Choco實現(xiàn)約束滿足問題，對云數(shù)據(jù)中心的能耗優(yōu)化資源調(diào)度問題建模，通過求解建立的約束模型可以獲得能耗最優(yōu)的資源分配方式，從而大大降低資源分配的復雜度，實現(xiàn)了能耗優(yōu)化和高能效的資源分配。模擬實驗的結(jié)果驗證了本文提出的可擴展分布式調(diào)度方法的有效性。本文提出的可擴展分布式調(diào)度方法SDSM 可以應用到云計算中心，很大程度上解決大規(guī)模云服務器分配資源效率低的問題，不僅能夠降低云計算中心能耗成本，并且提高了云資源分配速度。

［1］ Qusay H F.Demystifying cloud computing［J］.The Journal of Defense Software Engineering（CrossTalk），2011，（Jan/Feb）：16－21.

［2］ Mell P，Grance T，Mell P，et al.The NIST Definition of Cloud Computing（draft）.National Institute of Standards and Technology［J］.Appl Opt，2011，145（16）：1－7.

［3］ Srikantaiah S，Kansal A，Zhao F.Energy aware consolidation for cloud computing［C］∥Proc of HotPower’08，2008：1－15.

［4］ Berl A，Gelenbe E，Girolamo M，et al.Energy－efficient cloud computing［J］.The Computer Journal，2010，53（7）：1045－1051.

［5］ Beloglazoy A，Buyya R，Lee C Y，et al.A taxonomy and survey of energy－efficient data centers and cloud computing systems［J］.Advances in Computers，2011，82（2）：47－111.

［6］ Liu L，Wang H，Liu X，et al.Greencloud：A new architecture for green data center［C］∥Proc of ICAC－INDST’09，2009：29－38.

［7］ Jinquan Z，Lina N，Changjun J.A heuristic scheduling strategy for independent tasks on grid［C］∥Proc of International Conference on High－Performance Computing in Asia－Pacific Region，2005：588－593.

［8］ Shi Xue－lin，Xu Ke.Utility maximization model of virtual machine scheduling in cloud environment［J］.Chinese Journal of Computers，2013，36（2）：252－261.（in Chinese）

［9］ Lin Wei－wei，Qi De－yu.Survey of resource scheduling in cloud computing［J］.Computer Science，2012，39（10）：1－6.（in Chinese）

［10］ Beloglazov A，Abawajy J，Buyya R.Energy－aware resource allocation heuristics for efficient management of data centers for cloud computing［J］.Future Generation Computer Systems，2012，28（5）：755－768.

［11］ Garg S K，Yeo C S，Anandsivam A，et al.Environment conscious scheduling of HPC applications on distributed cloudoriented data centers［J］.Journal of Parallel and Distributed Computing，2011，71（6）：732－749.

［12］ Cheng Chun－ling，Pan Yu，Zhang Deng－yin，et al.Energy saving resource scheduling algorithm in cloud environment［J］.Systems Engineering and Electronics，2013，35（11）：2416－2423.

［13］ Mi Hai－bo，Wang Huai－min，Yin Gang，et al.Resource ondemand reconfiguration method for virtualized data centers［J］.Journal of Software，2011，22（9）：2193－2205.（in Chinese）

［14］ Addis B，Ardagna D，Panicucci B，et al.A hierarchical approach for the resource management of very large cloud platforms［J］.IEEE Transactions on Dependable ＆Secure Computing，2013，10（5）：253－272.

［15］ Lin Wei－wei，Qi De－yu.Cloud computing resource scheduling method based on dynamic reconfiguration of virtual resources：China，patent number：ZL2010102681057［P］.2011－01－05.（in Chinese）

［16］ Vignesh V，Sendhil Kumar K S，Jaisankar N.Resource management and scheduling in cloud environment［J］.International Journal of Scientific and Research Publications，2013，3（6）：1.

［17］ Zemin Z，Qing Z.Resource scheduling with load balance based on multi－dimensional QoS and cloud computing［J］.Computer Measurement ＆Control，2013（1）：087.

［18］ Lin Wei－wei，Liu Bo，Zhu Liang－chang，et al.CSP－based resource allocation model and algorithms for energy－efficient cloud computing［J］.Journal of Communication，2013，34（12）：33－41.（in Chinese）

［19］ Rivin I，Zabih R.An algebraic approach to constraint satisfaction problem［C］∥Proc of IJCAI’89，1989：284－289.

［20］ Rodero I，Jaramillo J，Quiroz A.Energy－efficient application－aware online provisioning for virtualized clouds and data centers［C］∥Proc of 2010International Green Computing Conference，2010：31－45.

附中文參考文獻：

［8］ 師雪霖，徐恪.云虛擬機資源分配的效用最大化模型［J］.計算機學報，2013，36（2）：252－261.

［9］ 林偉偉，齊德昱.云計算資源調(diào)度研究綜述［J］.計算機科學，2012，39（10）：1－6.

［12］ 程春玲，潘鈺，張登銀.云環(huán)境下一種節(jié)能的資源調(diào)度算法［J］.系統(tǒng)工程與電子技術(shù)，2013，35（11）：2416－2423.

［13］ 米海波，王懷民，尹剛，等.一種面向虛擬化數(shù)字中心資源按需重配置方法［J］.軟件學報，2011，22（9）：2193－2205.

［15］ 林偉偉，齊德昱.一種基于動態(tài)重配置虛擬資源的云計算資源調(diào)度方法：中國，專利號：ZL2010102681057［P］.2011－01－05.

［18］ 林偉偉，劉波，朱良昌，等.基于CSP 的能耗高效云計算資源調(diào)度模型與算法［J］.通信學報，2013，34（12）：33－41.