林偉偉，朱朝悅

（華南理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，廣東 廣州510640）

1 引言

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

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

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

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

2.1 問(wèn)題描述

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

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

2.2 基于服務(wù)器集群劃分的可擴(kuò)展分布式調(diào)度方法設(shè)計(jì)

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

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

Figure 2 Server cluster partitioning圖2 服務(wù)器集群劃分

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

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

3.1 集群劃分算法

3.1.1 算法描述

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

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

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

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

（3）對(duì)每個(gè)集群上的物理機(jī)資源進(jìn)行統(tǒng)計(jì)，將各個(gè)集群累加起來(lái)的資源進(jìn)行排序，每個(gè)集群資源越多，排序越前。

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

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

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

3.1.2 算法偽代碼

算法1 集群劃分算法

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

3.2.1 算法描述

將所有待調(diào)度的服務(wù)器按照上一節(jié)提到的集群劃分算法劃分為若干個(gè)服務(wù)器集群，然后在每個(gè)服務(wù)器集群中實(shí)現(xiàn)最優(yōu)能耗資源調(diào)度算法。最優(yōu)能耗資源調(diào)度算法的基本思想是以能耗最優(yōu)為目標(biāo)為分配的虛擬機(jī)搜索物理主機(jī)分配向量［18］。將最優(yōu)能耗資源調(diào)度算法表示成CSP 問(wèn)題，采用最佳優(yōu)先和剪枝的策略來(lái)對(duì)其進(jìn)行求解。首先需要將虛擬機(jī)分配向量重新整理，使之成為包含所有待分配虛擬機(jī)的簡(jiǎn)單向量。在搜索中，對(duì)于任一待擴(kuò)展節(jié)點(diǎn)，如果到達(dá)該節(jié)點(diǎn)的路徑對(duì)應(yīng)的能耗大于或等于最小能耗值，則停止對(duì)該節(jié)點(diǎn)的擴(kuò)展；否則，繼續(xù)擴(kuò)展該節(jié)點(diǎn)，若該節(jié)點(diǎn)是最后的葉節(jié)點(diǎn)，則更新最小能耗的值，最終返回使能耗最小的虛擬機(jī)放置向量。該過(guò)程使用開(kāi)源的Choco工具模擬實(shí)現(xiàn)，求解在每個(gè)集群中后最優(yōu)能耗為目標(biāo)的最優(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è)要被分配的虛擬機(jī)數(shù)為p，物理機(jī)數(shù)為n，因此，最多只能部署p個(gè)要被分配的虛擬機(jī)在一個(gè)物理機(jī)。根據(jù)式（1）～式（4）可知，一共有3n個(gè)約束條件，根據(jù)Rivin I等人［19］關(guān)于CSP 代數(shù)求解的研究，對(duì)于一個(gè)有n個(gè)變量、每個(gè)變量取值數(shù)為m以及M個(gè)約束條件的CSP問(wèn)題，其算法復(fù)雜度為O（nm·2M－n），故在最優(yōu)能耗資源調(diào)度中的算法復(fù)雜度為O（pn·4n）。

4 實(shí)驗(yàn)與結(jié)果分析

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

4.1 算法實(shí)現(xiàn)

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

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

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

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

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

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

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

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

③目標(biāo)函數(shù)。

s.minimize（false）；

s.setObject（power）；

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

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

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

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

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

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

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

4.3.1 實(shí)驗(yàn)1

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

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

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

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

Figure 5 Energy consumption comparison圖5 能耗比較

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

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

4.3.2 實(shí)驗(yàn)2

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

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

Figure 7 Comparison of running time under different Thresholds圖7 不同Threshold 下運(yùn)行時(shí)間對(duì)比

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

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

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

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

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

［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.

附中文參考文獻(xiàn)：

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

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

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

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

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

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