面向高校教學云服務的虛擬機動態調度方法＊

王 菁，王 崗，高 晶，李 寒，馬 倩

（1.北方工業大學云計算研究中心，北京100144；2.北方工業大學大規模流數據集成與分析技術北京市重點實驗室，北京100144）

1 引言

伴隨云計算技術的發展，高校逐步邁向云時代，校園云將成為高校重要的研究方向和信息化建設的主流。校園云能夠為學生、教師以及科研人員提供安全可靠的計算和存儲服務。它通過虛擬機的形式對用戶提供服務，可以動態調度各種物理資源，從而高效地管理云平臺中的資源［1］。

校園云平臺包含教學、科研兩類應用，為高校教師和學生提供教學及科研云服務。科研應用因其使用時間以及所需虛擬機數量不確定，呈現不可預知性、非周期性等特點，與傳統應用類似。例如，Hadoop實驗需要20臺虛擬機，使用時間為兩周。而教學應用具有周期性、可預測性、批量性等特點。例如，Java上機實驗課需要為每個學生分配一臺虛擬機，并且在第1～16周，每周一的1、2節課上課時間內使用。然而實際應用中資源利用率仍然較低。

分析原因可知，當前虛擬機調度機制為傳統調度方法，而傳統調度方法主要分為基于實時的調度與基于負載預測的調度兩類。若采用基于實時的調度方法，當上課期間出現過載或過閑的情況時才會進行調度遷移，而遷移需要消耗較大的帶寬資源、較多的能耗并且時間較長，勢必會影響上課質量；若采用基于負載預測的調度方法，對于新申請的課程虛擬機資源，沒有可參考的歷史運行數據，無法對物理機負載進行正確預測。所以，核心問題在于當前的虛擬機調度機制未考慮高校教學應用負載的特征，不能量體裁衣，這樣就會造成很多不必要的虛擬機遷移，以及由此帶來負載不均和資源浪費。

綜上所述，由于教學型應用的特殊性，面向教學需求的計算資源即虛擬機的調配這一關鍵問題又可進一步分解為以下兩個子問題：

（1）虛擬機創建時的部署問題，即決定新創建的虛擬機部署在哪臺物理機上；

（2）虛擬機使用時的動態調度問題，即根據物理機實際資源使用情況進行虛擬機的動態遷移。在前期工作［2］中針對第一個子問題進行了研究，定義了課程需求模型和物理機負載模型，提出了課程虛擬機部署算法。在此基礎上對第二個子問題開展研究，提出了“先平衡，后節能”的動態調度原理，定義了吻合度、遷移優先值、負載判定值等算法判定參數，最終提出了課程虛擬機動態調度算法（CRS），以期解決物理集群資源浪費、負載不均衡問題，實現節能、環保、高效的目的。

2 相關工作

虛擬機優化調度是虛擬機管理的核心問題，針對這一問題，學術界和工業界都提出了相關解決方案，下面將從面向節能、面向負載均衡、面向負載均衡以及節能三方面進行討論：

（1）面向節能方面，Mylavarapu S等人［3］將虛擬機的容量規劃問題建模為隨機優化問題，采用遺傳算法與蒙特卡羅模擬相結合的方式加以解決。他們首先根據平均工作負載來分配虛擬機資源，部署虛擬機；此外，根據應用的服務等級協議SLA（Service－Level Agreement）在每臺服務器上預留了空閑的資源池。這就避免了服務器過載、應用不能滿足SLA 而帶來的虛擬機遷移。該算法與傳統的基于峰值工作負載的算法相比，所需服務器的數量較少，實現了節能。Goudarzi H 等人［4］提出了一種生成虛擬機備份的方法——基于動態優化、局部搜索的算法，該算法決定了每臺服務器部署的虛擬機的數量。此外，還提出了節能虛擬機放置算法，該算法主要用來決定放置在不同物理機上的虛擬機副本數量。

（2）面向負載均衡方面，Chandakanna V R 等人［5］提出了一個適用于負載均衡集群的基于模型視圖控制器的自適應調整集群框架。該框架可自動部署新的虛擬機，自動升級現有應用，并且保證集群的一致性。Hu J等人［6］提出了一種根據所采集的歷史數據和系統當前狀態利用遺傳算法計算分配虛擬機資源后對系統的影響，從而找到最優分配方式的以負載均衡為目的的調度算法。

（3）兼顧節能以及負載均衡方面，Chang Y C等人［7］提出了一個基于學習算法的神經網絡模型。集群內的每臺服務器上部署了資源管理器用以預測云服務器的工作負載，從而高效地對資源進行分配，在提高服務器性能的同時降低能耗。

但是，目前的研究一般針對傳統的云數據中心，當然也有少數面向特定應用領域的，比如面向感知數據托管平臺［8］、電子 政務基礎架構云［9］、可對云資源進行綜合管理的清華云平臺［10］。但是，尚沒有針對高校教學應用的虛擬機動態調度機制，沒有考慮到教學云服務負載的特征，未能對癥下藥，利用周期性、可預測性、批量性進行有效的管理調度。

3 動態調度算法

3.1 問題定義

設校園云平臺的數據中心有n臺物理服務器，通過虛擬機動態調度使：

（1）活躍的物理機數量盡可能少。

（2）各活躍物理機的資源利用率盡可能均衡。

為了便于上述問題求解，本文作了如表1所示的定義。

Table 1 Definition of related symbols表1 相關符號定義

結合上述的相關問題可以定義：

3.2 調度原理

為了達到3.1節的目標，調度原理采用了“先平衡，后節能”的策略。對于實際負載較高的物理機進行虛擬機動態遷移操作，從而消除高負載的物理機，實現負載均衡。然后對于負載較低的物理機，選擇合適的物理機對低負載上的虛擬機進行動態遷移，從而關閉物理機，實現節能目的。

具體的調度原理如圖1所示。

Figure 1 Dynamic scheduling diagram of virtual machine圖1 虛擬機動態調度原理圖

在具體調度過程中，首先根據課程虛擬機運行時物理機實際資源使用情況對物理機進行分組；然后對于實際負載較高且已影響虛擬機正常運行的物理機，對綜合資源使用率較高的虛擬機進行遷移，目標主機根據待遷移虛擬機與正常物理機的相似程度及資源使用情況確定，從而消除高負載的物理機，動態遷移完成后更新物理機負載；當調度域內無過載物理機時，對于實際負載較低的物理機，進行虛擬機遷移操作，全部遷移完成之后，即可關閉該物理機，實現節能目的。

3.3 相關定義

定義1（課程虛擬機模型） 課程虛擬機模型可以定義為一個五元組：CVm＝（VMName，IWeek，FWeek，Resource，LSet），其中：

（1）VMName表示課程虛擬機名稱類，是課程虛擬機唯一性的標識。

（2）IWeek表示課程的起始周數，FWeek表示課程的結束周數。

（3）Resource表示課程虛擬機被分配的虛擬資源，每個元素可以表示為一個二元組Resource＝（Cpu，Memory），其中：Cpu表示被分配的虛擬CPU 數量；Memory表示被分配的虛擬內存大小。

（4）LSet表示課程具體的課時集，可表示為一個三元組：LSet＝（LSection，LDay，LWeek），其中，LSection表示課程在某一天具體上課的節數；LDay表示一周具體上課的時間，即課程所在的星期幾；LWeek表示課程所在的單雙周類，LWeek＝（SWeek，DWeek），其中，DWeek為1 表示雙周有課，SWeek為1表示單周有課，否則為0。

定義2（物理機負載模型） 物理機上所部署的課程虛擬機負載情況可定義為一個二元組：Cijk＝（PName，UResource）。其中：

（1）Cijk表示在第k周，星期j，i節課的物理機負載，其中1≤i≤5，1≤j≤5，1≤k≤16；

（2）PName＝ ｛VMName1，VMName2，…，VMNamew｝，其中w表示為第k周、星期j、i節課時間段所要同時進行的課程虛擬機的數目，VMNamew為第w個課程虛擬機的名稱；

（3）UResource表示物理機上已消耗的虛擬資源，可以表示為一個二元組UResource＝（Cpu，Memory），其中：Cpu表示已消耗的虛擬CPU 數量，Memory表示已消耗虛擬內存大小。

定義3（吻合度） 待遷移虛擬機與物理機負載相對應元之間的重合度高低。公式定義如下：

其中，Numoverlap表示待遷移虛擬機一共進行的課程次數，Numall表示與物理機負載相重合的課程數。

例如，一個待遷移虛擬機屬于C＋＋課程，該課程CVm＝（"C＋＋"，1，16，（2，4），｛（4，2，（1，1）），（5，1，（1，1））｝），可以得到該虛擬機一共進行了32次課程。若對于一臺物理機存在課程Java，課程虛擬機參數為CVm＝（"Java"，1，16，（2，4），（4，2，（1，1））），該物理機有Java課程虛擬機4臺，則該物理機與待遷移虛擬機的重合課程數為64，則吻合度GOFit＝16/64＝0.25。

定義4（判決周期T） 為了避免負載抖動的虛擬機進行遷移，本文統計λ倍的平均虛擬機遷移消耗時間Δt作為物理機狀態的判決周期，即T＝λ·Δt，通常λ大于5。

定義5（高負載物理機） 在判決周期T內，若某一物理機Pj（1≤j≤m，m為集群中物理機個數）某一資源維度上的資源利用率不小于Hi，則稱此物理機為高負載物理機。

定義6（低負載物理機） 在判決周期T內，若某一物理機Pj（1≤j≤m，m為集群中物理機個數）某一資源維度上的資源利用率不大于Li，則稱此物理機為低負載物理機。

定義7（負載判定值De） 該值用來對物理機的負載進行一個綜合度量，更加量化地顯示出過載與過閑的程度，通常用以下公式表示：

其中，RPi為T內物理機在資源維度i上的平均使用大小，TPi為物理機資源i的總量。De越小則負載越高，越大則負載越低。

文獻［11］只考慮了CPU 維度，但通常情況下，還要考慮內存、存儲等資源的維度。因此，本文通過對CPU、內存兩個維度的資源監控，更準確地度量了物理機負載。

定義8（遷移優先值） 該值用來對虛擬機的資源使用情況進行綜合評定，用以選出待遷移虛擬機，如上只考慮CPU、內存維度，所以用公式migrateValue＝wcpu·RVcpu＋wmemory·RVmemory計算，其中RVcpu為T 內虛擬機平均活動CPU 大小，RVmemory為T內虛擬機平均使用內存大小。

3.4 算法描述

當所部署的課程虛擬機正常運行時，虛擬機的負載會隨時間發生變化。因此，需要實時監控物理機、虛擬機負載情況，從而做出正確的優化調度。首先需要獲取集群中所有物理機的性能監控數據，根據De判斷物理機所處的隊列是高負載、低負載還是正常隊列。然后選取最高負載物理機，計算其上虛擬機的遷移優先值，選取待遷移的虛擬機后，根據當前物理機資源使用情況以及吻合度，選定目標主機，實施遷移操作。通過遷移即可消除高負載物理機，達到負載均衡的目的。最后對于最低負載物理機，對其上的虛擬機進行遷移，從而消除低負載物理機，關閉空閑物理機，實現節能目標。這樣通過對負載值的調節，可以同時兼顧負載均衡以及節能的目標。調度算法描述如下：

算法1 課程虛擬機動態調度算法（CRS算法）

輸入：集群內虛擬機和物理機的監控數據。

輸出：虛擬機和物理機遷移映射關系。

算法描述：

上述算法的輸出結果是遷移映射關系，根據該映射關系，執行遷移操作。需要注意的是，一個物理機同一時間只能進行一次遷移操作，避免因同時大規模遷移帶來集群的震蕩。遷移完成之后，更新平均虛擬機遷移消耗時間Δt，并調整監控數據獲取的周期T。

4 校園云平臺動態調度機制實現

4.1 調度系統架構

為實現上述面向高校教學云服務的虛擬機動態調度方法，本節提出了調度系統架構，架構圖如圖2所示。并且在以開源OpenStack Icehouse版本為基礎的校園云平臺上實現了面向教學需求的虛擬機動態調度系統。

Figure 2 Scheduling system architecture diagram圖2 調度系統架構圖

下面將對系統架構進行詳細闡述：

該系統的最底層為計算資源、存儲資源等物理資源；之上為通過服務器虛擬化技術形成的虛擬機資源，即虛擬化層，由于本系統是基于OpenStack這一開源虛擬化平臺管理工具，所以該層為Open－Stack虛擬化平臺；再往上則是本系統的核心部分，主要由數據存儲模塊、虛擬機調度模塊、虛擬機控制模塊組成。

下面將逐一介紹核心模塊的功能及其接口：

（1）數據存儲模塊。

存儲物理機預測負載：將根據虛擬機的課程詳情計算得到的的物理機預測負載存儲寫入到Mysql數據庫中；

存儲監控數據：將通過監控軟件獲得的物理機、虛擬機的實時資源（cpu、內存等）使用情況存儲到Mysql數據庫中；

存儲映射關系表：將服務器與虛擬機的放置映射關系存儲到Mysql數據庫中。

（2）虛擬機調度模塊。

吻合度計算：根據待遷移課程虛擬機課程信息和物理機負載計算物理機的吻合度大小；

物理機狀態判斷：根據監控所得數據、高低閾值判定物理機所處狀態；

負載判定值計算：根據物理機監控數據更加量化地計算物理機綜合資源使用情況；

遷移優先值計算：對于過載或過閑物理機上的虛擬機，根據監測數據對虛擬機的資源使用情況進行綜合判定；

動態調度：根據物理機狀態、負載判定值、遷移優先值、吻合度對虛擬機按照調度規則進行動態調度，生成遷移映射關系。

4.2 OpenStack動態調度機制擴展

由于OpenStack不支持虛擬機的動態在線遷移，因此，首先需要結合Ganglia監控軟件來獲取監控數據，實現物理機集群和虛擬機集群的實時監控。具體步驟如下：（1）通過UDP 協議將監控數據封裝為xml文件，被監控節點的監控信息匯聚到監控節點，從而將監控數據以xml文件形式存儲在監控節點；（2）由于Ganglia通過8651端口進行監控數據傳輸，所以等間隔地去讀取物理服務器端8651端口，獲得xml樹狀結構的數據；（3）通過SAXReader接口對xml數據進行解析，然后將獲得解析的監控數據實時地存入Mysql數據庫中。

其次，OpenStack熱遷移通過搭建分布式存儲Sheepdog實現共享存儲。Sheepdog是為kvm 虛擬化量身定做的分布式文件系統，相比共享SAN存儲，Sheepdog不存在單點故障，并且是開源的，沒有SAN 的價格昂貴。同時，Sheepdog也可作為Cinder、Glance和Swift的后端存儲，每臺服務器安裝Sheepdog后即是計算節點也是存儲節點。

最后，使用Python語言編寫課程虛擬機動態調度算法（CRS算法）并通過調用OpenStack Nova API中的live＿migration接口進行虛擬機在線遷移。

5 實驗驗證

該實驗使用8臺服務器構建的集群上搭建了OpenStack平臺，具體服務器配置如表2所示。

Table 2 Server configuration表2 服務器配置

如表2所示，sigsit.openstack.controller為控制節 點，computenode1、computenode2、computenode3、computenode4、computenode5、computenode6、computenode7為計算節點。

為了驗證課程虛擬機動態調度算法（CRS）的效果，本文從物理機負載監控值比較本算法與其他調度算法的優劣。首先通過表3的所有課程請求采用CRD 算法部署課程虛擬機，其中所有課程虛擬機的CPU 核數為1，內存為2GB。

Table 3 Details of the courses on request表3 課程請求詳情

其次，在所有課程虛擬機部署完成后，通過對不同動態調度策略的比較來驗證CRS 算法的優勢，調度策略采用目前使用較為廣泛的OpenStack開源軟件提供的SimpleSchedule（SS）以及貪心算法First Fit（FF）。另外，動態調度過程需要設定相關參數，若高閾值設定過高，容易造成虛擬機服務質量下降也無法得到遷移；而設置過低，會導致資源利用率不足的問題。若低閾值設定過高，當有新的虛擬機遷入時，容易成為高負載物理機，引起二次遷移；若設定過低，則會造成一定的資源浪費。Srikantaiah S等人［12］的研究表明，當CPU 利用率超過70%的時候虛擬機性能明顯下降，本文將相關值設定如下：Hcpu＝70%，Lcpu＝10%，Hmemory＝90%，Lmemory＝30%，T＝30s。

從圖3、圖4 可看出，在該課程首次上課時間段內，經本文提出的CRS算法動態調度之后，集群內CPU、內存基本達到負載均衡。而經其他兩種算法調度之后，可以消除高負載物理機，但是集群內資源嚴重不均衡，CPU 利用率差距大于25%，內存利用率差距大于60%。這樣雖然消除了高負載物理機，但是存在資源浪費。

綜上所述，本文提出的虛擬機動態調度算法（CRS），可在保證教學應用需求的同時，達到兼顧節能以及負載均衡多目標優化的目的。

Figure 3 CPU utilization of the cluster圖3 集 群CPU 利 用 率

Figure 4 Memory utilization of the cluster圖4 集群內存利用率

6 結束語

本文提出了面向高校教學云服務的虛擬機調度方法及系統，提出了“先平衡，后節能”的動態調度原理，提出了課程虛擬機動態調度算法（CRS），以期解決物理集群資源浪費、負載不均衡問題，實現節能、環保、高效的目的。但是，本文在資源維度的選取方面，只考慮了CPU 和內存這兩個維度，具有一定的局限性。為了更接近于真實的復雜環境，在日后的研究中可以考慮增加網絡帶寬、硬盤容量等維度，使得考量指標更豐富、更真實。

［1］ Nathuji R，Schwan K.Virtual power：Coordinated power management in virtualized enterprise systems［C］∥Proc of ACM Symposium on Operating Systems Principles（SOSP’07），2007：256－278.

［2］ Qian Ma，Jing Wang，Gang Wang.A deployment scheme of virtual machines for campus cloud platform［C］∥Proc of the 2014International Conference on Service Sciences，2014：187－192.

［3］ Mylayarapu S，Sukthankar V，Banerjee P.An optimized capacity planning approach for virtual infrastructure exhibiting stochastic workload［C］∥Proc of ACM Symposium on Applied Computing（SAC），2010：386－390.

［4］ Goudarzi H，Pedram M.Energy－efficient virtual machine replication and placement in a cloud computing system［C］∥Proc of 2012IEEE 5th International Conference on Cloud Computing（CLOUD），2012：750－757.

［5］ Chandakanna V－R，Vatsavayi V－K.A model view controller based self－adjusting clustering framework［J］.Journal of Systems and Software，2013，29（4）：581－589.

［6］ Hu J，Gu J，Sun G，et al.A scheduling strategy on load balancing of virtual machine resources in cloud computing environment［C］∥Proc of 2010 3rd International Symposium on Parallel Architectures， Algorithms and Programming（PAAP），2010：89－96.

［7］ Chang Y－C，Chang R－S，Chuang F－W.A predictive method for workload forecasting in the cloud environment［M］∥Advanced Technologies，Embedded and Multimedia for Humancentric Computing. Netherlands：Springer Netherlands，2014：577－585.

［8］ Li X，Jiang Y.A sensory－data－hosting oriented scheduling strategy on virtual machine［C］∥Proc of 2013IEEE and Internet of Things （iThings/CPSCom），IEEE International－Conference on Green Computing and Communications（GreenCom），and IEEE Cybe，Physical and Social Computing，2013：2029－2036.

［9］ Zhao Hong－wei，Shi Bo－le.On capacity planning for E－government cloud computing infrastructure［J］.Computer Applications and Software，2014，31（11）：118－121.（in Chinese）

［10］ Zhao Shao－ka，Li Li－yao，Ling Xiao，et al.Architecture and scheduling scheme design of TsinghuaCloud based on Open－Stack［J］.Journal of Computer Applications，2013，33（12）：3335－3338.（in Chinese）

［11］ Beloglazov A，Buyya R.Energy efficient allocation of virtual machines in cloud data centers［C］∥Proc of the 10th IEEE/ACM International Conference on Cluster，Cloud and Grid Computing（CCGrif’10），2010：577－578.

［12］ Srikantaish S，Kansal A，Zhao F.Energy aware consolidation for cloud computing［C］∥Proc of the 2008Conference on Power Aware Computing and System，2008：10.

附中文參考文獻：

［9］ 趙宏衛，施伯樂.電子政務基礎架構云的容量規劃方法研究［J］.計算機應用與軟件，2014，31（11）：118－121.

［10］ 趙少卡，李立耀，凌曉，等.基于OpenStack的清華云平臺構建與調度方案設計［J］.計算機應用，2013，33（12）：3335－3338.