摘  要：云計(jì)算通過虛擬化技術(shù)將基礎(chǔ)設(shè)施硬件資源虛擬化,，以動(dòng)態(tài)可縮放的方式提供給用戶。云計(jì)算基礎(chǔ)設(shè)施規(guī)模不斷增加導(dǎo)致資源調(diào)度系統(tǒng)負(fù)載不均衡,，從而造成資源浪費(fèi)等問題,。提出多目標(biāo)優(yōu)化資源調(diào)度策略和相應(yīng)的算法，試圖同時(shí)滿足多個(gè)資源調(diào)度優(yōu)化目標(biāo),，如減少資源浪費(fèi),，降低服務(wù)等級(jí)約定（SLA）違背率、保持系統(tǒng)負(fù)載均衡等,。通過仿真實(shí)驗(yàn),，驗(yàn)證了多目標(biāo)優(yōu)化資源調(diào)度的策略能夠在多個(gè)相互沖突的目標(biāo)之間實(shí)現(xiàn)最優(yōu)權(quán)衡。

　　關(guān)鍵詞： 云計(jì)算,；多目標(biāo)優(yōu)化,；虛擬機(jī)；資源調(diào)度

0 引言

　　云計(jì)算是一種新的計(jì)算服務(wù)模式,，可以在不同的抽象級(jí)別實(shí)現(xiàn),，這取決于云提供商提供的特定服務(wù)，如存儲(chǔ),、計(jì)算等,。本文主要研究基礎(chǔ)設(shè)施作為服務(wù)（IaaS）[1]的云的資源調(diào)度，IaaS云主要通過虛擬化技術(shù)[2]將基礎(chǔ)設(shè)施提供給用戶，包括以虛擬機(jī)方式的計(jì)算服務(wù),、虛擬磁盤方式的存儲(chǔ)服務(wù),、虛擬機(jī)交換機(jī)的網(wǎng)絡(luò)服務(wù)。隨著計(jì)算機(jī)與網(wǎng)絡(luò)技術(shù)的高速發(fā)展,，互聯(lián)網(wǎng)用戶不斷增多,，計(jì)算機(jī)基礎(chǔ)設(shè)施規(guī)模也不斷擴(kuò)大，導(dǎo)致資源浪費(fèi)不斷增加,，數(shù)據(jù)中心的負(fù)載失衡嚴(yán)重,。云環(huán)境的動(dòng)態(tài)特性使得云提供商向用戶提供的云服務(wù)不能嚴(yán)格滿足服務(wù)等級(jí)約定（SLA）。而大多數(shù)的解決方案只涉及某一方面的目標(biāo)優(yōu)化,，比如通過服務(wù)器的整合降低數(shù)據(jù)中心的能源消耗,，但是降低了用戶需求的滿意度。有的研究工作為了減少SLA違背率,，將虛擬機(jī)分散放在盡可能多的服務(wù)器上,，降低了資源的利用率，這是因?yàn)椴煌膬?yōu)化目標(biāo)之間是相互沖突的,。

　　針對(duì)以上問題,，本文提出了多目標(biāo)優(yōu)化的資源調(diào)度策略，該方法在多個(gè)相互沖突的目標(biāo)之間實(shí)現(xiàn)最優(yōu)權(quán)衡,，如降低服務(wù)等級(jí)協(xié)議違背率,、減少資源浪費(fèi)和負(fù)載均衡等。

1 相關(guān)工作分析

　　在云計(jì)算基礎(chǔ)設(shè)施中,，虛擬機(jī)資源的分配是一個(gè)重要研究課題,。目前已有一系列研究成果，比如參考文獻(xiàn)[3-4]通過服務(wù)器的整合來降低數(shù)據(jù)中心的能源消耗,，但是增加了服務(wù)等級(jí)約定違背率,。參考文獻(xiàn)[5]中提出了一種基于遺傳算法的負(fù)載均衡調(diào)度策略，該算法計(jì)算出在部署請(qǐng)求的虛擬機(jī)資源之后對(duì)系統(tǒng)的影響,，并選擇最小影響的解決方案,，避免進(jìn)行在線遷移，但是在資源分配過程中存在資源浪費(fèi)的問題,。Wood[6]描述了動(dòng)態(tài)監(jiān)測系統(tǒng)中CPU,、內(nèi)存資源、網(wǎng)絡(luò)帶寬的利用率,，提出了白盒測試與黑盒測試的方法,，并重點(diǎn)研究了通過虛擬機(jī)遷移進(jìn)行重映射解決負(fù)載失衡的問題，但是增加了SLA違背率,。參考文獻(xiàn)[7]中提出通過在虛擬機(jī)之間轉(zhuǎn)移工作負(fù)載,，優(yōu)化各個(gè)虛擬機(jī)的資源需求,，在任務(wù)執(zhí)行之后減少虛擬機(jī)的遷移，避免系統(tǒng)性能的降低,，但是同樣存在資源浪費(fèi)的問題,。

　　現(xiàn)有研究中很少將資源浪費(fèi)、保證服務(wù)等級(jí)約定和負(fù)載均衡進(jìn)行綜合考慮,，實(shí)現(xiàn)虛擬機(jī)資源調(diào)度的多目標(biāo)優(yōu)化,。大部分的研究只是將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為若干個(gè)單目標(biāo)優(yōu)化問題分階段解決，很少是同時(shí)對(duì)多個(gè)目標(biāo)進(jìn)行優(yōu)化的,。

2 資源優(yōu)化調(diào)度建模

　　2.1 數(shù)學(xué)模型

　　IaaS中虛擬機(jī)資源分配問題可以描述成在動(dòng)態(tài)云環(huán)境中多維裝箱問題,。本文構(gòu)建了數(shù)學(xué)模型，使用元組q=<t,，VMSET,，ts>表示各個(gè)虛擬機(jī)資源調(diào)度請(qǐng)求,，其中t表示虛擬機(jī)資源請(qǐng)求到達(dá)的時(shí)刻,，VMSET表示要申請(qǐng)的虛擬機(jī)集，ts表示虛擬機(jī)的生命周期,。

　　一個(gè)簡單的例子如圖1所示,。涉及到7個(gè)虛擬機(jī)資源請(qǐng)求，如虛擬機(jī)請(qǐng)求{2,，{1,，2}，6}表示請(qǐng)求在時(shí)刻2到達(dá),，申請(qǐng)了序號(hào)為1與2兩個(gè)虛擬機(jī),，虛擬機(jī)的生命周期為6個(gè)時(shí)間單元。在時(shí)刻15時(shí)虛擬機(jī)6,、7還在運(yùn)行,，1~5號(hào)虛擬機(jī)被刪除了。

　　本文考慮一個(gè)云數(shù)據(jù)中心的基礎(chǔ)設(shè)施由M個(gè)不同的物理主機(jī)組成,，每個(gè)物理主機(jī)由K種資源表示（如CPU,，內(nèi)存，網(wǎng)絡(luò)帶寬,，磁盤等）,。每個(gè)物理主機(jī)j對(duì)每種資源k有一個(gè)已知容量Cjk，其中j∈{1…M},，k∈{1…K},。例如規(guī)定CPU資源由索引值1表示，即k=1時(shí)表示為CPU資源,。

　　2.2 資源調(diào)度的優(yōu)化目標(biāo)

　?。?）減少資源浪費(fèi)：不同的虛擬機(jī)資源調(diào)度策略對(duì)物理主機(jī)的剩余資源影響程度不同。考慮到將來虛擬機(jī)資源請(qǐng)求,，各個(gè)物理主機(jī)上的剩余資源應(yīng)該在不同維度資源之間保持均衡,。否則，可能會(huì)阻止未來的虛擬機(jī)資源請(qǐng)求,，從而造成浪費(fèi)資源,。

　　（2）降低服務(wù)等級(jí)約定（SLA）違背率：滿足用戶服務(wù)質(zhì)量是衡量云計(jì)算服務(wù)的重要指標(biāo),。服務(wù)質(zhì)量請(qǐng)求通常表示為服務(wù)等級(jí)約定（SLA）,，在云系統(tǒng)中服務(wù)等級(jí)約定由最大響應(yīng)時(shí)間或者最小吞吐量決定。

　?。?）負(fù)載均衡：在云環(huán)境中將資源分配給虛擬機(jī),，要使得所有物理主機(jī)上的資源利用率均衡。

3 多目標(biāo)優(yōu)化的資源調(diào)度算法

　　多目標(biāo)優(yōu)化資源調(diào)度算法由兩個(gè)資源調(diào)度過程組成：虛擬機(jī)資源初始化分配與虛擬機(jī)動(dòng)態(tài)遷移,。

　　3.1 綜合權(quán)衡值

　　在提出多目標(biāo)優(yōu)化算法之前,，本文引入多目標(biāo)優(yōu)化算法核心的計(jì)分函數(shù)，稱為“綜合權(quán)衡值”,，其目的是為了衡量在過去的TM時(shí)間內(nèi)服務(wù)等級(jí)約定（SLA）違背率程度,、資源浪費(fèi)的程度與數(shù)據(jù)中心負(fù)載均衡度。所以“綜合權(quán)衡值”主要由服務(wù)等級(jí)約定（SLA）違背率,、資源浪費(fèi)的程度以及數(shù)據(jù)中心負(fù)載均衡度三部分的效用函數(shù)組成,。

　　第一個(gè)是服務(wù)等級(jí)約定違背率的效用函數(shù)，在一個(gè)給定的時(shí)刻,，定義函數(shù)U衡量服務(wù)等級(jí)約定的違背率,，公式（1）表示當(dāng)虛擬機(jī)集合V部署在物理主機(jī)h上時(shí)，函數(shù)U（H,，V,，T）衡量在t時(shí)刻對(duì)于物理主機(jī)h的CPU資源需求的不滿意度。

　　式中,，ri（t）表示虛擬機(jī)i請(qǐng)求的CPU資源量,，ai（t）表示物理主機(jī)分配給虛擬機(jī)i請(qǐng)求的CPU資源量。它的范圍值在[0,，1],。

　　第二個(gè)是資源浪費(fèi)程度的效用函數(shù)，如公式（2）所示,，在一個(gè)給定的時(shí)刻,，定義函數(shù)L衡量虛擬機(jī)集合V部署在物理主機(jī)h上時(shí)，物理主機(jī)h上的資源浪費(fèi)程度,。

　　式中,，Rk代表第k種資源的歸一化的剩余資源,，即剩余資源占總資源的比率；用下標(biāo)z表示多維資源中最小歸一化的剩余容量的資源,。在服務(wù)器上浪費(fèi)的剩余資源被計(jì)算為最小的歸一化剩余資源與其他剩余資源差異的總和,，它的值范圍為[0，1],。

　　最后一個(gè)是數(shù)據(jù)中心的負(fù)載均衡效用函數(shù),。更具體地說，就是數(shù)據(jù)中心中物理主機(jī)之間資源負(fù)載的均衡程度,。在一個(gè)給定的時(shí)刻,，定義函數(shù)B衡量數(shù)據(jù)中心的負(fù)載均衡度，如公式（3）表示虛擬機(jī)集V部署在物理主機(jī)h上時(shí),，數(shù)據(jù)中心的負(fù)載均衡程度,。

　　式中，M為所有物理主機(jī)節(jié)點(diǎn)的數(shù)量,，CPUj（t）表示物理主機(jī)j在t時(shí)刻的CPU利用率,，CPUavg為M個(gè)物理主機(jī)節(jié)點(diǎn)的CPU利用率均值。

　　本文使用DR表示“綜合權(quán)衡值”,，如公式（4）,，表示在過去的TM時(shí)間內(nèi)多目標(biāo)優(yōu)化的綜合效用函數(shù)性能指標(biāo),。

　　式中α1+α2+α3=1,，α1、α2,、α3是各個(gè)子目標(biāo)的權(quán)衡值,，通過設(shè)置α1、α2,、α3的大小可以權(quán)衡各個(gè)子目標(biāo)實(shí)現(xiàn)的程度,。

　　3.2 虛擬機(jī)資源初始化調(diào)度算法

　　虛擬機(jī)資源調(diào)度初始化分配算法過程如圖2所示。

　?。?）首先根據(jù)指定的過濾方法（例如物理主機(jī)剩余資源不能滿足用戶需求）對(duì)所有可用的物理主機(jī)節(jié)點(diǎn)進(jìn)行過濾,，得到滿足過濾條件的物理主機(jī)節(jié)點(diǎn)集合。

　?。?）計(jì)算出過濾后所有物理主機(jī)“綜合權(quán)衡值”,，然后將所有過濾后的物理主機(jī)節(jié)點(diǎn)按照“綜合權(quán)衡值”的大小進(jìn)行升序排列。

　?。?）選擇“綜合權(quán)衡值”最小的物理主機(jī)給用戶分配虛擬機(jī)資源,。

　　3.3 虛擬機(jī)動(dòng)態(tài)遷移算法

　　虛擬機(jī)的遷移涉及到確定遷移的時(shí)機(jī)、虛擬機(jī)的選擇和虛擬機(jī)的放置問題,。

　　通過實(shí)時(shí)監(jiān)測物理主機(jī),，確定虛擬機(jī)遷移的時(shí)機(jī),。為了防止暫時(shí)的越界而發(fā)生的虛擬機(jī)遷移，在資源監(jiān)測過程中可以設(shè)定一個(gè)固定大小的時(shí)間段,，并且資源利用率在這個(gè)時(shí)間段內(nèi)按照固定的時(shí)間間隔采樣,，如果在采樣結(jié)果中資源利用率超過門限值的次數(shù)大于設(shè)定的次數(shù)，則開始預(yù)測下一次的資源利用率,，當(dāng)下一次資源利用率也超過了門限值時(shí)觸發(fā)虛擬機(jī)的遷移,。本文使用了時(shí)間序列預(yù)測技術(shù)[8]里的自回歸模型AR（n），此模型可以預(yù)測未來的資源利用率,。

　　在確定哪個(gè)物理主機(jī)需要遷移虛擬機(jī)后,，系統(tǒng)會(huì)選擇將該物理主機(jī)上的虛擬機(jī)遷移出去。此時(shí),，需要討論虛擬機(jī)的選擇與虛擬機(jī)的放置策略,。關(guān)于虛擬機(jī)的選擇以及放置，可以通過以下算法獲得,。

　　虛擬機(jī)動(dòng)態(tài)遷移算法：

　　for all vmi deployed in ReHost do

　　for all j∈1...M,，j≠ReHost do

　　BeScore=DR（ReHost，vmInHost（ReHost）,，T）+

　　DR（j,，vmInHost，T）,；

　　AfScore=DR（ReHost,，vmInHost（ReHost）\i，T+

　　DR（j,，vmInHost∪i,，T）；

　　MigrationScore（i,，j）=BeScore-AfScore,；

　　end for

　　end for

　　iz，jz=argmax（MigrationScore（i,，j））,；

　　if MigrationScore（iz，jz）>0 then

　　perform migration,；

　　else

　　stop migration,；

　　end if

　　算法思路：在確定哪個(gè)物理主機(jī)需要遷移虛擬機(jī)之后，考慮該物理主機(jī)上哪一個(gè)虛擬機(jī)需要遷移,，然后確定遷移到哪一個(gè)物理主機(jī)上,。算法中第一層循環(huán)為遍歷遷移源物理主機(jī)上的所有虛擬機(jī)，第二層循環(huán)是遍歷除了遷移源物理主機(jī)之外的所有物理主機(jī)節(jié)點(diǎn),。經(jīng)過兩次循環(huán),，首先計(jì)算出在遷移之前,，遷移源物理主機(jī)與遷移目的物理主機(jī)的綜合權(quán)衡值的和值，然后計(jì)算出遷移之后源物理主機(jī)與目的物理主機(jī)的綜合權(quán)衡值的和值,，最后計(jì)算出虛擬機(jī)從源物理主機(jī)遷移到目的物理主機(jī)的遷移值,。遷移值被定義為兩個(gè)綜合權(quán)衡和值之間的差異。最后,，取出所有遷移值中的最高值,，只有遷移值為正時(shí)才會(huì)考慮進(jìn)行遷移。

4 測試及結(jié)果分析

　　4.1 仿真建立

　　本節(jié)采用CloudSim[9]云計(jì)算仿真平臺(tái)進(jìn)行多目標(biāo)優(yōu)化的資源調(diào)度算法的驗(yàn)證,，并提供了多目標(biāo)優(yōu)化的資源調(diào)度算法與其他不同算法相比較的結(jié)果,。CloudSim是由澳大利亞墨爾本大學(xué)的網(wǎng)格實(shí)驗(yàn)室和Gridbus項(xiàng)目推出的云計(jì)算仿真軟件。

　　仿真實(shí)驗(yàn)的硬件環(huán)境：Intel Core i5,，CPU主頻為2.66 GHz,，內(nèi)存4 GB，硬盤500 GB,。軟件環(huán)境：Windows 7操作系統(tǒng),，MyEclipse 10.7和CloudSim-3.0.3，以及Java1.8.0開發(fā)工具,。在多目標(biāo)優(yōu)化資源調(diào)度算法中設(shè)置門限值為80%,，物理主機(jī)節(jié)點(diǎn)監(jiān)測的周期為3 s，對(duì)系統(tǒng)資源的采樣間隔為4 s,，一次監(jiān)測過程的時(shí)間長度為1 min,，即一次監(jiān)測過程中有20次歷史監(jiān)測數(shù)據(jù)。當(dāng)超過門限值的次數(shù)大于等于10次就觸發(fā)告警,。任務(wù)的數(shù)量分三種情況模擬：200個(gè),、400個(gè),、600個(gè),。

　　這個(gè)實(shí)驗(yàn)主要分析本文提出的多目標(biāo)優(yōu)化算法的有效性，比較了以下4種算法：（1）單目標(biāo)減少資源浪費(fèi)算法,；（2）單目標(biāo)降低SLA違背率算法,；（3）單目標(biāo)負(fù)載均衡算法；（4）多目標(biāo)優(yōu)化資源調(diào)度算法,。

　　4.2 仿真結(jié)果與分析

　　如圖3,、圖4、圖5所示描述了在不同的資源調(diào)度算法下的資源浪費(fèi)程度,、SLA違背率以及數(shù)據(jù)中心的不均衡度,。資源浪費(fèi)程度越高，表示各種資源利用的差距越大,。SLA違背率越低說明用戶的服務(wù)質(zhì)量越高,。數(shù)據(jù)中心負(fù)載均衡度越低代表負(fù)載均衡效果越好,。由圖可知采用減少資源浪費(fèi)的算法時(shí)資源浪費(fèi)的程度最低，使用減少SLA違背率算法時(shí)SLA違背率最低,，使用負(fù)載均衡算法時(shí)數(shù)據(jù)中心不均衡度是最低的,，這是因?yàn)樵趫?zhí)行單目標(biāo)優(yōu)化問題時(shí)，單目標(biāo)優(yōu)化算法能得出最優(yōu)解,。由圖3,、圖4、圖5可知,，雖然單目標(biāo)優(yōu)化算法在各自的優(yōu)化目標(biāo)上取得最優(yōu)解,，但是單目標(biāo)算法在其他目標(biāo)實(shí)現(xiàn)的效果上比較差，如雖然使用減少SLA算法時(shí)SLA違背率最低,，但是資源利用率很低,。這是因?yàn)樵诙嗄繕?biāo)優(yōu)化的問題中，各個(gè)子目標(biāo)之間有時(shí)是沖突的,，一個(gè)解不能同時(shí)使所有的子目標(biāo)達(dá)到最優(yōu),，所以需要在各個(gè)目標(biāo)之間做好協(xié)調(diào)權(quán)衡。

　　多目標(biāo)優(yōu)化算法就很好地解決了多個(gè)目標(biāo)之間相互沖突的問題,，雖然多目標(biāo)優(yōu)化算法不能使數(shù)據(jù)中心取得最低的資源浪費(fèi)程度,、最低的服務(wù)等級(jí)約定違背率與最低的不均衡度，但是在各個(gè)目標(biāo)優(yōu)化的效果比較好,。如圖5所示,，多目標(biāo)優(yōu)化資源調(diào)度算法的數(shù)據(jù)中心的不均衡度比負(fù)載均衡算法的值高，但是低于減少SLA違背率算法與減少資源浪費(fèi)算法的值,。

5 總結(jié)

　　本文針對(duì)多目標(biāo)優(yōu)化的資源調(diào)度問題,，提出了多目標(biāo)資源優(yōu)化的資源調(diào)度策略。多目標(biāo)優(yōu)化資源調(diào)度的策略能夠在多個(gè)相互沖突的目標(biāo)之間實(shí)現(xiàn)最優(yōu)權(quán)衡,。通過仿真實(shí)驗(yàn)驗(yàn)證了多目標(biāo)資源優(yōu)化的資源調(diào)度策略的有效性,。

參考文獻(xiàn)

　　[1] BHARDWAJ S，  JAIN L,，  JAIN S. Cloud computing： a study of infrastructure as a service （IAAS）[J]. International Journal of Engineering and Information Technology,， 2010，  2（1）：60-63.

　　[2] UHLIG R,， NEIGER G,， RODGERS D， et al. Intel virtualization technology[J]. Computer,，  2005,， 38（5）：48-56.

　　[3] CHEN Y， DAS A,， QIN W,， et al. Managing server energy and operational costs in hosting centers[C]. ACM SIGMETRICS Performance Evaluation Review,， ACM， 2005,，33（1）： 303-314.

　　[4] KUSIC D,， KEPHART J O， HANSON J E,， et al. Power and performance management of virtualized computing environments via lookaheadcontrol[J]. Cluster Computing,， 2009， 12（1）：1-15.

　　[5] HU J,， GU J,， SUN G， et al. A scheduling strategy on load balancing of virtual machine resources in cloud computing environment[C]. Parallel Architectures,， Algorithms and Programming（PAAP）,， 2010 Third International Symposium on. IEEE， 2010：89-96.

　　[6] WOOD T,， SHENOY P J,， VENKATARAMANI A， et al. Black-box and Gray-box strategies for virtual machine migration[C]. NSDI,， 2007：17-17.

　　[7] TANG C,， STEINDER M， SPREITZER M,， et al. A scalable application placement controller for enterprise data centers[C]. Proceedings of the 16th International Conference on World Wide Web,， ACM， 2007：331-340.

　　[8] BOX G E P,， JENKINS G M,， REINSEL G C. Time series analysis： forecasting and control[M]. New York： John Wiley & Sons， 2013.

　　[9] CALHEIROS R N,， RANJAN R,， BELOGLAZOV A， et al. CloudSim： a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J]. Software： Practice and Experience,， 2011,，41（1）：23-50.