申秋慧，郭麗萍，張文娟

(周口師范學(xué)院 計算機科學(xué)與技術(shù)學(xué)院 ，河南 周口 466000)

云計算的核心技術(shù)是如何合理地將虛擬機調(diào)度到物理機上，調(diào)度算法的優(yōu)劣直接影響云計算系統(tǒng)的性能及收益.目前國內(nèi)外的研究成果中，采用的方法可總結(jié)為兩類：簡單調(diào)度策略和基于啟發(fā)式算法的全局尋優(yōu)策略.

簡單的調(diào)度策略易于實現(xiàn)，比如Amazon EC2采用的以負載均衡為目標(biāo)的輪轉(zhuǎn)調(diào)度(RR)[1]，HP采用的以公平分配為目標(biāo)的先來先服務(wù)(FIFS)策略[2]，但執(zhí)行效率較低. 基于啟發(fā)式算法的調(diào)度策略只從單方面考慮，或者考慮的只是單個方面的多個目標(biāo)而已，比如基于博弈論的算法，能保證負載均衡，但算法復(fù)雜，無法充分保證用戶服務(wù)質(zhì)量(QoS)；基于遺傳算法的策略(MOGA)能保證資源充分利用，但忽略了資源過載對任務(wù)執(zhí)行效率的影響[3]；基于內(nèi)存感知的服務(wù)器整合算法(BCSF)以節(jié)能為目的，但物理機性能會因負載不均衡而降低[4].

為了解決上述問題，本文基于M/M/n理論建模云計算系統(tǒng)并提出了一種虛擬機調(diào)度策略，不僅能動態(tài)分配虛擬機以滿足用戶對資源的需求，還能進行虛擬機的遷移達到負載均衡，關(guān)閉空閑的物理機降低能耗.

1 問題描述

本文基于M/M/n理論，把物理機可容納的虛擬機數(shù)量比作服務(wù)窗口，把待分配的虛擬機比作隊列中等待服務(wù)的客戶. 設(shè)云數(shù)據(jù)中心有x個物理主機，物理主機的集合是H={h1，h2，…，hx}，對于任一物理主機hj，用每秒百萬指令數(shù)(MIPS)描述他的CPU性能，則hj={cj，rj，wj}，其中cj表示hj的CPU能力，rj表示hj的存儲容量，wj表示hj的網(wǎng)絡(luò)帶寬，hjr表示hj的剩余可用資源.

云數(shù)據(jù)中心根據(jù)類型把任務(wù)分為計算密集型、存儲密集型、傳輸密集型和混合型4類，每個類型又分為大、中、小3種規(guī)模. 為每一類型的不同規(guī)模的任務(wù)創(chuàng)建一個虛擬機，也就是說云計算中心一共需要建立12個不同配置的虛擬機模板.當(dāng)任務(wù)到達時，調(diào)度中心先根據(jù)任務(wù)的類型和規(guī)模參照模板為它初始化一個虛擬機，虛擬機模板集合V={v1，v2，…，v12}，對于每一類虛擬機用vir={c(vi)，r(vi)，n(vi)}表示虛擬機所占資源，其中c(vi)，r(vi)，n(vi)分別表示虛擬機的CPU性能、存儲容量和網(wǎng)絡(luò)帶寬. 用n表示當(dāng)前系統(tǒng)中物理機可容納的最大虛擬機數(shù)量，也就是M/M/n模型中服務(wù)窗口的大小，可取容納最小虛擬機個數(shù)和最大虛擬機個數(shù)的均值，即

(1)

設(shè)到達云數(shù)據(jù)中心的任務(wù)ti是相互獨立的，服從λ的泊松分布，即與任務(wù)匹配的虛擬機的創(chuàng)建間隔也服從λ的泊松分布，虛擬機調(diào)度到物理機上后即開始運行，由于任務(wù)的多樣性，物理機對虛擬機的服務(wù)時間st是隨機的，假設(shè)該服務(wù)時間st服從參數(shù)為μ的負指數(shù)分布.

2 基于M/M/n的云數(shù)據(jù)中心系統(tǒng)模型

2.1 模型設(shè)計

根據(jù)第1部分的描述可以建立基于M/M/n的云數(shù)據(jù)中心系統(tǒng)模型，如圖1所示.

圖1 基于M/M/n的云數(shù)據(jù)中心系統(tǒng)模型

任務(wù)到達后，由初始化模塊分析任務(wù)的類型和規(guī)模，然后從模板庫中選擇一個合適的模板為任務(wù)初始化一個虛擬機. 所有任務(wù)的虛擬機按照初始化完成的先后順序排成一個全局虛擬機隊列，用Nd表示全局隊列中虛擬機的數(shù)量，用t(vi)表示在能夠滿足用戶QoS的情況下虛擬機vi的最大等待時間，等于虛擬機開始運行的時間減去初始化完成的時間. 如果調(diào)度策略判斷當(dāng)前系統(tǒng)無法在保證服務(wù)質(zhì)量的情況下完成虛擬機調(diào)度，就開啟新的物理機；若判斷到物理機資源空閑較多，則進行虛擬機的遷移，關(guān)閉空閑物理機，以達到節(jié)能的目的.

若任務(wù)運行完成，與之對應(yīng)的虛擬機就被撤銷，對應(yīng)物理機hj被虛擬機vi占用的資源就釋放了，hj可以接納新的虛擬機.

2.2 模型分析

綜上所述，可用λ表示虛擬機的初始化完成速率，μ表示各虛擬機在物理機上運行的服務(wù)速率，所以nμ表示整個系統(tǒng)的平均服務(wù)率. 記ρ1=λ/μ，ρ=λ/(nμ)表示服務(wù)強度，用Pi表示系統(tǒng)中存在第i個需要調(diào)度的虛擬機的定態(tài)概率. 根據(jù)Little公式可知，當(dāng)ρ<1時，整個系統(tǒng)處于穩(wěn)定狀態(tài)，即云計算系統(tǒng)處于負載均衡的穩(wěn)定狀態(tài).

對于云計算系統(tǒng)來說，任務(wù)數(shù)量是無限的，因此需要分配的虛擬機也是無限的，所以整個云計算系統(tǒng)可以看成是一個不斷進行狀態(tài)變換的生滅系統(tǒng)，系統(tǒng)可能的狀態(tài)集可寫為Φ={0,1,2,3,…}，其狀態(tài)流圖如圖2所示.

圖2 基于M/M/n的云數(shù)據(jù)中心狀態(tài)流圖

其中狀態(tài)k(n≥k≥0)表示系統(tǒng)中有k個虛擬機已經(jīng)分配到了物理機上運行，物理機還可以接納n-k個虛擬機，當(dāng)狀態(tài)k>n時，表示待分配的虛擬機數(shù)量超過了系統(tǒng)中物理機所能容納的虛擬機數(shù)量，物理機已達到飽和狀態(tài)，剩余的k-n個虛擬機必須排隊等待. 當(dāng)云計算系統(tǒng)處于平衡狀態(tài)時，可以得到K氏代數(shù)方程[5]：

(2)

(3)

由此，可得

(4)

根據(jù)上述分析，可知

(5)

由Little公式可知

(6)

根據(jù)上述公式，只要確定了云計算系統(tǒng)當(dāng)前開機的物理機的參數(shù)，就能計算出系統(tǒng)處于平穩(wěn)狀態(tài)時的Nw及Tw.

3 虛擬機調(diào)度策略

基于上文所建立云數(shù)據(jù)中心模型，提出了虛擬機調(diào)度策略，該策略包括一個全局調(diào)度算法，M/M/n調(diào)度算法；3個處理不同情況的子算法：檢測算法、遷移算法和分配算法.

3.1 M/M/n調(diào)度算法

首先選取一個排在全局虛擬機隊列隊首的虛擬機vi，然后從物理機集合H中選擇一個可用資源滿足vi的物理機hj，把vi分配給hj，完成虛擬機vi的調(diào)度，然后調(diào)用檢測算法，檢測是否有大量空閑物理機，如果有，調(diào)用遷移算法，集中虛擬機，把空閑物理機關(guān)閉. 否則，如果找不到一個滿足vi的物理機hj，就計算物理機集合H中所有可用資源的總和Hr，如果Hr>vir，調(diào)用遷移算法，進行虛擬機的遷移，把可用資源集中到一臺物理機上hj，把vi分配給它. 如果遷移失敗，就表示當(dāng)前物理機已達到飽和，此時，需調(diào)用分配算法，判斷vi是繼續(xù)等待還是新啟動一臺物理機，然后把vi分配給它. 算法偽代碼如表1所示.

表1 M/M/n算法偽代碼

3.2 子調(diào)度算法

檢測算法的思路是首先假設(shè)關(guān)閉一臺物理機，然后根據(jù)公式(1)計算服務(wù)窗口n，根據(jù)公式(5)計算等待分配的虛擬機的平均個數(shù)Nw.如果當(dāng)前全局隊列中虛擬機的數(shù)量Nd

分配算法的步驟是先計算Nw，再根據(jù)公式(6)計算虛擬機的平均等待時間Tw. 若全局隊列中虛擬機數(shù)量Nd小于平均等待數(shù)量Nw，且vi的允許等待時間t(vi)大于平均等待時間Tw，則vi繼續(xù)等待，下一輪再分配. 否則，為了保證用戶滿意度，開啟新的物理機并把vi分配給它.

4 實驗與性能分析

本文使用CloudSim云仿真平臺運行在真實云環(huán)境中進行實驗. 選擇了來自不同科學(xué)領(lǐng)域的四個真實任務(wù)Montage，LIGO，SIPHT和CyberShake作為實驗輸入[6]. 這四個任務(wù)按大、中、小規(guī)?？蓪?yīng)本文提出的12個虛擬機模板. 用提出的M/M/n調(diào)度算法與RR算法、MOGA算法、BGT算法和BCSF算法在系統(tǒng)能耗、活躍物理機數(shù)量和任務(wù)完成率三個方面進行比較.

4.1 實驗配置

實驗運行在一臺IBM高性能服務(wù)器上，模擬了400臺物理機，物理機的配置是10 000 MIPS的CPU計算能力，2 TB的存儲和10 G的帶寬. 虛擬機類型及配置如表2所示：

表2 虛擬機類型及配置

將工作流分為平均50，200，400，500，600，800，1 000個任務(wù)，每個任務(wù)配置一個虛擬機，也就是說系統(tǒng)中虛擬機的數(shù)量分別是50，200，400，500，600，800，1 000，每種虛擬機數(shù)量運行20次，將20次實驗結(jié)果的平均數(shù)據(jù)作為最終評估數(shù)據(jù).

4.2 結(jié)果分析

在實驗中，假設(shè)初始有20臺物理機處于開機狀態(tài)，可估算出n=178，取λ=250[7]，即虛擬機到達間隔是0.004 s，取服務(wù)強度ρ=0.85. 活躍物理機數(shù)量如圖3所示，活躍物理機數(shù)量與虛擬機規(guī)模存在正比關(guān)系，虛擬機數(shù)量變大，活躍物理機數(shù)量也隨之增加，系統(tǒng)能耗明顯提升，如圖4所示. 在同一數(shù)量的虛擬機請求規(guī)模下，M/M/n算法在活躍物理機數(shù)量上明顯少于RR算法、MOGA算法和BGT算法，相比與這三種算法活躍的物理機數(shù)量分別減少了約14.5%，9.4%，6.5%，但高于以節(jié)能為目的的BCSF算法2.75%.

圖3 活躍物理機數(shù)量比較

圖4 系統(tǒng)能耗比較

M/M/n算法在任務(wù)完成率方面高于RR算法、MOGA算法、BGT算法和BCSF算法，如圖5所示.原因是M/M/n算法在調(diào)度虛擬機時不僅考慮了待分配物理機的數(shù)量，還考慮了虛擬機允許的最大等待時間，若不滿足最大等待時間立即開啟新的物理機以滿足虛擬機的調(diào)度. 而對于整個云計算系統(tǒng)還考慮了物理機空閑的情況，根據(jù)Nw動態(tài)檢測系統(tǒng)負載，若負載輕，立即運行遷移算法，騰出輕載物理機并關(guān)閉，以降低系統(tǒng)能耗.

圖5 任務(wù)完成率比較

5 結(jié)論

本文分析了典型的虛擬機調(diào)度策略及其存在的問題，基于排隊理論對云計算系統(tǒng)進行建模，提出了M/M/n虛擬機調(diào)度策略.該策略不僅考慮了全局虛擬機的分配，還動態(tài)地對物理機的負載情況進行檢測，結(jié)合動態(tài)閾值進行虛擬機的遷移和物理機的開關(guān)機，在保證任務(wù)完成率的情況下，也達到了節(jié)能的目的. 實驗驗證了M/M/n調(diào)度策略的優(yōu)越性，雖然能耗方面略高于以節(jié)能為優(yōu)化目標(biāo)的BCSF算法，但任務(wù)完成率方面M/M/n調(diào)度策略效果最好.

M/M/n調(diào)度策略的關(guān)鍵是動態(tài)計算Nw和Tw，Nw和Tw的計算都用到λ，實驗時λ的取值用的是大多數(shù)研究者在M/M/n排隊理論中的取值. 此未來的工作會研究與任務(wù)類型最匹配的λ取值，讓不同類型的虛擬機使用不同的λ值，對M/M/n調(diào)度策略做進一步地優(yōu)化和驗證.