薛茹

(西北大學(xué) 現(xiàn)代學(xué)院，西安 710130)

0 引言

云計(jì)算是一種將計(jì)算作為服務(wù)提供給消費(fèi)者的一種新服務(wù)方式，其主要功能包括基于互聯(lián)網(wǎng)共享的資源、軟件和信息[1]。云計(jì)算的主要優(yōu)點(diǎn)是降低云計(jì)算用戶和服務(wù)提供商的資本支出。云計(jì)算的應(yīng)用領(lǐng)域包括網(wǎng)站托管、社交網(wǎng)絡(luò)、科學(xué)工作、電子商務(wù)、客戶服務(wù)和高性能計(jì)算等多種場景。基于虛擬化技術(shù)和現(xiàn)代網(wǎng)絡(luò)技術(shù)，云計(jì)算可以向用戶提供各種動態(tài)資源服務(wù)。虛擬化技術(shù)就是指使多個操作系統(tǒng)和應(yīng)用程序可以在一個真實(shí)主機(jī)上同時運(yùn)行的技術(shù)，多個虛擬機(jī)共享主機(jī)的計(jì)算資源，從而充分地優(yōu)化和利用主機(jī)系統(tǒng)的資源。作為虛擬化技術(shù)的一種重要形式，虛擬機(jī)(Virtual Machine, VM)是指利用軟件模擬具備真實(shí)硬件系統(tǒng)功能的、運(yùn)行在隔離環(huán)境中的計(jì)算機(jī)系統(tǒng)。由此可知，云計(jì)算與虛擬機(jī)之間是相互促進(jìn)，密不可分的。云計(jì)算環(huán)境的數(shù)據(jù)中心基于高速網(wǎng)絡(luò)互聯(lián)的計(jì)算機(jī)集群組成，非常適合大量、多樣化任務(wù)的計(jì)算。

文獻(xiàn)[2]提出了一種考慮輸入輸出特性的虛擬機(jī)預(yù)測調(diào)度策略，不僅大大降低了計(jì)算復(fù)雜度，而且提高了調(diào)度精度。文獻(xiàn)[3]在詳細(xì)分析云計(jì)算管理過程中的資源使用問題的基礎(chǔ)上，提出一種考慮虛擬機(jī)資源使用情況的調(diào)度方法，從而大大降低了因資源過度使用而導(dǎo)致的調(diào)度性能變差的問題。文獻(xiàn)[4]在已有的考慮內(nèi)存資源的虛擬機(jī)調(diào)度策略的基礎(chǔ)上，提出一種基于閑置內(nèi)存理論和內(nèi)存使用與交換的新型調(diào)度方法，實(shí)驗(yàn)結(jié)果證明了該方法可以在有效利用計(jì)算資源的前提下，實(shí)現(xiàn)高效率的工作調(diào)度。文獻(xiàn)[5]針對峰值負(fù)荷時期的虛擬機(jī)調(diào)度問題，提出了一種基于網(wǎng)絡(luò)感知的調(diào)度策略，大幅度提高了系統(tǒng)的動態(tài)性能。文獻(xiàn)[6]提出一種基于二次指數(shù)平滑預(yù)測和資源最佳適配技術(shù)的虛擬機(jī)調(diào)度方法，實(shí)驗(yàn)結(jié)果表明該調(diào)度方法可以有效降低能耗，提高調(diào)度的準(zhǔn)確率。文獻(xiàn)[7]提出了一種基于K均值聚類和蝙蝠算法的云計(jì)算虛擬機(jī)調(diào)度算法，提高了調(diào)度的收斂速度和精度。文獻(xiàn)[8]在分析虛擬機(jī)請求的網(wǎng)絡(luò)延遲基礎(chǔ)上，基于運(yùn)籌學(xué)優(yōu)先制M/M/1排隊(duì)模型，解決了針對虛擬機(jī)輸出的不同數(shù)據(jù)的優(yōu)先級問題。文獻(xiàn)[9]設(shè)計(jì)了一種HACC新型分析結(jié)構(gòu)，并在此基礎(chǔ)上提出了一種宇宙學(xué)N-body代碼，利用現(xiàn)場協(xié)同調(diào)度算法實(shí)現(xiàn)了PB級規(guī)模輸出的高效率調(diào)度。文獻(xiàn)[10]針對無線數(shù)據(jù)云中的工作流調(diào)度問題，提出了具備松散數(shù)據(jù)傳輸約束的長時間尺度工作流分割方法，以及基于循環(huán)規(guī)則的短時間尺度工作流通信資源調(diào)度方法，實(shí)驗(yàn)結(jié)果表明了所提算法的優(yōu)越性。文獻(xiàn)[11]提出了一中大規(guī)模云計(jì)算中資源調(diào)度技術(shù)的性能分析技術(shù)，系統(tǒng)地分析了工作流調(diào)度在執(zhí)行功率控制路由協(xié)議過程中的性能指標(biāo)。文獻(xiàn)[12]提出了異構(gòu)計(jì)算系統(tǒng)中基于啟發(fā)式學(xué)習(xí)的工作流調(diào)度方法，顯著加快了調(diào)度工作流的完成時間，并改進(jìn)了計(jì)算資源的供應(yīng)與分配。文獻(xiàn)[13]提出了一種新型的基于靜態(tài)啟發(fā)式算法的數(shù)據(jù)主機(jī)預(yù)訂工作流調(diào)度策略，通過預(yù)測數(shù)據(jù)存儲服務(wù)器的可用性來提高數(shù)據(jù)主機(jī)應(yīng)對網(wǎng)絡(luò)延時的效率，并基于數(shù)據(jù)定位對虛擬機(jī)進(jìn)行了精準(zhǔn)的選擇與執(zhí)行。實(shí)驗(yàn)結(jié)果表明提出的算法在效率、精度等方面明顯優(yōu)于其他啟發(fā)式算法。

然而，由上述分析可知，現(xiàn)階段針對云計(jì)算環(huán)境下考慮截止時間的虛擬機(jī)調(diào)度方法的研究很少。因此，本文提出考慮云計(jì)算截止時間感知的調(diào)度方法，在減少平均等待時間和平均周轉(zhuǎn)時間的同時，最大限度地減少等待時間和響應(yīng)時間，從而實(shí)現(xiàn)提高調(diào)度效率的目的。

1 基于截止時間感知的VM調(diào)度算法

在云計(jì)算中，一項(xiàng)工作的順利完成需要借助云中的計(jì)算資源來實(shí)現(xiàn)，而云中的計(jì)算資源是以虛擬機(jī)的形式提供的，基本工作過程為：調(diào)度程序接受調(diào)度作業(yè)(或工作)請求，并為每個作業(yè)分配所需的云資源(即虛擬機(jī))。

提出的基于截止期限感知的調(diào)度策略中，調(diào)度程序從不同的用戶處接受作業(yè)請求，并將虛擬機(jī)作為資源分配給不同的請求，每個作業(yè)需要兩個不同類型的虛擬機(jī)來共同完成任務(wù)。

1.1 算法原理

在介紹提出的算法之前，首先給出用到的符號定義：r1,r2,…,rn代表云計(jì)算中的一組作業(yè)請求，其中n是作業(yè)請求數(shù)，r是作業(yè)請求，ri是第i個作業(yè)請求；完成ri需要使用第一類虛擬機(jī)(VM1)的作業(yè)時間是ti1，需要使用第二類虛擬機(jī)(VM2)的作業(yè)時間為ti2；dwi代表ri等待時間的截止期限；dri代表ri響應(yīng)時間的截止期限；si代表ri在VM1上的開始時間，ci代表ri在VM2上的完成時間；平均等待時間、平均周轉(zhuǎn)時間、等待/響應(yīng)時間延時等作為評估調(diào)度方法的指標(biāo)。

提出的算法工作原理具體為：首先，利用解向量SV存儲作業(yè)請求的調(diào)度序列；其次在所有未處理作業(yè)中依次識別具有最短的ti1和ti2的作業(yè)請求ri，如果最短時間為ti1，則將ri添加到SV的前端(在調(diào)度的最開始被處理以最小化調(diào)度中所有作業(yè)的等待時間)，否則(即最短時間為ti2)將ri添加到SV的尾端。

ri的等待時間是指在VM1上開始工作之前的等待時間，以及VM1完成到等待VM2工作開始的等待時間之和。

假定每個虛擬機(jī)類型都具有p個實(shí)例用于完成調(diào)度作業(yè)，則調(diào)度序列的解向量SV={r1,r2, …,rn}可以分解為p個子序列：

S1={ri/(imodp)=1}

S2={ri/(imodp)=2}

?

Sp={ri/(imodp)=0}

其中：1≤i≤n，每個子序列Si將依次在VM1、VM2上處理。

基于截止期限感知的調(diào)度策略的輸入包括n個作業(yè)請求，處理時間ti1、ti2，截止時間dwi、dri，輸出為調(diào)度隊(duì)列S1,S2,…,Sp，其偽代碼如下所示。

1)開始

2)初始化i=n，j=n+1，SV=NULL；

3)對于未處理作業(yè)中具有最短時間的作業(yè)請求ri， 如果ti1

4)結(jié)束

5)當(dāng)n

6)結(jié)束

7)當(dāng)n+1

8)結(jié)束

9)計(jì)算整個調(diào)度策略的性能評估指標(biāo)

10)結(jié)束

1.2 算法性能評估指標(biāo)

為了比較不同算法的性能，定義了一下評估指標(biāo)。請求ri的等待時間wi與完成時間ci和總處理時間ti1+ti2相關(guān)，如式(1)。

(1)

所有工作請求的平均等待時間taw和平均周轉(zhuǎn)時間tat定義為式(2)、(3)。

(2)

(3)

2 實(shí)驗(yàn)分析

為了驗(yàn)證所提算法的優(yōu)越性，開發(fā)了一種可自行設(shè)置的模擬環(huán)境，運(yùn)行在CPU為Cortex 5、內(nèi)存4G的計(jì)算機(jī)上，用于在具有p個實(shí)例的虛擬機(jī)上對文獻(xiàn)[14]、文獻(xiàn)[15]以及本文提出的調(diào)度策略進(jìn)行性能評估與對比分析。虛擬機(jī)上作業(yè)請求的處理時間滿足高斯分布。首先，使用文獻(xiàn)[14]調(diào)度算法將作業(yè)隊(duì)列按照先后順序分解為p個子隊(duì)列，p根據(jù)給定的虛擬機(jī)實(shí)例的數(shù)量確定。其次，對于所有工作請求以遞增的順序進(jìn)行排序，并將調(diào)度隊(duì)列分解為自調(diào)度隊(duì)列。再次，對于給定的實(shí)例，應(yīng)用文獻(xiàn)[15]的調(diào)度算法。最后，利用本文提出的調(diào)度算法生成最優(yōu)調(diào)度序列，并將調(diào)度序列分解為p個調(diào)度子序列。通過計(jì)算上述調(diào)度策略的性能評估指標(biāo)，對各種算法的優(yōu)劣進(jìn)行分析。

選取8個作業(yè)請求，將它們應(yīng)用于兩種類型的虛擬機(jī)上，每種類型的虛擬機(jī)均具有兩個實(shí)例，每個實(shí)例上每個任務(wù)的等待時間ti1和ti2，而等待時間截止期限dwi和響應(yīng)時間截止期限dri隨機(jī)產(chǎn)生，如表1所示。

表1 n=8時的調(diào)度實(shí)例

在給定實(shí)例上使用文獻(xiàn)[14]的調(diào)度策略進(jìn)行調(diào)度并計(jì)算的評估指標(biāo)結(jié)果，如表2所示。

通過該調(diào)度算法得到的調(diào)度子序列為：

S1={1,3}

S2={2,5}

S3={0,7}

S4={4,6}

在上述調(diào)度策略中，有2項(xiàng)作業(yè)違反了等待時間截止期限，包括{1,7}；有2項(xiàng)作業(yè)違反了響應(yīng)時間截止期限，包括{0,3}。

表2 文獻(xiàn)[14]的調(diào)度策略在n=8，p=2時的性能指標(biāo)

在給定實(shí)例上應(yīng)用文獻(xiàn)[15]的調(diào)度策略進(jìn)行調(diào)度并計(jì)算得到的評估度量結(jié)果，如表3所示。

表3 文獻(xiàn)[15]的調(diào)度策略在n=8，p=2時的性能指標(biāo)

通過該調(diào)度算法得到的調(diào)度子序列分別為：

S1={0,1}

S2={4,7}

S3={3,6}

S4={2,5}

在該調(diào)度策略中，有1項(xiàng)作業(yè)違反了等待時間截止期限，包括{3} ；有3項(xiàng)作業(yè)違反了響應(yīng)時間截止期限，包括{1,4,6} 。

在給定實(shí)例上使用提出的調(diào)度策略進(jìn)行調(diào)度并計(jì)算的評估度量結(jié)果，如表4所示。

表4 本文的調(diào)度策略在n=8，p=2時的性能指標(biāo)

通過該調(diào)度算法得到的調(diào)度子序列為：

S1={6,7}

S2={3,5}

S3={0,4}

S4={1,2}

在上述調(diào)度策略中，有2項(xiàng)作業(yè)違反了等待時間截止期限，包括{4,7} ；有1項(xiàng)作業(yè)違反了響應(yīng)時間截止期限，包括{6}。

文獻(xiàn)[14]、文獻(xiàn)[15]以及本文提出的調(diào)度策略的總體性能評估指標(biāo)，包括均等待時間、平均周轉(zhuǎn)時間等，如表5所示。

表5 3種調(diào)度策略在n=8，p=2時的性能指標(biāo)比較

此外，對于提到的3種調(diào)度策略，也確定了違反等待時間截止期要求vw和違反響應(yīng)時間截止期要求vs的工作數(shù)量。

在n=8，p=2時，與文獻(xiàn)[14]、[15]中的調(diào)度策略相比，提出的調(diào)度策略在平均等待時間這一性能指標(biāo)上分別減少了45.2%和37.8%；在平均周轉(zhuǎn)時間一性能指標(biāo)上，分別減少了26.5%和18.4%。圖形化的方式給出了3種調(diào)度策略的taw、tat的比較分析結(jié)果，如圖1所示。

圖1 3種調(diào)度策略在n=8，p=2時的taw和tat

在n=8，p=2時，提出的調(diào)度策略的等待時間截止期限違反vw的數(shù)量僅為3，而文獻(xiàn)[14]、[15]中的調(diào)度策略的等待時間截止期違反的數(shù)量分別為9和7。類似的，在響應(yīng)時間截止期違反vr的數(shù)量上，提出的調(diào)度策略的為2，而文獻(xiàn)[14]、[15]分別為8和5。3種調(diào)度策略的vw和vr的比較結(jié)果，如圖2所示。

圖2 3種調(diào)度策略在n=8，p=時的vw和vr

3種調(diào)度策略的調(diào)度精度或準(zhǔn)確性的比較結(jié)果分析，文獻(xiàn)[14]、[15]及本文的調(diào)度策略的調(diào)度精度分別為89.4%、82.3%和95.6%，如圖3所示。

由以上分析可知，與文獻(xiàn)[14]、[15]中的兩種典型調(diào)度策略相比，本文提出的方法具有非常高的工作效率，且調(diào)度的準(zhǔn)確性非常高，可以很好地解決云計(jì)算中虛擬機(jī)的高效、精準(zhǔn)調(diào)度，為分布式計(jì)算的快速發(fā)展和規(guī)?；瘧?yīng)用奠定了堅(jiān)實(shí)的基礎(chǔ)。

圖3 3種調(diào)度策略在n=8，p=2時的調(diào)度精度

3 總結(jié)

針對虛擬機(jī)調(diào)度問題，提出一種基于截止期限感知的虛擬機(jī)項(xiàng)目作業(yè)調(diào)度算法，并在定義性能指標(biāo)的基礎(chǔ)上，通過實(shí)驗(yàn)對比分析了另外兩種調(diào)度策略在平均等待時間、平均周轉(zhuǎn)時間、等待時間截止期違反、響應(yīng)時間截止期違反、調(diào)度精度等的優(yōu)劣。實(shí)驗(yàn)結(jié)果表明提出的調(diào)度策略可以大幅度提高云計(jì)算中虛擬機(jī)的調(diào)度速度和精度，提高計(jì)算資源的利用率。