一種基于M/M/n模型的虛擬機調(diào)度策略

申秋慧，郭麗萍，張文娟

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

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

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

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

1 問題描述

本文基于M/M/n理論，把物理機可容納的虛擬機數(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)絡帶寬，hjr表示hj的剩余可用資源.

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

(1)

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

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

2.1 模型設計

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

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

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

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

2.2 模型分析

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

對于云計算系統(tǒng)來說，任務數(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個虛擬機，當狀態(tài)k>n時，表示待分配的虛擬機數(shù)量超過了系統(tǒng)中物理機所能容納的虛擬機數(shù)量，物理機已達到飽和狀態(tài)，剩余的k-n個虛擬機必須排隊等待. 當云計算系統(tǒng)處于平衡狀態(tài)時，可以得到K氏代數(shù)方程[5]：

(2)

(3)

由此，可得

(4)

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

(5)

由Little公式可知

(6)

根據(jù)上述公式，只要確定了云計算系統(tǒ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)用遷移算法，集中虛擬機，把空閑物理機關閉. 否則，如果找不到一個滿足vi的物理機hj，就計算物理機集合H中所有可用資源的總和Hr，如果Hr>vir，調(diào)用遷移算法，進行虛擬機的遷移，把可用資源集中到一臺物理機上hj，把vi分配給它. 如果遷移失敗，就表示當前物理機已達到飽和，此時，需調(diào)用分配算法，判斷vi是繼續(xù)等待還是新啟動一臺物理機，然后把vi分配給它. 算法偽代碼如表1所示.

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

3.2 子調(diào)度算法

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

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

4 實驗與性能分析

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

4.1 實驗配置

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

表2 虛擬機類型及配置

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

4.2 結(jié)果分析

在實驗中，假設初始有20臺物理機處于開機狀態(tài)，可估算出n=178，取λ=250[7]，即虛擬機到達間隔是0.004 s，取服務強度ρ=0.85. 活躍物理機數(shù)量如圖3所示，活躍物理機數(shù)量與虛擬機規(guī)模存在正比關系，虛擬機數(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算法在任務完成率方面高于RR算法、MOGA算法、BGT算法和BCSF算法，如圖5所示.原因是M/M/n算法在調(diào)度虛擬機時不僅考慮了待分配物理機的數(shù)量，還考慮了虛擬機允許的最大等待時間，若不滿足最大等待時間立即開啟新的物理機以滿足虛擬機的調(diào)度. 而對于整個云計算系統(tǒng)還考慮了物理機空閑的情況，根據(jù)Nw動態(tài)檢測系統(tǒng)負載，若負載輕，立即運行遷移算法，騰出輕載物理機并關閉，以降低系統(tǒng)能耗.

圖5 任務完成率比較

5 結(jié)論

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

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