方錦明

（義烏工商職業(yè)技術(shù)學(xué)院 機(jī)電信息分院，浙江 義烏322000）

0 引 言

Luis M.Vaquero學(xué)者在研究了20種云計(jì)算的定義后，給出了一個(gè)云計(jì)算的定義：云計(jì)算是一種大規(guī)模的易用的可訪問的虛擬資源 （如硬件、平臺和／或服務(wù)）池［1－4］。由此可知，虛擬性［5］在云計(jì)算中扮演了一個(gè)核心角色。然而，在云計(jì)算環(huán)境中，虛擬資源的調(diào)度問題也凸顯出來。虛擬資源的調(diào)度是指，按照一定的規(guī)則合理地將用戶申請的虛擬資源映射到相應(yīng)的物理資源。一個(gè)好的調(diào)度器應(yīng)該能夠均勻地將虛擬資源映射到物理資源上，然而，由于請求的虛擬資源的差異性和物理資源的異構(gòu)性，該問題是一個(gè)難解問題。

在現(xiàn)在的已經(jīng)實(shí)現(xiàn)的云計(jì)算調(diào)度系統(tǒng)上，一般都是采用簡單的策略實(shí)現(xiàn)。如EC2［6］使用按購買分配，VMware［7］按照CPU和內(nèi)存的使用動(dòng)態(tài)分配，NimBus［8］和 Eucalyptus［9］采用靜態(tài)貪婪策略和隨機(jī)選擇，oVirt［10］采用手工分配模式，OpenNebula［11］采用需要／排序動(dòng)態(tài)分配的策略。簡單的調(diào)度策略來進(jìn)行調(diào)度已經(jīng)很難滿足日益增長的云計(jì)算的規(guī)模，因此不少學(xué)者開始研究這個(gè)問題。如Ravi Iyer［12］研究了虛擬資源間對物理資源的競爭所導(dǎo)致的性能下降，并提出了一種有效的模型來預(yù)測這種下降并在此基礎(chǔ)上提出了一種虛擬機(jī)管理模型；墨爾本大學(xué)的學(xué)者［13］提出了一個(gè)InterGrid系統(tǒng)來管理不同云系統(tǒng)間虛擬資源的遷移問題；國內(nèi)學(xué)者田冠華等［14］提出了一種基于失效規(guī)則的資源動(dòng)態(tài)提供策略，能有效提高動(dòng)態(tài)提供節(jié)點(diǎn)資源的可靠性。

本文通過對虛擬資源調(diào)度過程的分析，將虛擬資源的調(diào)度過程抽象為具有CPU，內(nèi)存，和帶寬等屬性的節(jié)點(diǎn)的匹配過程，分析了該問題的難解性，將其轉(zhuǎn)換為具有負(fù)載均衡的多目標(biāo)優(yōu)化問題，采用多目標(biāo)優(yōu)化算法來對虛擬資源進(jìn)行調(diào)度。與具體的虛擬資源調(diào)度的實(shí)現(xiàn)相比，該調(diào)度模型更能反映云計(jì)算中虛擬資源調(diào)度的復(fù)雜性，同時(shí)不同于簡單的調(diào)度策略，采用多目標(biāo)優(yōu)化算法進(jìn)行調(diào)度，能使得云計(jì)算中虛擬資源的調(diào)度更加合理。通過實(shí)驗(yàn)驗(yàn)證了本文提出的模型的合理性并驗(yàn)證了使用多目標(biāo)優(yōu)化算法求解該問題的合理性。

1 虛擬資源調(diào)度的建模

不同于網(wǎng)格計(jì)算等其他分布式計(jì)算平臺，云計(jì)算中一個(gè)核心就是虛擬化。圖1是云計(jì)算與其他分布式計(jì)算平臺的差異。簡單地講，虛擬資源就是通過虛擬化技術(shù)將物理資源抽象為同一的虛擬資源。使用虛擬資源的優(yōu)點(diǎn)有：

圖1 云計(jì)算與其他分布式平臺的差異

（1）可用性：在共享的分布式環(huán)境中，每個(gè)用戶的需求是不一樣的，在沒有對資源虛擬的情況下，當(dāng)一個(gè)用戶占用了一個(gè)物理資源時(shí)，其他的用戶只有等待，而該用戶使用結(jié)束時(shí)，其他用戶又不得不重新配置自己的環(huán)境。當(dāng)資源被虛擬化后，不僅不同的用戶可以同時(shí)使用相同的資源，而且每個(gè)用戶只需配置自己的環(huán)境一次。

（2）安全性：在虛擬環(huán)境中，每個(gè)用戶的程序相互隔離，當(dāng)一個(gè)用戶程序出現(xiàn)崩潰以后，不會(huì)影響到其他用戶程序的運(yùn)行；同時(shí)，每個(gè)用戶在虛擬環(huán)境中，其權(quán)限受到限制，對用戶的數(shù)據(jù)更加安全。在虛擬環(huán)境中，用戶可以隨時(shí)暫停，保存，恢復(fù)程序的運(yùn)行。當(dāng)由于配置錯(cuò)誤等其他原因?qū)е颅h(huán)境崩潰后，可以通過回滾的方式將環(huán)境恢復(fù)到正確的狀態(tài)。

（3）遷移性：當(dāng)由于設(shè)備更新?lián)Q代或者其他原因需要將程序遷移到新的環(huán)境中時(shí)，虛擬資源的配置可以很容易遷移到其他平臺上。

虛擬資源的優(yōu)點(diǎn)導(dǎo)致了虛擬化技術(shù)的蓬勃發(fā)展，然而，將虛擬資源均衡地調(diào)度到物理資源上成為一個(gè)難點(diǎn)。因?yàn)槊總€(gè)用戶對虛擬資源的需求不同，而且物理資源也具有差異性。本文首先對虛擬資源的調(diào)度進(jìn)行建模并證明其難解性。

虛擬資源的調(diào)度是將虛擬資源合理地映射到物理資源上。在云計(jì)算的實(shí)際環(huán)境中，一個(gè)虛擬資源可以抽象為一個(gè)具有一定屬性的節(jié)點(diǎn)。如一個(gè)具有cpu屬性，內(nèi)存屬性和帶寬屬性的虛擬資源可以抽象為v（c，m，b），其中，c為cpu屬性，m為內(nèi)存屬性，b為帶寬屬性。同理一個(gè)物理資源也可以抽象為p（c，m，b）。如表1所示。

表1 抽象后的虛擬資源及物理資源

在此基礎(chǔ)上，本文提出如下定義：

定義1 虛擬資源的調(diào)度是將將虛擬資源映射到物理資源上的一個(gè)方案，對應(yīng)于虛擬資源vi（cvi，mvi，bvi），vi＝1，2，… ，m，和物理資源pi（cpi，mpi，bpi），pi＝ 1，2，… ，n，一個(gè)調(diào)度可以由m個(gè)物理資源組成的排列L（pi1，pi2，…，pim）來表示，此時(shí)，虛擬資源cv1被調(diào)度到物理資源pi1，虛擬資源cv2被調(diào)度到物理資源pi2等。

定理1 采用窮舉算法進(jìn)行求解，虛擬資源的調(diào)度是難解問題。

證明：采用窮舉算法對云計(jì)算環(huán)境中的虛擬問題進(jìn)行求解，則，對于v1有n個(gè)選擇，v2有n個(gè)選擇，…，vm有n個(gè)選擇，因此對于排列L有nm種，因此該算法的時(shí)間復(fù)雜度是O（nm），由NP問題的定義知，該問題是難解問題。

2 基于NSGA II的虛擬資源調(diào)度算法

在前面討論的基礎(chǔ)上，本文針對虛擬資源的調(diào)度問題，提出采用多目標(biāo)優(yōu)化算法進(jìn)行求解，下面分別介紹多目標(biāo)優(yōu)化算法的主要組成部分：編碼、優(yōu)化函數(shù)和搜索算法。

2.1 編 碼

由定義1知道，虛擬資源的調(diào)度是尋找一個(gè)調(diào)度序列，設(shè)虛擬資源的編號為vi＝1，2，…，m，物理資源的編號為pi＝1，2，…，n。本文采用序列編號作為編碼方式，因此對需要調(diào)度的虛擬資源進(jìn)行排序設(shè)為 （v1，v2，…，vm），然后按照排序?qū)μ摂M資源進(jìn)行調(diào)度，設(shè)調(diào)度序列為 （va1，va2，…，vam），其中，vai∈｛pi｝，則調(diào)度方法為，對應(yīng)于vi，i＝1，2，…，m，其映射的物理資源為vai。算法中的編碼方式為（va1，va2，…，vam）。

2.2 優(yōu)化函數(shù)

評價(jià)一個(gè)調(diào)度算法的好壞，主要是看該算法給出的調(diào)度方法是否符合負(fù)載均衡的要求，因此本文借鑒數(shù)學(xué)上方差的思想，對資源分布的均勻性進(jìn)行量化，提出了針對不同屬性的均勻分布策略。

對于一個(gè)給定的編碼 （va1，va2，…，vam）有：（1）cpu屬性的均衡度

因此，cpu的均衡度為

同理，可得：

（2）內(nèi)存屬性的均衡度

（3）帶寬屬性的均勻性

2.3 搜索算法

本文使用NSGA II［15］對問題求解。NSGA II是多目標(biāo)優(yōu)化算法中的經(jīng)典算法，其思想與遺傳算法類似，不同的是在個(gè)體選擇過程中首先按照Pareto支配的概念進(jìn)行排序同時(shí)計(jì)算個(gè)體的擁擠度，然后按照非支配優(yōu)先，擁擠度較小的原則選擇個(gè)體。Pareto支配是指：設(shè)求解目標(biāo)函數(shù)的最小值，則對于兩個(gè)個(gè)體，若所有的目標(biāo)有：A （B）＜＝B（A）且A不等于B，則稱A （B）支配B （A），反之，則稱A、B互不支配。NSGA II能一次求解多個(gè)目標(biāo)，但是，非支配排序是一個(gè)非常耗時(shí)的過程，為改善算法的求解性能，受文獻(xiàn)［16］的啟發(fā)，本文提出了如下基于樹的非支配求解算法來加快算法的求解速度。

首先對種群按照第一個(gè)目標(biāo)進(jìn)行排序，然后對每一個(gè)個(gè)體賦一個(gè)唯一的編號，設(shè)1，2，…，n。因此編號小的個(gè)體一定不會(huì)被編號大的個(gè)體所支配。然后采用二叉樹構(gòu)造法構(gòu)建一棵非支配樹。最后采用算法1獲取非支配解集。

算法1：獲取非支配解集

遍歷樹Tree獲得非支配解集F

逐個(gè)將Tree及其左子樹壓入第一層非支配解集F1；

將F1壓入F；

循環(huán)如果F中的個(gè)體數(shù)＜小于樹節(jié)點(diǎn)個(gè)體的一半

對于Fi－1中的每一個(gè)個(gè)體p

對于pi＝p.right；pi！＝null；pi＝pi.left

若pi不被Fi中的個(gè)體所支配

將pi添加到Fi；

否則

將pi添加到集合Left；

對于每個(gè)pi屬于Left

若pi不被Fi中的個(gè)體所支配

將pi添加到Fi；

若pi支配Fi中的某個(gè)個(gè)體qi

將qi添加到Left；

程序結(jié)束

算法的整體流程圖如圖2所示。首先隨機(jī)生成包含n個(gè)基因的種群P1，同時(shí)選擇交叉，變異生成下一代種群Q1；然后，將一棵空樹和節(jié)點(diǎn)集PiUQi作為參數(shù)輸入到算法1，返回一棵樹，對該樹按算法2進(jìn)行遍歷得到排序后的集合，同時(shí)對最后一個(gè)集合進(jìn)行擁擠度的計(jì)算；最后按照非支配優(yōu)先，擁擠度較小的原則選擇個(gè)體，即：若A支配B，則選擇A，若A，B互不支配，則選擇擁擠度較小的那個(gè)個(gè)體。

圖2中，選擇交叉采用錦標(biāo)賽選擇，兩點(diǎn)交叉，即，隨機(jī)選擇兩個(gè)個(gè)體，并選擇其中較優(yōu)的個(gè)體作為父個(gè)體p1，同樣的方法選擇父個(gè)體p2，然后隨機(jī)生成兩個(gè)交叉點(diǎn)c1，c2，將p1從c1到c2的基因片段與p2從c1到c2的基因片段交換，生成子個(gè)體u1，u2。變異是對每個(gè)個(gè)體每一位按照變異因子Pc進(jìn)行變異，即：若隨機(jī)數(shù)小于變異因子，則隨機(jī)生成一個(gè)基因位替換原來的基因。算法中采用基于樹的非支配排序算法進(jìn)行排序，然后參照文獻(xiàn) ［15］計(jì)算擁擠度，即：對于每一個(gè)目標(biāo)，非支配個(gè)體按照該目標(biāo)排序，對于第一個(gè)和最后一個(gè)個(gè)體擁擠度為最小，其他個(gè)體則是相鄰兩個(gè)個(gè)體的距離倒數(shù)。

圖2 算法的整體流程

3 實(shí)驗(yàn)及結(jié)果分析

實(shí)驗(yàn)的主要目的有：①驗(yàn)證NSGA II算法的可行性；②在不同資源數(shù)和不同資源比例下對比NSGA II與隨機(jī)調(diào)度算法，靜態(tài)調(diào)度算法及排序匹配算法。

3.1 實(shí)驗(yàn)設(shè)置及對比算法的描述

本文實(shí)驗(yàn)Java語言編程實(shí)現(xiàn)。算法的具體參數(shù)設(shè)置如下：種群個(gè)數(shù)：48，最大迭代次數(shù)：1000，交叉因子：0.9，變異因子：1／l，其中l(wèi)為基因長度。本文對比了3種簡單的調(diào)度算法：隨機(jī)調(diào)度算法，靜態(tài)調(diào)度算法和排序匹配算法。對于虛擬資源集V，物理資源集P，3種算法簡述如下：

（1）隨機(jī)調(diào)度算法：隨機(jī)給出一個(gè)調(diào)度方案L（a1，…，am）；

（2）靜態(tài)調(diào)度算法：調(diào)度方案為L （a1，… ，am），其中，ai＝i%n；

（3）排序匹配算法：該算法的主要思想是：對于一個(gè)要分配的資源，尋找與其最接近的物理資源作為分配策略。即：對于某個(gè)虛擬資源vi（cvi，mvi，bvi）和物理資源pi（cpi，mpi，bpi），pi＝1，2，… ，n，其計(jì)算公式如下：ai＝min｛pi｝，pi＝1，2，… ，n。此時(shí)有：min｛｜c(diǎn)pi－cvi｜＋｜mpi－mvi｜＋｜bpi－bvi｜｝。

3.2 對本文示例的求解

對第二節(jié)的實(shí)例進(jìn)行求解，以驗(yàn)證本文模型的正確性和NSGA II求解該問題的可行性以及對比其他算法的優(yōu)勢。限于篇幅，表2給出了使用NSGA II算法對第二節(jié)實(shí)例求解的前8個(gè)非支配解的求解情況。從表中可以看出NSGA II可以通過一次求解獲取多個(gè)不同的解。因此，本文采用3種策略來選擇最終解：cpu策略、內(nèi)存策略、帶寬策略、均衡策略，實(shí)際使用中可以根據(jù)不同的需要進(jìn)行選擇。cpu策略是指：在所有解中選擇cpu最均衡的解。內(nèi)存和帶寬策略亦類似。均衡策略是指：對于一組非支配解，選擇目標(biāo)函數(shù)之和最小的解。

表2 使用NSGA II求解的非支配解集分布情況

表3給出不同策略下的求解結(jié)果，注意，隨機(jī)算法、靜態(tài)算法和排序算法不能按照相應(yīng)的策略給出不同的解。

表3 NSGA II算法對本文實(shí)例求解結(jié)果及與其他算法的對比

從表3中可以看出幾種屬性間相互影響，對于一個(gè)給定的問題，幾乎不存在唯一最優(yōu)解。同時(shí)，NSGA II給出了多個(gè)解，用戶可以按照自己的要求選擇不同的解，而簡單的求解算法則無法達(dá)到這樣的要求。簡單地可以看到，NSGAII給出的解幾乎全面優(yōu)于其他算法。

3.3 不同資源比下的比較

為了更詳細(xì)地比較NSGA II與其他算法的求解結(jié)果，了解在不同資源映射情況下NSGA II的解的情況，本文對多個(gè)資源分配進(jìn)行求解。在云計(jì)算環(huán)境中，虛擬資源個(gè)數(shù)與物理資源個(gè)數(shù)比代表了資源的緊張程度。如：虛擬資源個(gè)數(shù)與物理資源個(gè)數(shù)的比例0.2，那么，此時(shí)有大量的物理資源被閑置，此種情況下，調(diào)度的均衡性變的不是非常重要；反正，若比例為1.2，則表明物理資源非常緊張，調(diào)度的好壞，直接影響著系統(tǒng)的均衡性和吞吐量。為全面了解算法的求解情況，本文對比例為 ［0.2－1.2］的虛擬資源調(diào)度進(jìn)行求解。

實(shí)驗(yàn)中，隨機(jī)生成個(gè)數(shù)為 ［100－1000］的物理資源，然后按照不同的比值生成虛擬資源。物理資源和虛擬資源的各個(gè)屬性隨機(jī)生成。CPU取值為 ［100～2000］，內(nèi)存的取值為 ［10～4000］，帶寬的取值為 ［1～100］。這樣的資源取值可以充分代表異構(gòu)的物理資源的復(fù)雜性及虛擬任務(wù)的多樣性。

圖3－圖5顯示了在均衡策略下算法運(yùn)行100次后的平均結(jié)果。3張圖分別表示cpu，內(nèi)存和帶寬的均衡性。從圖中可以看出，NSGA II算法要全面優(yōu)于其他算法。而隨機(jī)算法和固定算法的均衡度接近，排序算法的均衡度最差。這是因?yàn)?，排序算法是按照匹配度進(jìn)行的，這樣會(huì)導(dǎo)致某個(gè)匹配的機(jī)器負(fù)載較重，資源分配失去平衡性。

為從直觀的數(shù)值上比較各個(gè)算法的均衡度，表4給出了各個(gè)算法在不同資源比下的各個(gè)均衡度的平均值及NSGA II相比其他算法的均衡度提高的倍數(shù)。從表中可以看出，在均衡策略下，NSGA II各個(gè)數(shù)值都要優(yōu)于其他算法的結(jié)果。

表4 各個(gè)算法的平均值及NSGA II相對于其他算法提高的倍數(shù)

4 結(jié)束語

本文對云計(jì)算環(huán)境下的虛擬資源調(diào)度問題進(jìn)行了建模，提出將虛擬資源和物理資源抽象為具有一定屬性的節(jié)點(diǎn)的匹配過程。采用NSGA II算法對該問題進(jìn)行求解，同時(shí)改進(jìn)了NSGA II的非支配排序過程。最后通過實(shí)驗(yàn)對比了NSGA II算法和其他3種基于簡單策略的調(diào)度算法。實(shí)驗(yàn)表明，NSGA II可以用來求解云計(jì)算環(huán)境下的虛擬資源調(diào)度問題，一次求解給出多個(gè)候選解，為用戶采用不同的調(diào)度策略進(jìn)行調(diào)度提供了可能性。同時(shí)，實(shí)驗(yàn)中給出了在均衡策略下與其他3種簡單的調(diào)度算法的對比，結(jié)果表明，本文提出的基于NSGA II的調(diào)度算法能進(jìn)行更好地調(diào)度。

［1］Armbrust Michael，F(xiàn)ox Armando，Griffith Rean，et al.A view of cloud computing ［J］.Communications of the ACM，2010，53 （4）：50－58.

［2］WANG Jiajun，LU Zhihui，WU Jie，et al.Cloud computing technology development analysis and applications discussion［J］.Computer Engineering and Design，2010，31 （20）：4405－4409（in Chinese）.［王佳雋，呂智慧，吳杰，等.云計(jì)算計(jì)算發(fā)展分析及其應(yīng)用探討 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2010，31 （20）：4405－4409.］

［3］Amazon.Amazon EC2 ［EB／OL］.http：／／www.amazon.com／ec2，2011.

［4］Luis M Vaquero，Luis Rodero Merino，Juan Caceres，et al.A break in the clouds：Towards a cloud definition ［J］.ACM Sigcomm，2009，39 （1）：50－55.

［5］Mendel Rosenblum，Tal Carfinkel.Virtual machine monitors：Current technology and future trends computer ［J］.Computer，2005，38 （5）：39－47.

［6］Ostermann Simon，Iosup Alexandria，Yigitbasi Nezih，et al.A performance analysis of EC2cloud computing services for scientific computing ［J］.Cloud Computing，2010，34 （4）：115－131.

［7］VMware Inc.VMware VCloud initiative ［EB／OL］.http：／／www.vmware.com／technology／cloud－computing.html，2011.

［8］WANG Lizhe，Laszewski Von Gregor.Scientific cloud computing：Early definition and experience［C］.Dalian：10th IEEE International Conference on High Performance Computing and Communications，2008：825－830.

［9］Nurmi Daniel，Wolski Rich，Grzegorczyk Chris.The eucalyptus open－source cloud－computing system ［C］. Washington：IEEE Computer Society，2009：1－8.

［10］Redhet Inc.oVirt.［EB／OL］.http：／／ovirt.org，2011.

［11］Borja Sotomayor，Rubén S Montero，Ignacio M Llorente，et al.Virtual infrastructure management in private and hybrid clouds［J］.Internet Computing IEEE，2009，13 （5）：14－22.

［12］Ravi Iyer，Ramesh Illikkal，Omesh Tickoo，et al.VM3：Measuring modeling and managing VM shared resources ［J］.Computer Networks，2009，53 （17）：2873－2887.

［13］Alexandre Di Costanzo，Marcos Dias De Assuncao，Rajkumar Buyya.Harnessing cloud technologies for a virtualized ［J］.Distributed Computing Infrastructure，2009，13 （5）：24－33.

［14］TIAN Guanhua，MENG Dan，ZHAN Jianfeng.Reliable resource provision policy for cloud computing ［J］.Chinese Journal of Computer，2010，33 （10）：1859－1872 （in Chinese）［田冠華，孟丹，詹劍鋒.云計(jì)算環(huán)境下基于失效規(guī)則的資源動(dòng)態(tài)提供策略 ［J］.計(jì)算機(jī)學(xué)報(bào)，2010，33 （10）：1859－1872.］

［15］LI Hui，ZHANG Qingfu.Multiobjective optimization problems with complicated pareto sets MOEA／D and NSGA－II［J］.IEEE Transactions on Evolutionary Computation，2009，13（2）：284－302.

［16］SHI Chuan，YAN Zhenyu，SHI Zhongzhi，et al.A fast multi－objective evolutionary algorithm based on a tree structure［J］.Applied Soft Computing，2010，10 （2）：468－480.