李濟漢，李素粉，張云勇，房秉毅

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

1 引言

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

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

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

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

2 問題描述與符號定義

本文主要針對云計算環(huán)境下虛擬機資源的調(diào)度問題進行分析。虛擬機資源是云計算環(huán)境下的一類主要云服務資源，載體是物理服務器資源。基于如圖1所示的網(wǎng)絡架構，用戶向云服務資源池提出服務請求，云服務資源池根據(jù)物理服務器和虛擬機的當前運行情況，依據(jù)一定的策略將合適的虛擬機分配給當前用戶，在滿足用戶需求的同時，使得服務器資源的總體利用率最高。

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

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

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

表1 基本符號定義

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

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

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

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

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

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

步驟2對于不飽和運行的云服務資源池，選擇一個虛擬機資源執(zhí)行當前任務，具體實現(xiàn)步驟如下。

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

（2）開啟第一臺物理服務器PS1，并將當前任務安排在虛擬機S1，1上運 行。

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

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

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

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

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

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

步驟4結束。

4 算例分析

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

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

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

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

其中，Yi∈{0，1}，當PMRatei=0時，Yi=0，否則Yi=1。

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

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

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

5 結束語

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

1 童曉渝,張云勇,房秉毅等.電信運營商實施云計算的策略建議.信息通信技術,2012(1)

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

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

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

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

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