李濟(jì)漢，李素粉，張?jiān)朴?，房秉?/p>

（1.北京郵電大學(xué) 北京100876；2.中國聯(lián)通集團(tuán)研究院 北京100048）

1 引言

云計(jì)算環(huán)境下，一些大型企業(yè)紛紛由傳統(tǒng)業(yè)務(wù)向云服務(wù)轉(zhuǎn)型，組建企業(yè)云，形成云服務(wù)資源池。例如，亞馬遜建立專門的數(shù)據(jù)中心，以云服務(wù)的形式向用戶和開發(fā)者提供存儲(chǔ)服務(wù)器、帶寬和CPU資源等。云計(jì)算在企業(yè)的深度和廣度應(yīng)用，必將催生大量云服務(wù)。以電信行業(yè)為例，國內(nèi)外電信運(yùn)營企業(yè)紛紛開展云計(jì)算相關(guān)的研究和應(yīng)用，逐漸形成基礎(chǔ)設(shè)施即服務(wù)（infrastructure as a service，IaaS）、平臺(tái)即服務(wù)（platform as a service，PaaS）和軟件即服務(wù)（software as a service，SaaS）3個(gè)層次的服務(wù)資源池，服務(wù)資源將呈現(xiàn)規(guī)?；蜕虡I(yè)化特點(diǎn)[1,2]。這種情況下，面對(duì)規(guī)模日益龐大的云服務(wù)資源池，有效的云服務(wù)資源調(diào)度方法對(duì)于提高服務(wù)資源的整體利用率具有重要意義。

當(dāng)虛擬化成為云計(jì)算的主要支撐技術(shù)后，資源虛擬化對(duì)數(shù)據(jù)中心的資源復(fù)用、關(guān)聯(lián)、動(dòng)態(tài)管理等方面都提出了新的挑戰(zhàn)。云計(jì)算數(shù)據(jù)中心虛擬機(jī)資源利用率問題已經(jīng)成為學(xué)術(shù)界的研究熱點(diǎn)之一。目前常用的云服務(wù)資源調(diào)度規(guī)則主要有輪轉(zhuǎn)法、最小負(fù)載優(yōu)化法和散列法等[3]。輪轉(zhuǎn)法通常是預(yù)先設(shè)定好一個(gè)輪轉(zhuǎn)周期（如物理服務(wù)器個(gè)數(shù)），依次將用戶需求的虛擬機(jī)分配給不同的物理服務(wù)器，一個(gè)輪轉(zhuǎn)周期結(jié)束后重新開始新一個(gè)輪轉(zhuǎn)；最小負(fù)載優(yōu)化法是每次分配虛擬機(jī)時(shí)，檢查前一段時(shí)間內(nèi)有物理服務(wù)器的負(fù)載情況，總是選擇當(dāng)前一段時(shí)間內(nèi)負(fù)載最小的物理服務(wù)器分配虛擬機(jī)；散列法預(yù)先設(shè)置一個(gè)散列函數(shù)，用于將反映用戶需求的虛擬機(jī)映射到相應(yīng)的物理服務(wù)器上。

基于上述基本調(diào)度規(guī)則，相關(guān)學(xué)者對(duì)云計(jì)算數(shù)據(jù)中心的虛擬機(jī)調(diào)度問題進(jìn)行了大量研究。參考文獻(xiàn)[4]針對(duì)云環(huán)境下，數(shù)據(jù)中心虛擬化資源的一致共享和多租戶應(yīng)用異構(gòu)性之間的矛盾所帶來的，服務(wù)器內(nèi)部多種資源間分配不均衡問題，研究并提出了基于多維協(xié)同聚合的虛擬機(jī)調(diào)度機(jī)制。參考文獻(xiàn)[5]針對(duì)云計(jì)算中物理服務(wù)器間的負(fù)載不均衡問題，提出一種基于多屬性層次分析的虛擬機(jī)部署與調(diào)度策略，該算法將虛擬機(jī)按照資源的需求特點(diǎn)進(jìn)行分類，根據(jù)該虛擬機(jī)量化后的權(quán)向量以及服務(wù)器資源的使用記錄，對(duì)各個(gè)服務(wù)器進(jìn)行預(yù)測(cè)評(píng)價(jià)，以期選擇最佳服務(wù)器進(jìn)行部署。參考文獻(xiàn)[6]針對(duì)傳統(tǒng)虛擬機(jī)調(diào)度方法中，虛擬機(jī)申請(qǐng)時(shí)調(diào)用相應(yīng)負(fù)載均衡算法將虛擬機(jī)調(diào)度到相應(yīng)的物理服務(wù)器上，不能達(dá)到整體效益最優(yōu)的問題，提出了一種實(shí)時(shí)滿足運(yùn)營商資源最高效益的動(dòng)態(tài)調(diào)度方法?；谠摲椒?，每次新加入用戶時(shí)，新加入的用戶資源和先前分配的資源一起重新在所有服務(wù)器上規(guī)劃，進(jìn)行全局虛擬機(jī)調(diào)度，遷移那些能給系統(tǒng)帶來足夠效益的虛擬機(jī)，完成全局最優(yōu)的虛擬機(jī)部署。

由于服務(wù)資源在處理業(yè)務(wù)請(qǐng)求時(shí)需要消耗一定的時(shí)間，隨著訪問服務(wù)資源次數(shù)的增加，服務(wù)請(qǐng)求會(huì)產(chǎn)生排隊(duì)現(xiàn)象，導(dǎo)致等待時(shí)間的產(chǎn)生。在實(shí)際的業(yè)務(wù)服務(wù)選擇中，排隊(duì)等待時(shí)間往往是云服務(wù)資源調(diào)度的一個(gè)關(guān)鍵決策因素。然而現(xiàn)有文獻(xiàn)鮮有提及。因此，本文提出了一種服務(wù)運(yùn)行狀態(tài)和服務(wù)等待時(shí)間的調(diào)度方法，并設(shè)計(jì)具體的計(jì)算規(guī)則，提高服務(wù)資源的均衡利用率。

2 問題描述與符號(hào)定義

本文主要針對(duì)云計(jì)算環(huán)境下虛擬機(jī)資源的調(diào)度問題進(jìn)行分析。虛擬機(jī)資源是云計(jì)算環(huán)境下的一類主要云服務(wù)資源，載體是物理服務(wù)器資源?；谌鐖D1所示的網(wǎng)絡(luò)架構(gòu)，用戶向云服務(wù)資源池提出服務(wù)請(qǐng)求，云服務(wù)資源池根據(jù)物理服務(wù)器和虛擬機(jī)的當(dāng)前運(yùn)行情況，依據(jù)一定的策略將合適的虛擬機(jī)分配給當(dāng)前用戶，在滿足用戶需求的同時(shí)，使得服務(wù)器資源的總體利用率最高。

為有效提高資源池中虛擬機(jī)的平均利用率，本文針對(duì)飽和與不飽和兩種資源池運(yùn)行狀態(tài)，分別設(shè)計(jì)虛擬機(jī)資源調(diào)度策略。為便于描述虛擬機(jī)資源調(diào)度算法，給出表1所示符號(hào)定義。

3 資源調(diào)度實(shí)現(xiàn)算法

假設(shè)云服務(wù)資源池中有I個(gè)物理服務(wù)器PSi，i=1，2，3，…，I，I為正整數(shù)，每個(gè)物理服務(wù)器PSi上承載Ji個(gè)虛擬服務(wù)器Si,j（以下簡(jiǎn)稱虛擬機(jī)）,i=1，2，3，…，I，j=1，2，3，…，Ji，Ji是正整數(shù)，每個(gè)虛擬機(jī)可同時(shí)并行運(yùn)行pNi,j個(gè)任務(wù),pNi,j>0，是正整數(shù)。

表1 基本符號(hào)定義

利用任務(wù)到達(dá)觸發(fā)資源分配，當(dāng)任務(wù)到達(dá)時(shí)，基于資源調(diào)度規(guī)則，選擇一個(gè)虛擬機(jī)資源，執(zhí)行該任務(wù)。本文提出的虛擬機(jī)資源調(diào)度步驟如下。

步驟1根據(jù)資源池中物理服務(wù)器的運(yùn)行狀態(tài)，判斷云服務(wù)資源池的運(yùn)行狀態(tài)PoolStatus，具體方法如下。

（1）通過圖1所示的云服務(wù)資源監(jiān)控與調(diào)度服務(wù)器，對(duì)于每個(gè)物理服務(wù)器PSi，獲取其承載的每個(gè)虛擬機(jī)Si，j上正在運(yùn)行的任務(wù)數(shù)pni，j。

（2）計(jì)算物理服務(wù)器PSi的利用率PMRatei，i=1，2，3，…，I，計(jì)算規(guī)則如式（1）：

其中，分母表示物理服務(wù)器PSi可以并行運(yùn)行的最大任務(wù)數(shù)，分子表示當(dāng)前運(yùn)行的任務(wù)數(shù)。PMRatei=1，表示物理服務(wù)器PSi處于飽和運(yùn)行狀態(tài)；PMRatei=0，表示物理服務(wù)器i上沒有虛擬機(jī)在執(zhí)行任務(wù)，本文假設(shè)這種狀態(tài)下，物理服務(wù)器i處于未開啟狀態(tài)。

（3）判定云服務(wù)資源池的運(yùn)行狀態(tài)PoolStatus。對(duì)于所有物理服務(wù)器PSi，如果均有PMRatei=1，i=1，2，3，…，I，即所有可以執(zhí)行當(dāng)前任務(wù)的物理服務(wù)器都開啟且處于飽和運(yùn)行狀態(tài)，則將云服務(wù)資源池的狀態(tài)記為飽和狀態(tài)，即PoolStatus=1，轉(zhuǎn)步驟3；否則記為不飽和狀態(tài)，即PoolStatus=0，轉(zhuǎn)步驟2。

步驟2對(duì)于不飽和運(yùn)行的云服務(wù)資源池，選擇一個(gè)虛擬機(jī)資源執(zhí)行當(dāng)前任務(wù)，具體實(shí)現(xiàn)步驟如下。

（1）根據(jù)物理服務(wù)器PSi的利用率PMRatei，判斷是否所有物理服務(wù)器均未開啟，即當(dāng)前時(shí)刻該資源池沒有運(yùn)行任何任務(wù)。判斷方法為：對(duì)于i=1，2，3，…，I，均有物理服務(wù)器PSi的利用率PMRatei=0，則表明所有物理服務(wù)器均未開啟，轉(zhuǎn)步驟（2），否則，轉(zhuǎn)步驟（3）。

（2）開啟第一臺(tái)物理服務(wù)器PS1，并將當(dāng)前任務(wù)安排在虛擬機(jī)S1，1上運(yùn) 行。

（3）在開啟的物理服務(wù)器中，根據(jù)步驟1中的（2）計(jì)算物理服務(wù)器利用率PMRatei，選擇利用率最小的一臺(tái)物理服務(wù)器，轉(zhuǎn)步驟（4）。存在兩種特殊情況：若同時(shí)存在多臺(tái)物理服務(wù)器PSi的利用率相同且最小，則選擇值較小的一臺(tái)物理服務(wù)器，轉(zhuǎn)步驟（4）；若利用率最小的物理服務(wù)器PSi的利用率PMRatei=1，也就是說所有已開啟的物理服務(wù)器均飽和，則開啟下一臺(tái)物理服務(wù)器，并選擇該物理服務(wù)器上的第一個(gè)虛擬機(jī)執(zhí)行當(dāng)前任務(wù)，轉(zhuǎn)步驟4。

（4）在步驟（3）選定的物理服務(wù)器上，根據(jù)每個(gè)虛擬機(jī)Si，j上正在運(yùn)行的任務(wù)數(shù)pni，j，選 擇pni，j最小的一臺(tái)虛擬機(jī)執(zhí)行當(dāng)前任務(wù)，如果同時(shí)存在多個(gè)虛擬機(jī)的pni，j相同且最小，則選擇j值較小的一個(gè)虛擬機(jī)執(zhí)行當(dāng)前任務(wù)。

步驟3對(duì)于飽和運(yùn)行的云服務(wù)資源池，計(jì)算所有虛擬機(jī)資源的等待時(shí)間，選擇等待時(shí)間最短的虛擬機(jī)執(zhí)行當(dāng)前任務(wù)；對(duì)于候選虛擬機(jī)資源Si，j，如果當(dāng)前運(yùn)行實(shí)例數(shù)pni，j等于最大并行實(shí)例數(shù)pNi，j，則新的任務(wù)請(qǐng)求需要排隊(duì)等待。對(duì)于飽和運(yùn)行狀態(tài)的云服務(wù)資源池，每個(gè)虛擬機(jī)資源均處于飽和運(yùn)行狀態(tài)，虛擬機(jī)資源等待時(shí)間的計(jì)算方法如下。

（1）由調(diào)度服務(wù)器檢測(cè)虛擬機(jī)資源Si，j的運(yùn)行狀態(tài)并自 動(dòng)獲取相應(yīng)參數(shù)值，包括虛擬機(jī)Si，j當(dāng)前運(yùn)行實(shí)例數(shù)pni，j、虛擬機(jī)Si，j上 進(jìn)度最快的 任務(wù)的執(zhí)行 進(jìn)度sti，j、當(dāng)前虛 擬 機(jī)Si，j的任 務(wù)排隊(duì)數(shù)量queuei，j、虛擬機(jī)Si，j運(yùn) 行 完 一 個(gè) 任務(wù)所需 要 的 時(shí) 間ti，j。

（2）計(jì)算虛擬機(jī)Si，j資源等待時(shí)間wti，j，計(jì)算方法如式（2）所示：

（3）選擇等待時(shí)間wti，j最短的虛擬機(jī)執(zhí)行當(dāng)前任務(wù)，若同時(shí)存在多個(gè)虛擬機(jī)的等待時(shí)間相同且最小，則選擇i，j值較小的虛擬機(jī)資源。

步驟4結(jié)束。

4 算例分析

為了評(píng)測(cè)算法性能，采用現(xiàn)有的策略與本方法進(jìn)行比較。最小負(fù)載優(yōu)化法是目前常用的一種均衡調(diào)度方法，即每次分配虛擬機(jī)時(shí)，檢查前一段時(shí)間內(nèi)有物理服務(wù)器的負(fù)載情況，總是選擇當(dāng)前一段時(shí)間內(nèi)負(fù)載最小的物理服務(wù)器分配虛擬機(jī)。本文所提的調(diào)度方法實(shí)質(zhì)上是對(duì)最小負(fù)載優(yōu)化方法的一種改進(jìn)方法。本節(jié)通過算例分析，將本文所提的虛擬機(jī)資源均衡調(diào)度方法與最小負(fù)載優(yōu)化法進(jìn)行比較分析。

假設(shè)云服務(wù)資源池包含I個(gè)物理服務(wù)器節(jié)點(diǎn)，令I(lǐng)=20，不失一般性，假設(shè)I個(gè)物理服務(wù)器上的虛擬機(jī)數(shù)量相同且Ji=5，i=1,2,3,…,I。對(duì)于云服務(wù)資源池的初始狀態(tài)，采用隨機(jī)方法設(shè)置。根據(jù)第3節(jié)步驟3的（1），描述云服務(wù)資源池當(dāng)前運(yùn)行狀態(tài)的參數(shù)包括：虛擬機(jī)Si，j當(dāng)前運(yùn)行實(shí)例數(shù)pni，j、虛擬機(jī)Si，j上進(jìn)度最快的任務(wù)的執(zhí)行進(jìn)度sti，j以及當(dāng)前虛擬機(jī)Si，j的 任務(wù)排隊(duì)數(shù)量queuei，j。若表示物理服務(wù)器PSi處于關(guān)閉或者待機(jī)狀態(tài)。對(duì)于當(dāng)前需求情況，設(shè)計(jì)4種不同的當(dāng)前任務(wù)數(shù)，分別是TN=1、5、20、50。

計(jì)算指標(biāo)分為兩種：物理服務(wù)器的平均利用率μ和物理服務(wù)器的利用率偏差σ，前者計(jì)算方法如式（3）描述，反映物理資源的利用率情況；后者采用均方差的計(jì)算方法，如式（4）描述，計(jì)算結(jié)果反映一個(gè)數(shù)據(jù)集的離散程度，在這里用于描述各個(gè)物理服務(wù)器資源的均衡利用程度。

其中，分母I0表示處于關(guān)閉狀態(tài)的物理服務(wù)器數(shù)量，即PMRatei=0時(shí)的物理服務(wù)器數(shù)量。

其中，Yi∈{0，1}，當(dāng)PMRatei=0時(shí)，Yi=0，否則Yi=1。

分別采用最小負(fù)載優(yōu)化法和本文所提的調(diào)度方法，針對(duì)4種不同的當(dāng)前任務(wù)需求，分別對(duì)上述算例進(jìn)行計(jì)算，兩種計(jì)算指標(biāo)計(jì)算結(jié)果分別如表2和圖2、圖3所示。

表2和圖2、圖3顯示，對(duì)于不同的當(dāng)前任務(wù)請(qǐng)求數(shù)量，的值均優(yōu)于或不劣于，且的值均優(yōu)于或不劣于。表明本文所提的調(diào)度方法優(yōu)于一般的最小負(fù)載優(yōu)化方法，且隨著當(dāng)前請(qǐng)求任務(wù)數(shù)的增多，優(yōu)勢(shì)愈加明顯。本文所提調(diào)度方法實(shí)質(zhì)上是對(duì)最小負(fù)載優(yōu)化方法的一種改進(jìn)。通過該算例分析，進(jìn)一步驗(yàn)證本文所提的虛擬機(jī)資源調(diào)度方法相對(duì)一般的最小負(fù)載優(yōu)化方法具有改進(jìn)效果。

表2 兩種調(diào)度策略下平均利用率μ和偏差σ計(jì)算結(jié)果

5 結(jié)束語

針對(duì)云計(jì)算環(huán)境下的虛擬機(jī)資源調(diào)度問題，基于云服務(wù)資源池的虛擬機(jī)資源利用率和等待時(shí)間等狀態(tài)參數(shù)，設(shè)計(jì)一種面向虛擬機(jī)資源的均衡調(diào)度算法，算例分析表明所提方法的有效性。該算法對(duì)于提高虛擬機(jī)資源的均衡利用具有重要作用。

1 童曉渝,張?jiān)朴?房秉毅等.電信運(yùn)營商實(shí)施云計(jì)算的策略建議.信息通信技術(shù),2012(1)

2 袁文成,朱怡安,陸偉.面向虛擬資源的云計(jì)算資源管理機(jī)制.西北工業(yè)大學(xué)學(xué)報(bào),2010,28(5)

3 田文洪,趙勇.云計(jì)算——資源調(diào)度管理.北京:國防工業(yè)出版社,2011

4 孫鑫.面向云環(huán)境數(shù)據(jù)中心的高效資源調(diào)度機(jī)制研究.北京郵電大學(xué)博士學(xué)位論文,2012

5 莊威,桂小林,林建材等.云環(huán)境下基于多屬性層次分析的虛擬機(jī)部署與調(diào)度策略.西安交通大學(xué)學(xué)報(bào)，2013(2)

6 尹紅軍，李京，宋滸等.云計(jì)算中運(yùn)營商效益最優(yōu)的資源分配機(jī)制.華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版),2011(S1)