摘  要：云計(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)測(cè)系統(tǒng)中CPU、內(nèi)存資源、網(wǎng)絡(luò)帶寬的利用率，提出了白盒測(cè)試與黑盒測(cè)試的方法，并重點(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è)簡(jiǎn)單的例子如圖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)

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

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

　　（3）負(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)集合。

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

　　在確定哪個(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 測(cè)試及結(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)測(cè)的周期為3 s，對(duì)系統(tǒng)資源的采樣間隔為4 s，一次監(jiān)測(cè)過程的時(shí)間長(zhǎng)度為1 min，即一次監(jiān)測(cè)過程中有20次歷史監(jiān)測(cè)數(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.