徐忠勝，沈蘇彬

（南京郵電大學(xué)計(jì)算機(jī)學(xué)院，江蘇南京210003）

一種云計(jì)算資源的多目標(biāo)優(yōu)化的調(diào)度方法*

徐忠勝，沈蘇彬

（南京郵電大學(xué)計(jì)算機(jī)學(xué)院，江蘇南京210003）

云計(jì)算通過(guò)虛擬化技術(shù)將基礎(chǔ)設(shè)施硬件資源虛擬化，以動(dòng)態(tài)可縮放的方式提供給用戶。云計(jì)算基礎(chǔ)設(shè)施規(guī)模不斷增加導(dǎo)致資源調(diào)度系統(tǒng)負(fù)載不均衡，從而造成資源浪費(fèi)等問(wèn)題。提出多目標(biāo)優(yōu)化資源調(diào)度策略和相應(yīng)的算法，試圖同時(shí)滿足多個(gè)資源調(diào)度優(yōu)化目標(biāo)，如減少資源浪費(fèi)，降低服務(wù)等級(jí)約定（SLA）違背率、保持系統(tǒng)負(fù)載均衡等。通過(guò)仿真實(shí)驗(yàn)，驗(yàn)證了多目標(biāo)優(yōu)化資源調(diào)度的策略能夠在多個(gè)相互沖突的目標(biāo)之間實(shí)現(xiàn)最優(yōu)權(quá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云主要通過(guò)虛擬化技術(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)化，比如通過(guò)服務(wù)器的整合降低數(shù)據(jù)中心的能源消耗，但是降低了用戶需求的滿意度。有的研究工作為了減少SLA違背率，將虛擬機(jī)分散放在盡可能多的服務(wù)器上，降低了資源的利用率，這是因?yàn)椴煌膬?yōu)化目標(biāo)之間是相互沖突的。

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

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

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

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

IaaS中虛擬機(jī)資源分配問(wèn)題可以描述成在動(dòng)態(tài)云環(huán)境中多維裝箱問(wè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ī)被刪除了。

圖1 虛擬機(jī)資源分配實(shí)例

本文考慮一個(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ī)的剩余資源影響程度不同?？紤]到將來(lái)虛擬機(jī)資源請(qǐng)求，各個(gè)物理主機(jī)上的剩余資源應(yīng)該在不同維度資源之間保持均衡。否則，可能會(huì)阻止未來(lái)的虛擬機(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í)間或者最小吞吐量決定。

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

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

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

3.1 綜合權(quán)衡值

在提出多目標(biāo)優(yōu)化算法之前，本文引入多目標(biāo)優(yōu)化算法核心的計(jì)分函數(shù)，稱為“綜合權(quán)衡值”，其目的是為了衡量在過(guò)去的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ù)。更具體地說(shuō)，就是數(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），表示

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

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

虛擬機(jī)資源調(diào)度初始化分配算法過(guò)程如圖2所示。在過(guò)去的TM時(shí)間內(nèi)多目標(biāo)優(yōu)化的綜合效用函數(shù)性能指標(biāo)。

圖2 虛擬機(jī)資源初始化分配過(guò)程

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

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

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

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

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

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

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

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

算法思路：在確定哪個(gè)物理主機(jī)需要遷移虛擬機(jī)之后，考慮該物理主機(jī)上哪一個(gè)虛擬機(jī)需要遷移，然后確定遷移到哪一個(gè)物理主機(jī)上。算法中第一層循環(huán)為遍歷遷移源物理主機(jī)上的所有虛擬機(jī)，第二層循環(huán)是遍歷除了遷移源物理主機(jī)之外的所有物理主機(jī)節(jié)點(diǎn)。經(jīng)過(guò)兩次循環(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開(kāi)發(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è)過(guò)程的時(shí)間長(zhǎng)度為1 min，即一次監(jiān)測(cè)過(guò)程中有20次歷史監(jiān)測(cè)數(shù)據(jù)。當(dāng)超過(guò)門限值的次數(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違背率越低說(shuō)明用戶的服務(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)化問(wèn)題時(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)化的問(wèn)題中，各個(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)之間相互沖突的問(wèn)題，雖然多目標(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)算法的值。

圖3 不同資源調(diào)度算法下資源浪費(fèi)程度

圖4 不同資源調(diào)度算法下SLA違背率

圖5 不同資源調(diào)度算法下數(shù)據(jù)中心不均衡度

5 總結(jié)

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

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

A multi-objective optim ization scheduling method in Cloud com puting

Xu Zhongsheng，Shen Subin
（School of Computer，Nanjing University of Posts and Telecommunications，Nanjing 210003，China）

Cloud computing infrastructure virtualizes hardware resource by virtualization technology，and provides it to users in scalable way.The increasing size of cloud computing infrastructure results in the waste of resources because of system load imbalance and other issues.This paper proposes a multi-objective optimization of resource scheduling policies and a related algorithm that can simultaneously achieve multiple objectives，such as reducing the waste of resources，reducing the service level agreement（SLA）and keep the system load balance.Simulation results show that the multi-objective optimization of resource scheduling method can achieve the optimal trade-offs among multiple conflicting goals.

Cloud computing；multi-objective optimization；virtual machine；resource scheduling

TP393

A

1674-7720（2015）13-0017-04

2015-03-02）

徐忠勝（1989-），通信作者，男，碩士研究生，主要研究方向：計(jì)算機(jī)網(wǎng)絡(luò)。E-mail：xuzhongsheng722@sina.com。

江蘇省未來(lái)網(wǎng)絡(luò)前瞻性研究資助項(xiàng)目（BY2013095-1-08）

沈蘇彬（1964-），男，研究員，博士生導(dǎo)師，主要研究方向：計(jì)算機(jī)網(wǎng)絡(luò)、下一代電信網(wǎng)及網(wǎng)絡(luò)安全。