摘  要：云計算通過虛擬化技術將基礎設施硬件資源虛擬化，以動態可縮放的方式提供給用戶。云計算基礎設施規模不斷增加導致資源調度系統負載不均衡，從而造成資源浪費等問題。提出多目標優化資源調度策略和相應的算法，試圖同時滿足多個資源調度優化目標，如減少資源浪費，降低服務等級約定（SLA）違背率、保持系統負載均衡等。通過仿真實驗，驗證了多目標優化資源調度的策略能夠在多個相互沖突的目標之間實現最優權衡。

　　關鍵詞： 云計算；多目標優化；虛擬機；資源調度

0 引言

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

　　針對以上問題，本文提出了多目標優化的資源調度策略，該方法在多個相互沖突的目標之間實現最優權衡，如降低服務等級協議違背率、減少資源浪費和負載均衡等。

1 相關工作分析

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

　　現有研究中很少將資源浪費、保證服務等級約定和負載均衡進行綜合考慮，實現虛擬機資源調度的多目標優化。大部分的研究只是將多目標優化問題轉化為若干個單目標優化問題分階段解決，很少是同時對多個目標進行優化的。

2 資源優化調度建模

　　2.1 數學模型

　　IaaS中虛擬機資源分配問題可以描述成在動態云環境中多維裝箱問題。本文構建了數學模型，使用元組q=<t，VMSET，ts>表示各個虛擬機資源調度請求，其中t表示虛擬機資源請求到達的時刻，VMSET表示要申請的虛擬機集，ts表示虛擬機的生命周期。

　　一個簡單的例子如圖1所示。涉及到7個虛擬機資源請求，如虛擬機請求{2，{1，2}，6}表示請求在時刻2到達，申請了序號為1與2兩個虛擬機，虛擬機的生命周期為6個時間單元。在時刻15時虛擬機6、7還在運行，1~5號虛擬機被刪除了。

　　本文考慮一個云數據中心的基礎設施由M個不同的物理主機組成，每個物理主機由K種資源表示（如CPU，內存，網絡帶寬，磁盤等）。每個物理主機j對每種資源k有一個已知容量Cjk，其中j∈{1…M}，k∈{1…K}。例如規定CPU資源由索引值1表示，即k=1時表示為CPU資源。

　　2.2 資源調度的優化目標

　　（1）減少資源浪費：不同的虛擬機資源調度策略對物理主機的剩余資源影響程度不同。考慮到將來虛擬機資源請求，各個物理主機上的剩余資源應該在不同維度資源之間保持均衡。否則，可能會阻止未來的虛擬機資源請求，從而造成浪費資源。

　　（2）降低服務等級約定（SLA）違背率：滿足用戶服務質量是衡量云計算服務的重要指標。服務質量請求通常表示為服務等級約定（SLA），在云系統中服務等級約定由最大響應時間或者最小吞吐量決定。

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

3 多目標優化的資源調度算法

　　多目標優化資源調度算法由兩個資源調度過程組成：虛擬機資源初始化分配與虛擬機動態遷移。

　　3.1 綜合權衡值

　　在提出多目標優化算法之前，本文引入多目標優化算法核心的計分函數，稱為“綜合權衡值”，其目的是為了衡量在過去的TM時間內服務等級約定（SLA）違背率程度、資源浪費的程度與數據中心負載均衡度。所以“綜合權衡值”主要由服務等級約定（SLA）違背率、資源浪費的程度以及數據中心負載均衡度三部分的效用函數組成。

　　第一個是服務等級約定違背率的效用函數，在一個給定的時刻，定義函數U衡量服務等級約定的違背率，公式（1）表示當虛擬機集合V部署在物理主機h上時，函數U（H，V，T）衡量在t時刻對于物理主機h的CPU資源需求的不滿意度。

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

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

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

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

　　式中，M為所有物理主機節點的數量，CPUj（t）表示物理主機j在t時刻的CPU利用率，CPUavg為M個物理主機節點的CPU利用率均值。

　　本文使用DR表示“綜合權衡值”，如公式（4），表示在過去的TM時間內多目標優化的綜合效用函數性能指標。

　　式中α1+α2+α3=1，α1、α2、α3是各個子目標的權衡值，通過設置α1、α2、α3的大小可以權衡各個子目標實現的程度。

　　3.2 虛擬機資源初始化調度算法

　　虛擬機資源調度初始化分配算法過程如圖2所示。

　　（1）首先根據指定的過濾方法（例如物理主機剩余資源不能滿足用戶需求）對所有可用的物理主機節點進行過濾，得到滿足過濾條件的物理主機節點集合。

　　（2）計算出過濾后所有物理主機“綜合權衡值”，然后將所有過濾后的物理主機節點按照“綜合權衡值”的大小進行升序排列。

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

　　3.3 虛擬機動態遷移算法

　　虛擬機的遷移涉及到確定遷移的時機、虛擬機的選擇和虛擬機的放置問題。

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

　　在確定哪個物理主機需要遷移虛擬機后，系統會選擇將該物理主機上的虛擬機遷移出去。此時，需要討論虛擬機的選擇與虛擬機的放置策略。關于虛擬機的選擇以及放置，可以通過以下算法獲得。

　　虛擬機動態遷移算法：

　　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

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

4 測試及結果分析

　　4.1 仿真建立

　　本節采用CloudSim[9]云計算仿真平臺進行多目標優化的資源調度算法的驗證，并提供了多目標優化的資源調度算法與其他不同算法相比較的結果。CloudSim是由澳大利亞墨爾本大學的網格實驗室和Gridbus項目推出的云計算仿真軟件。

　　仿真實驗的硬件環境：Intel Core i5，CPU主頻為2.66 GHz，內存4 GB，硬盤500 GB。軟件環境：Windows 7操作系統，MyEclipse 10.7和CloudSim-3.0.3，以及Java1.8.0開發工具。在多目標優化資源調度算法中設置門限值為80%，物理主機節點監測的周期為3 s，對系統資源的采樣間隔為4 s，一次監測過程的時間長度為1 min，即一次監測過程中有20次歷史監測數據。當超過門限值的次數大于等于10次就觸發告警。任務的數量分三種情況模擬：200個、400個、600個。

　　這個實驗主要分析本文提出的多目標優化算法的有效性，比較了以下4種算法：（1）單目標減少資源浪費算法；（2）單目標降低SLA違背率算法；（3）單目標負載均衡算法；（4）多目標優化資源調度算法。

　　4.2 仿真結果與分析

　　如圖3、圖4、圖5所示描述了在不同的資源調度算法下的資源浪費程度、SLA違背率以及數據中心的不均衡度。資源浪費程度越高，表示各種資源利用的差距越大。SLA違背率越低說明用戶的服務質量越高。數據中心負載均衡度越低代表負載均衡效果越好。由圖可知采用減少資源浪費的算法時資源浪費的程度最低，使用減少SLA違背率算法時SLA違背率最低，使用負載均衡算法時數據中心不均衡度是最低的，這是因為在執行單目標優化問題時，單目標優化算法能得出最優解。由圖3、圖4、圖5可知，雖然單目標優化算法在各自的優化目標上取得最優解，但是單目標算法在其他目標實現的效果上比較差，如雖然使用減少SLA算法時SLA違背率最低，但是資源利用率很低。這是因為在多目標優化的問題中，各個子目標之間有時是沖突的，一個解不能同時使所有的子目標達到最優，所以需要在各個目標之間做好協調權衡。

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

5 總結

　　本文針對多目標優化的資源調度問題，提出了多目標資源優化的資源調度策略。多目標優化資源調度的策略能夠在多個相互沖突的目標之間實現最優權衡。通過仿真實驗驗證了多目標資源優化的資源調度策略的有效性。

參考文獻

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