林偉偉，劉波，朱良昌，齊德昱

(1. 華南理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，廣東 廣州 510006；2. 華南師范大學(xué) 計(jì)算機(jī)學(xué)院，廣東 廣州 510631)

1 引言

隨著云計(jì)算技術(shù)的發(fā)展和云應(yīng)用的普及，云計(jì)算現(xiàn)在已經(jīng)被越來越多的企業(yè)接受，并同時對其展開了廣泛的研究[1]。最近幾年，隨著計(jì)算機(jī)系統(tǒng)電能消耗的不斷增加，能源的高效利用已經(jīng)成為現(xiàn)代計(jì)算機(jī)系統(tǒng)(如數(shù)據(jù)中心和云端)的一個非常重要的研究內(nèi)容[2]。近期，有一些關(guān)于云計(jì)算的資源提供與云計(jì)算資源管理的研究，其中GARG等[3]提出一種接近最優(yōu)的調(diào)度策略，該策略利用橫跨不同數(shù)據(jù)中心之間的數(shù)據(jù)為云提供者服務(wù)。他們考慮了許多影響能源效率的因素(例如：能源消耗、碳排放速度、工作量、CPU功耗效率)，這些因素依據(jù)其位置、結(jié)構(gòu)設(shè)計(jì)和管理系統(tǒng)的不同而在各個數(shù)據(jù)中心進(jìn)行變化。為了解決這一問題，出現(xiàn)了一些基于裝箱問題部署虛擬服務(wù)器的優(yōu)化方法，在一些文獻(xiàn)中有其具體的描述[4～8]，關(guān)于虛擬機(jī)的部署問題就被建模為裝箱問題。然而，目前提出的面向能耗優(yōu)化的調(diào)度方法大部分是針對同構(gòu)服務(wù)器的調(diào)度[7,9～13]，但是，由于現(xiàn)有的數(shù)據(jù)中心服務(wù)器的采購時間不同、使用年限不同及品牌不同等異構(gòu)性，比如文獻(xiàn)[13]描述的數(shù)據(jù)中心的服務(wù)器往往是異構(gòu)的，因此，目前提出的大部分同構(gòu)服務(wù)器調(diào)度方法不能很好地應(yīng)用在一般的云計(jì)算數(shù)據(jù)中心的能耗管理中。

為此，本文針對異構(gòu)物理服務(wù)器的能耗優(yōu)化資源調(diào)度問題進(jìn)行研究，利用約束滿足問題[14]對異構(gòu)物理服務(wù)器的能耗優(yōu)化資源調(diào)度問題建模，并基于Choco[15]約束編程求解建立的能耗優(yōu)化資源分配模型，能夠減少虛擬化的云數(shù)據(jù)中心的服務(wù)器能源消耗。然后，設(shè)計(jì)了資源調(diào)度算法來實(shí)現(xiàn)該優(yōu)化配置方案。最后，使用Choco模擬實(shí)驗(yàn)進(jìn)行算法評價(jià)，實(shí)驗(yàn)結(jié)果表明提出的模型和算法在能耗方面明顯優(yōu)于已有的資源調(diào)度方法。

2 相關(guān)研究

減少能源的消耗對于資源供應(yīng)商減少成本和利潤最大化來說非常重要[16,17]。BELOGLAZOV等[18]提出了一種用于虛擬機(jī)化云計(jì)算數(shù)據(jù)中心的有效的資源管理系統(tǒng)，它可以減少運(yùn)營成本并提供所需的服務(wù)質(zhì)量。節(jié)約能源是通過虛擬機(jī)不斷地依據(jù)當(dāng)前的資源利用率以及虛擬機(jī)和熱狀態(tài)下的計(jì)算節(jié)點(diǎn)之間建立的虛擬拓?fù)渚W(wǎng)絡(luò)結(jié)構(gòu)來進(jìn)行整合的。RODERO等[19]為高性能計(jì)算和虛擬化計(jì)算平臺提出了一種能量感知型的網(wǎng)絡(luò)配置方法。能源效率的提高是通過工作量的感知，恰到好處地動態(tài)配置機(jī)制以及通過關(guān)閉主機(jī)系統(tǒng)中沒有映射虛擬機(jī)的子系統(tǒng)方法來實(shí)現(xiàn)的。ABDELSALAM等[20]創(chuàng)建了一個用于云計(jì)算環(huán)境，主要服務(wù)于客戶的如Web服務(wù)一樣的交互式應(yīng)用的電力管理數(shù)學(xué)模型，這個數(shù)學(xué)模型計(jì)算服務(wù)器的最優(yōu)數(shù)量和它們應(yīng)該運(yùn)行的頻率。文獻(xiàn)[21]中，作者提出了一個提供高效、綠色、強(qiáng)化的可擴(kuò)展的云計(jì)算架構(gòu)的新框架。通過使用電力調(diào)度技術(shù)、可變的資源管理、實(shí)時調(diào)度和最小化的虛擬機(jī)設(shè)計(jì)等技術(shù)，使基于最小化云開銷的數(shù)據(jù)中心系統(tǒng)的整體功效得到了改善，CHANG等[22]對云資源的優(yōu)化配置進(jìn)行了研究。他們制定了關(guān)于計(jì)算能力和其他資源的多樣性的資源分配問題。他們提出了一個可證明的在多項(xiàng)式時間內(nèi)得到接近最優(yōu)解的近似算法。然而現(xiàn)今的方法大都考慮的是給予的每個物理機(jī)節(jié)點(diǎn)上有著相同的物理參數(shù)，如CPU速度、硬盤容量、內(nèi)存等。

此外，絕大部分方法僅將處理器作為唯一值得考慮的資源，而拋棄了其他一些同樣很重要的資源，例如內(nèi)存和存儲空間。這樣就導(dǎo)致由于工作量大量聚集在同一個節(jié)點(diǎn)而形成瓶頸，導(dǎo)致性能的下降以及能量消耗的增加，這個在文獻(xiàn)[23]中有所提及。在運(yùn)行時虛擬機(jī)實(shí)現(xiàn)再分配的能力，可以動態(tài)地配制工作量，同時可以使虛擬機(jī)實(shí)現(xiàn)重新部署，使運(yùn)行的物理機(jī)節(jié)點(diǎn)達(dá)到最小，而空閑節(jié)點(diǎn)則切換為省電模式。然而虛擬機(jī)的遷移會導(dǎo)致時間延遲、額外的性能開銷以及功耗，所以需要通過仔細(xì)分析和智能技術(shù)消除這些因工作量變化而導(dǎo)致的非生產(chǎn)性的遷移[2]。

裝箱問題是一個著名的NP組合難題，已提出許多啟發(fā)式和貪心算法來解決這難題[9,24]。一些啟發(fā)式算法，例如first-fit decreasing (FFD)[10]、best-fit decreasing(BFD)[10]和modified best fit decreasing(MBFD)[25]都被提出來和應(yīng)用在數(shù)據(jù)中心的虛擬機(jī)調(diào)度中[4～8]。這些方法大部分是針對同構(gòu)服務(wù)器的調(diào)度，不能很好地應(yīng)用在一般的異構(gòu)云計(jì)算數(shù)據(jù)中心的資源調(diào)度和能耗管理中。CSP(約束滿足問題)[26]：由一個變量集合和一個約束集合組成；問題的一個狀態(tài)是由對一些或全部變量的一個賦值定義的；問題的解是滿足所有約束的完全賦值，或更進(jìn)一步，使目標(biāo)函數(shù)最大化。約束滿足問題作為人工智能研究的一個基本問題，在許多實(shí)際問題中都得到了廣泛的應(yīng)用，特別是調(diào)度中的資源分配問題。為此，本文主要是針對物理服務(wù)器異構(gòu)的云數(shù)據(jù)中心的資源調(diào)度問題進(jìn)行研究，給出異構(gòu)物理服務(wù)器環(huán)境下的能耗優(yōu)化的資源調(diào)度模型和算法，減少云數(shù)據(jù)中心的能源消耗。

3 基于CSP的能耗優(yōu)化資源分配模型

3.1 問題描述

最直觀的節(jié)能減排方式就是關(guān)閉利用率不高的服務(wù)器，在傳統(tǒng)模式中，一個應(yīng)用運(yùn)行在一個服務(wù)器上，關(guān)閉服務(wù)器就等于關(guān)閉了應(yīng)用；然而，服務(wù)器虛擬化為解除應(yīng)用與物理服務(wù)器的綁定提供了可能，在負(fù)載低谷期，管理員可以將原來運(yùn)行在各個服務(wù)器上的應(yīng)用整合到較少的幾臺服務(wù)器上，關(guān)閉空閑的服務(wù)器，已達(dá)到綠色節(jié)能的目的。因而，一般能耗中的優(yōu)化問題就是最小化物理主機(jī)數(shù)；但是，在考慮物理主機(jī)異構(gòu)的情況，由于每個物理主機(jī)都有不同能耗，此時，能耗優(yōu)化的問題并不是最小物理主機(jī)數(shù)。下面舉個例子進(jìn)行具體說明。

物理服務(wù)器和虛擬機(jī)的資源大小及能耗參數(shù)如圖1所示，其中Dy1～3表示當(dāng)虛擬機(jī)VM1～3分配到該物理節(jié)點(diǎn)時產(chǎn)生的動態(tài)能耗。待部署的虛擬機(jī)以及其參數(shù)如圖2所示。假設(shè)需要將這3臺虛擬機(jī)部署在這3個物理節(jié)點(diǎn)上。如果采用最小主機(jī)數(shù)策略，3臺物理機(jī)都應(yīng)該分配到PM1上，這時的總能耗為650 W；若將VM1和VM2部署在PM2上，VM3部署在PM3上，則總能耗為420 W，可見，在物理主機(jī)異構(gòu)的情況下，能耗的優(yōu)化問題并不是最小物理主機(jī)數(shù)，而是綜合能耗最小。針對上述問題，本文提出了一個基于CSP的能耗優(yōu)化的云資源調(diào)度框架，該框架的系統(tǒng)架構(gòu)如圖2所示。

圖1 物理服務(wù)器與虛擬機(jī)的資源大小及能耗參數(shù)

圖2 基于CSP的能耗優(yōu)化的云資源調(diào)度框架

從圖2可以看出，提出的基于CSP的能耗優(yōu)化的云資源調(diào)度框架由應(yīng)用程序檢測、虛擬機(jī)配置和虛擬機(jī)部署3個模塊組成。本文將在3.2節(jié)～3.4節(jié)分別對各模塊進(jìn)行詳細(xì)描述。在詳細(xì)描述之前，先對部分符號進(jìn)行如下說明。

3.2 應(yīng)用程序監(jiān)測模塊

該模塊首先測出各應(yīng)用程序當(dāng)前的負(fù)載，然后根據(jù)當(dāng)前負(fù)載和 SLA目標(biāo)確定分配給各應(yīng)用程序的資源(CPU、memory、network)。對于應(yīng)用程序ai，其分配的資源可以定義為當(dāng)前負(fù)載和SLA目標(biāo)的函數(shù)，即：Ri= fi(Li,Si)，其中，Li為應(yīng)用程序ai的當(dāng)前負(fù)載，Si為應(yīng)用程序的SLA目標(biāo)，Ri為分配給應(yīng)用程序的資源，它是(CPU、memory、network)三元組。對于分配給應(yīng)用程序ai的資源與其當(dāng)前負(fù)載和SLA目標(biāo)的函數(shù)關(guān)系fi，本文沒有做出基于經(jīng)驗(yàn)的或基于實(shí)驗(yàn)的假設(shè)，它可以由各數(shù)據(jù)中心的管理者根據(jù)相應(yīng)的管理政策、經(jīng)驗(yàn)以及大量實(shí)驗(yàn)數(shù)據(jù)而確定。

下面以 VAN等人[11]關(guān)于自動化虛擬資源管理研究中提到的一個基于實(shí)驗(yàn)數(shù)據(jù)的經(jīng)驗(yàn)主義的性能模型(如圖 3所示)為例，對應(yīng)用程序監(jiān)測模塊進(jìn)行簡單說明。

圖3 性能模型

水平軸表示應(yīng)用程序每秒的請求量，即工作負(fù)載；垂直軸表示響應(yīng)時間；圖中的斜線表示特定CPU能力下響應(yīng)時間與每秒請求數(shù)的關(guān)系。假設(shè)應(yīng)用程序A是一個Web應(yīng)用程序，其SLA目標(biāo)是請求的響應(yīng)時間，假設(shè)其值為100 ms，若此刻應(yīng)用程序A的負(fù)載為每秒300次請求，則根據(jù)圖3所示的關(guān)系可以得出分配給應(yīng)用程序A的CPU能力至少為10 000 MHz。

當(dāng)然，上面只是一個可能的簡單示例，不同應(yīng)用程序的應(yīng)用程序有著不同的 SLA目標(biāo)、不同類型的工作負(fù)載以及它們之間的不同函數(shù)關(guān)系。在提出的模型中，沒有對這些性質(zhì)做任何可能的假設(shè)，它們應(yīng)該由數(shù)據(jù)中心管理員根據(jù)不同類型的應(yīng)用程序，基于經(jīng)驗(yàn)或?qū)嶒?yàn)數(shù)據(jù)對這些性質(zhì)進(jìn)行描述與設(shè)定。

3.3 虛擬機(jī)配置模塊

該模塊根據(jù)應(yīng)用監(jiān)測程序模塊輸出的分配給各應(yīng)用程序的資源向量R=(R1,…, Rj,…, Rc)為各應(yīng)用程序分配虛擬機(jī)，使總的分配代價(jià)最小。換句話說，該模塊的目的是給出使目標(biāo)函數(shù)(1)最小化的各應(yīng)用程序的虛擬機(jī)分配向量為

其中，m為應(yīng)用程序的數(shù)目，cost為虛擬機(jī)的操作開銷向量，每一項(xiàng)對應(yīng)于每一類虛擬機(jī)的分配開銷，Ni為分配給應(yīng)用程序i的虛擬機(jī)向量，并且Ni=（ni1,…,nij,…, nic），而nij為分配給應(yīng)用程序 i的第j類虛擬機(jī)的數(shù)量，cost·Ni則表示分配虛擬機(jī)向量Ni給應(yīng)用程序i的開銷。

根據(jù)本文的假設(shè)，數(shù)據(jù)中心中每類虛擬機(jī)的數(shù)目是有限的，即擁有一個上限閾值，下面定義各類虛擬機(jī)的閾值向量為：Nmax=(n1max,…, njmax,…, ncmax），且有如下關(guān)系

分配給各應(yīng)用程序資源量應(yīng)滿足應(yīng)用程序監(jiān)測模塊確定的資源要求，即

同時，部署在物理機(jī)上的所有虛擬機(jī)的資源總量不能超過所有物理機(jī)的資源總量，故有如下關(guān)系

采用約束編程的方法對上述模型進(jìn)行求解，即可獲總花費(fèi)最小的虛擬機(jī)分配向量，每一個虛擬機(jī)分配向量對應(yīng)于各應(yīng)用程序的虛擬機(jī)分配情況，即分配了哪類虛擬機(jī)及各類虛擬機(jī)分配的數(shù)量。

3.4 虛擬機(jī)部署模塊

虛擬機(jī)部署模塊將虛擬機(jī)分配模塊產(chǎn)生的虛擬機(jī)分配向量N作為輸入，然后將虛擬機(jī)分配向量N整合為表示當(dāng)前所有需要運(yùn)行的虛擬機(jī)集合的向量VM = (vm1,…,vmi,…,vmp)，其中，vmi= (vmiCPU, vmimemory,vminetwork)。同時數(shù)據(jù)中心提供每臺物理主機(jī)的動態(tài)能耗參數(shù)。在描述物理資源約束前，先給出虛擬機(jī)放置的定義。

位向量Hi的定義為：?pi∈P，Hi= (hi1,…,hij,…, hip)，hij=1當(dāng)且僅當(dāng)虛擬機(jī)vmj部署在物理機(jī)pi上。

對于每臺物理機(jī)和其上部署的虛擬機(jī)有如下的約束關(guān)系

根據(jù)文獻(xiàn)[28]可知，物理服務(wù)器的能耗為空閑時產(chǎn)生的能耗和其上運(yùn)行的應(yīng)用所產(chǎn)生的能耗之和為E = Edynamic+ Estatic，其中 Estatic表示物理機(jī)空閑時的能耗（即沒有分配虛擬機(jī)時的能耗，物理服務(wù)器 pi上的空閑能耗用 Eistatic表示），假設(shè)物理機(jī) pi上放置各虛擬機(jī)資源時新增能耗的向量為 Eidynamic=(ei1,… ,eik)，而 Edynamic為放置在物理服務(wù)器 pi上所有虛擬機(jī)新增能耗之和 H ?Edynamic。因此，可以建立異構(gòu)服務(wù)器的

i i能耗最優(yōu)（?。┑馁Y源調(diào)度模型為

其中，Ei為物理服務(wù)器 pi的能耗。由此可以得出關(guān)于能耗的約束條件為

其中， EiM

ax為物理服務(wù)器 pi所能承載的最大能耗值，即物理服務(wù)器ip的實(shí)際能耗大小必須小于等于MaxiE 。

4 算法設(shè)計(jì)

4.1 虛擬機(jī)配置算法

4.1.1 算法描述

虛擬機(jī)配置算法的基本思想是為需要部署的應(yīng)用搜索操作開銷最小的虛擬機(jī)，并輸出分配的虛擬機(jī)向量。首先將虛擬機(jī)配置問題表示成 CSP問題，采用最佳優(yōu)先和剪枝的策略對其進(jìn)行搜索求解。對于任一待擴(kuò)展節(jié)點(diǎn)，如果到達(dá)該節(jié)點(diǎn)的路徑對應(yīng)的花費(fèi)大于或等于最小花費(fèi)值，則停止對該節(jié)點(diǎn)的擴(kuò)展；否則，則繼續(xù)擴(kuò)展該節(jié)點(diǎn)，若該節(jié)點(diǎn)是最后的葉節(jié)點(diǎn)，則更新最小花費(fèi)的值；最終返回使花費(fèi)最小的虛擬機(jī)分配向量。

4.1.2 算法偽代碼

算法偽代碼如下所示。

1) Input ∶ pmList,vmList, AE,wights

2) Output ∶ allocation vector of VM

3) minCost MAX

4) queue new priority_queue()

5) root new node()

6) queue.push(root)

7) while queue is not empty do

8) parent queue.top()

9) queue.pop()

10) cost estimateCost(root);

11) if cost ＞ = minCost then continue

12) app the next application in AE

13) if app == NULL then

14) minCost cost

15) else

16) foreach vm in vmList do

17) if constraints are satisfied then

18) allocate vm to app

19) child new node(root,app)

20) queue.push(child)

21) return allocation vector of VM that minimizes allocation cost

4.1.3 算法性能分析

在虛擬機(jī)配置模塊中，假定應(yīng)用程序數(shù)為m，預(yù)定義的虛擬機(jī)種類數(shù)為 c，對于每一類虛擬機(jī)都有一個允許被分配的最大數(shù)目，設(shè)d是所有這些最大數(shù)目中的最大值，則對于每個應(yīng)用程序，可以分配的虛擬機(jī)數(shù)量最多為cd；根據(jù)式(2)～式(8)可知，一共有3m+c+1個約束條件；根據(jù)RIVIN等人關(guān)于CSP代數(shù)求解的研究[27]，對于一個有n個變量，每個變量取值數(shù)為m以及M個約束條件的CSP問題，其算法復(fù)雜度為O(nm·2M-n)，故虛擬機(jī)配置模塊的算法復(fù)雜度為O (cdm·22mfc)。

4.2 虛擬機(jī)部署算法

4.2.1 算法描述

虛擬機(jī)部署算法的基本思想是為需要創(chuàng)建的虛擬機(jī)搜索能耗最小的物理主機(jī)分配向量，并輸出分配的物理主機(jī)向量。將虛擬機(jī)部署模塊也表示成CSP問題，采用最佳優(yōu)先和剪枝的策略來對其進(jìn)行求解。在搜索前，首先需要對虛擬機(jī)分配向量進(jìn)行重整，使之成為包含所有待分配虛擬機(jī)的簡單向量。在搜索中，對于任一待擴(kuò)展節(jié)點(diǎn)，如果到達(dá)該節(jié)點(diǎn)的路徑對應(yīng)的能耗大于或等于最小能耗值，則停止對該節(jié)點(diǎn)的擴(kuò)展；否則，則繼續(xù)擴(kuò)展該節(jié)點(diǎn)，若該節(jié)點(diǎn)是最后的葉節(jié)點(diǎn)，則更新最小能耗的值，最終返回使能耗最小的虛擬機(jī)放置向量。

4.2.2 算法偽代碼

算法偽代碼如下所示。

1) Input ∶ pmList, allocation vector N, dyList

2) Output ∶ placement vector of VM

3) VM collapses(N) //collapses N into a single vector VM = (vm1,…, vmp)

4) minPower upperbound(pmList,VM,dyList)

5) queue new priority_queue()

6) root new node()

7) queue.push(root)

8) while queue is not empty do

9) parent queue.top()

10) queue.pop()

11) power = estimatePower(root);

12) if power ＞ = minPower then continue

13) vm the next virtual machine in VM

14) if vm == NULL then

15) minPower power

16) else

17) foreach pm in pmList do

18) if constraints are satisfied then

19) allocate vm to pm 20) child new node(root, pm)21) queue.push(child)

22) return placement vector of VM that minimizes power consumption

4.2.3 算法性能分析

在虛擬機(jī)部署模塊中，假定要被分配的虛擬機(jī)數(shù)為 p，物理機(jī)數(shù)為 n，則對于每一個物理機(jī)，最多只能部署p個要被分配的虛擬機(jī)；根據(jù)式(9)～式(12)可知，一共有4n個約束條件；根據(jù)RIVIN等人關(guān)于CSP代數(shù)求解的研究[27]，對于一個有n個變量，每個變量取值數(shù)為m以及M個約束條件的CSP問題，其算法復(fù)雜度為O(nm·2M-n)，故虛擬機(jī)部署模塊的算法復(fù)雜度為O(pn·8n)。

5 實(shí)驗(yàn)與結(jié)果

5.1 算法模擬實(shí)現(xiàn)

為了驗(yàn)證提出的模型和算法，本文進(jìn)行了模擬實(shí)驗(yàn)。在提出的模型中，虛擬機(jī)配置和部署問題均被定義為約束滿足問題，然后使用基于JAVA的約束編程CHOCO對它們進(jìn)行建模和求解，模擬實(shí)驗(yàn)按如下步驟進(jìn)行。

1) 在應(yīng)用程序監(jiān)測模塊，根據(jù)應(yīng)用程序當(dāng)前負(fù)載和SLA目標(biāo)，獲得各應(yīng)用程序所需的資源量，同時設(shè)置或調(diào)整各應(yīng)用程序的權(quán)重。

2) 根據(jù)應(yīng)用程序監(jiān)測模塊的輸出，虛擬機(jī)配置模塊反復(fù)探求所有可能的虛擬機(jī)分配方案，找出平均花費(fèi)最小的分配方案。

3) 根據(jù)虛擬機(jī)配置模塊的輸出，虛擬機(jī)部署模塊以最小化數(shù)據(jù)中心能耗為目標(biāo)，將需要被分配的虛擬機(jī)部署到物理節(jié)點(diǎn)上。

4) 增加應(yīng)用程序的數(shù)量，預(yù)定義虛擬機(jī)的種類數(shù)量以及數(shù)據(jù)中心物理機(jī)的數(shù)量，重復(fù)步驟 1)～3)的過程。

下面分別列出虛擬機(jī)配置模塊和虛擬機(jī)部署模塊中模型中約束的實(shí)現(xiàn)方法。

(a)虛擬機(jī)配置模塊

約束式(2)：addConstraint(Choco.leq(Choco.sum(dualpos[i]),VMMAX[i]));

約束式(3)～式(5)：addConstraint(Choco.geq(ACPU[i],APCPU[i]));addConstraint(Choco.geq(AMEM[i],APRAM[i]));addConstraint(Choco.geq(ABW[i],APBW[i]));

約束式(6)～式(8)：addConstraint(Choco.leq(Choco.sum(ACPU),CPUMAX));addConstraint(Choco.leq(Choco.sum(AMEM),RAMMAX));addConstraint(Choco.leq(Choco.sum(ABW),BWMAX));

(b) 虛擬機(jī)部署模塊

約束式(9)～式(12)：addConstraint(Choco.leq(Choco.scalar(dualpos[i],VMCPU),PMCPU[i]));addConstraint(Choco.leq(Choco.scalar(dualpos[i],VMRAM),PMRAM[i]));addConstraint(Choco.leq(Choco.scalar(dualpos[i],VMBW),PMBW[i]));addConstraint(Choco.leq(Choco.plus(DYNAMICPower[i],PMSTAPOWER[i]), PMax[i]));

5.2 實(shí)驗(yàn)環(huán)境和實(shí)驗(yàn)數(shù)據(jù)

為了驗(yàn)證提出的能耗優(yōu)化資源分配算法（DY，dynamicpower），在物理主機(jī)不同異構(gòu)性的情況下進(jìn)行了一些模擬實(shí)驗(yàn)，對提出的算法DY與已有的算法 MinPM[4]、FFD[22]、BFD[22]在性能和能耗兩方面進(jìn)行了比較。本文在16組不同資源數(shù)量的環(huán)境下進(jìn)行算法模擬實(shí)驗(yàn)，每組模擬實(shí)驗(yàn)中的虛擬機(jī)數(shù)和物理機(jī)的數(shù)量為：10×實(shí)驗(yàn)組號，即 16組實(shí)驗(yàn)中虛擬機(jī)數(shù)和物理機(jī)的數(shù)量分別為：10，20，30，…，160。而且，分別在物理主機(jī)的能耗異構(gòu)性不同的2種情況下進(jìn)行實(shí)驗(yàn)。其中能耗異構(gòu)性的大小是根據(jù)物理機(jī)上的能耗參數(shù)決定的，如果一組中各物理主機(jī)能耗參數(shù)相差越大，則該組物理機(jī)的異構(gòu)性越大。實(shí)驗(yàn)中物理主機(jī)的能耗參數(shù)數(shù)據(jù)的生成規(guī)則如下。

1) 異構(gòu)性小的物理主機(jī)能耗參數(shù)設(shè)置

空閑能耗：100～300之間。將其分為100～150,150～200, 200～250, 250～300 4 組，依據(jù)物理主機(jī)的資源大小，選擇其中一個組，隨機(jī)生成數(shù)據(jù)，選擇原則一般依照：資源大的，能耗較小。以下選擇的原則相同。

最大能耗：1 000～2 000之間。將其分為1 000～1 250, 1 250～1 500, 1 500～1 750, 1 750～2 000 4 組，同樣依據(jù)物理機(jī)主機(jī)的資源大小，選擇其中一組，隨機(jī)生成數(shù)據(jù)。

2) 異構(gòu)性大的物理主機(jī)能耗參數(shù)設(shè)置

空閑能耗：100～500之間。將其分為100～200,200～300, 300～400, 400～500 4 組，依據(jù)物理主機(jī)的資源大小，選擇其中一組，隨機(jī)生成數(shù)據(jù)。

最大能耗：800～3 500之間。 將其分為800～1 500,1 500～2 200, 2 200～2 900, 2 900～3 600 4組，依據(jù)物理主機(jī)的資源大小，選擇其中一組，隨機(jī)生成數(shù)據(jù)。

另外，實(shí)驗(yàn)中物理主機(jī)和虛擬機(jī)的資源大小參數(shù)的設(shè)置如下。

1) 物理主機(jī)的資源參數(shù)設(shè)置PMCPU：2 ～32 GHz //CPU；PMRAM：2～32 GB//內(nèi)存；PMBW：100～500 M//帶寬。

2) 物理主機(jī)的資源參數(shù)設(shè)置VMCPU：256 MHz～10 GHz//CPU；VMRAM：256 MB～10 GB//內(nèi)存；VMBW：30 ～120 M//帶寬。

5.3 實(shí)驗(yàn)結(jié)果

圖4(a)～圖4(d)分別是物理主機(jī)能耗異構(gòu)小與異構(gòu)大 2種實(shí)驗(yàn)環(huán)境下 DynamicPower(DY)、MinPM、FFD、BFD 4個算法資源分配的能耗情況。其中，縱坐標(biāo)為能耗（單位為Wh），橫坐標(biāo)為實(shí)驗(yàn)編號。從圖4中可以看出，本文提出的能耗優(yōu)化資源分配算法DY和MinPM算法，隨著物理主機(jī)數(shù)和虛擬機(jī)數(shù)的增加，能耗的節(jié)省要優(yōu)于FFD和BFD算法，這主要是因?yàn)镕FD和BFD只是尋求一個合理的資源分配解，而不是尋求能耗最優(yōu)的資源分配解。就DY和MinPM 2種算法而言，DY要優(yōu)于MinPM，因?yàn)镈Y算法考慮虛擬機(jī)動態(tài)能耗求得綜合能耗最小的資源分配方式，而 MinPM 僅僅是求物理主機(jī)數(shù)的最小值，所以DY算法得到的能耗始終是小于MinPM的能耗。將圖4(a)～圖4(d)對比可以看出，當(dāng)物理機(jī)的異構(gòu)性越大時DY算法的能耗減少得更明顯。

為了更好地分析物理主機(jī)的能耗異構(gòu)性大小對資源分配結(jié)果的影響，下面給出2種異構(gòu)環(huán)境下的能耗節(jié)能的比例情況，見圖 5(a)和圖 5(b)。其中，圖 5(a)和圖 5(b)分別表示圖4中各組實(shí)驗(yàn)中4種算法的能耗與最大能耗相比所節(jié)省的能耗百分比。從圖中可以看出，異構(gòu)性大的環(huán)境下DY算法節(jié)省的能耗均在50%左右，而異構(gòu)性小的環(huán)境下DY算法節(jié)省的能耗在40%左右，即異構(gòu)性小環(huán)境下節(jié)能百分比明顯大于異構(gòu)性大環(huán)境下節(jié)能百分比。

(a) 物理主機(jī)異構(gòu)小環(huán)境的能耗1

(b) 物理主機(jī)異構(gòu)小環(huán)境的能耗2

(c) 物理主機(jī)異構(gòu)大環(huán)境的能耗1

圖4 能耗比較

除了能耗優(yōu)化的考慮外，還需要考慮算法的運(yùn)行效率的問題。圖6是圖4中各算法在各組實(shí)驗(yàn)中所對應(yīng)的運(yùn)行時間。

圖5 節(jié)能百分比

圖6 算法運(yùn)行時間比較

圖6 (a)和圖6(b)分別表示圖4中各組實(shí)驗(yàn)的運(yùn)行時間，縱坐標(biāo)為運(yùn)行時間，單位為毫秒(ms)。從上圖中均可以看出，隨著物理主機(jī)和虛擬機(jī)數(shù)的增加，DY和MinPM算法在運(yùn)行時間上有比較明顯的增加，而FFD和BFD 2種算法相比之下在運(yùn)行效率上則具有很明顯的優(yōu)勢，尤其是在物理機(jī)和虛擬機(jī)數(shù)量增加的情況下，這種優(yōu)勢越加明顯。DY的運(yùn)行效率則略優(yōu)于 MinPM 算法，在物理主機(jī)異構(gòu)性較大的情況，則DY的運(yùn)行效率的優(yōu)勢更大，這主要是因?yàn)镈Y算法約束條件相比MinPM算法更多，搜索空間更小，所以求解更快。

6 結(jié)束語

本文主要研究在物理服務(wù)器異構(gòu)情況下的能耗優(yōu)化的資源調(diào)度問題。由于物理主機(jī)資源和能耗的異構(gòu)，不同種類的虛擬機(jī)分配到同一物理主機(jī)上產(chǎn)生的動態(tài)能耗也不同。此時，能耗優(yōu)化的問題并不是最小物理主機(jī)數(shù)。針對該問題，提出了一個基于CSP的能耗最優(yōu)的資源調(diào)度模型，該模型支持異構(gòu)應(yīng)用程序和工作負(fù)載，并且同時支持增加資源到單節(jié)點(diǎn)的垂直伸縮方式和增加節(jié)點(diǎn)數(shù)的水平伸縮方式。在該模型中，將虛擬機(jī)的資源配置從虛擬機(jī)的動態(tài)部署中分離出來。虛擬機(jī)的資源配置模塊旨在根據(jù)用戶 SLA要求確定代價(jià)最小化的資源配置方案，虛擬機(jī)的動態(tài)部署旨在最優(yōu)化數(shù)據(jù)中心的能源消耗。本文將這2個問題建模為約束滿足問題，采用約束規(guī)劃的方法求解該優(yōu)化問題。模擬實(shí)驗(yàn)的結(jié)果驗(yàn)證了本文提出的能耗最優(yōu)模型與算法的有效性。本文提出的模型和算法可以應(yīng)用到云數(shù)據(jù)中心，不僅可以減少云數(shù)據(jù)中心的能耗和經(jīng)營成外，而且這項(xiàng)工作還具有重要的社會意義，因?yàn)樗梢詼p少現(xiàn)代IT基礎(chǔ)設(shè)施CO2的釋放量和能源的消耗量。

[1] BUYYA R, YEO C S, VENUGOPAL S. Market oriented cloud computing∶ vision, hype, and reality for delivering IT services as computing utilities[A]. HPCC’08[C]. Dalian, China, 2008. 5-13.

[2] 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)∶47-111.

[3] GARG S K, YEO C S, ANANDSIVAM A, et al. Environmentconscious scheduling of HPC applications on distributed cloud-oriented data centers[J]. Journal of Parallel and Distributed Computing, 2011,71(6)∶ 732-749.

[4] BICHLER M, SETZER T, SPEITKAMP B. Capacity planning for virtualized servers[A]. WITS’06[C]. Milwaukee, Wisconsin, USA, 2006.1-6

[5] KHANNA G, BEATY K, KAR G, et al. Application performance management in virtualized server environments[A]. NOMS 2006[C].Vancouver, BC, 2006. 373-381.

[6] VERMA A, AHUJA P, NEOGI A. pMapper∶ power and migration cost aware application placement in virtualized systems[A]. Middleware'08 [C]. New York, NY, USA∶ Springer-Verlag, 2008. 243-264.

[7] HERMENIER F, LORCA X, MENAUD J M, et al. Entropy∶ a consolidation manager for cluster[A]. VEE’09[C]. New York, NY,USA∶ ACM, 2009. 41-50.

[8] RIETZ J, MACEDO R, ALVES C, et al. Efficient lower bounding procedures with application in the allocation of virtual machines to data centers[J]. WSEAS Transactions on Information Science And Applications, 2011, 4(8)∶157-170.

[9] BATU R R T, WHITE P. Fast approximate PCPs for multidimensional bin-packing problem[J]. Lecture Notes in Computer Science, 1999,1671∶245-256.

[10] TIAGO C F, MARCO A S N, RODRIGO N C, et al. Server consolidation with migration control for virtualized data centers[J].Future Generation Comp Syst, 2011, 27(8)∶ 1027-1034.

[11] VAN H N, TRAN F D, MENAUD J M. SLA-aware virtual resource management for cloud infrastructures[A]. CIT’09[C]. Washington DC,USA, 2009.357-362.

[12] VON LAZEWSKI G, WANG L, YOUNGE A J, et al. Power-aware scheduling of virtual machines in DVFS-enabled clusters[A].CLUSTER’09[C]. New Orleans, LA, USA, 2009.1-10.

[13] LIU L, WANG H, LIU X, et al. Greencloud∶ a new architecture for green data center[A]. ICAC-INDST '09[C]. New York, NY, USA,ACM, 2009.29-38.

[14] HARALICK R, ELLIOTT G. Increasing tree search efficiency for constraint satisfaction problems[J]. Artificial Intelligence, 1980, 14(3)∶263-313.

[15] JUSSIEN N, ROCHART G , LORCA X. The CHOCO constraint programming solver[A]. OSSICP’08[C]. Paris, France, 2008.

[16] SRIKANTAIAH S, KANSAL A, ZHAO F. Energy aware consolidation for cloud computing[A]. HotPower'08[C]. Berkeley, CA,USA, 2009. 1-15.

[17] BERL A, GELENBE E, GIROLAMO M, et al. Energy-efficient cloud computing[J]. The Computer Journal, 2010, 53(7)∶ 1045-1051.

[18] BELOGLAZOV A, BUYYA R. Energy efficient resource management in virtualized cloud data centers[A]. CCGRID ‘10[C]. Washington DC,USA, 2010. 826-831.

[19] RODERO I, JARAMILLO J, QUIROZ A. Energy-efficient application-aware online provisioning for virtualized clouds and data centers[A]. GREENCOMP’10[C]. Washington DC, USA, 2010.[20] 3A1B-4D5E.LSALAM H S, MALY K, KAMINSKY D. Analysis of energy efficiency in clouds[A]. Computationworld '09[C]. Washington DC,USA, 2009.416-422.

[21] YOUNGE A J, LASZEWSKI G , WANG L. Efficient resource management for Cloud computing environments[A]. GREENCOMP’10[C].Washington DC, USA, 2010. 357-364.

[22] CHANG F, REN J, VISWANATHAN R. Optimal resource allocation in clouds[A]. CLOUD’10[C]. Washington DC, USA, 2010. 418-425.

[23] LEE Y C, ZOMAYA A Y. Energy efficient utilization of resources in cloud computing systems[J]. The Journal of Supercomputing, 2012,60(2)∶ 268-280.

[24] KARMARKAR N, KARP R M. An efficient approximation scheme for the one-dimensional bin-packing problem[A]. FOCS’82[C].Washington DC, USA, 1982. 312-320.

[25] BELOGLAZOV A, ABAWAJY J H, BUYYA R. Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing[J]. Future Generation Comp Syst, 2012, 28(5)∶755-768.

[26] KUMAR V. Algorithms for constraint satisfaction problems∶ a survey[J]. AI Magazine, 1992, 13(1)∶ 32-44.

[27] RIVIN I, ZABIH R. An algebraic approach to constraint satisfaction problem[A]. IJCAI'89[C]. San Francisco, CA, USA, 1989. 284-289.