利用截止期感知的云計(jì)算數(shù)據(jù)中心虛擬機(jī)調(diào)度方法

薛茹

(西北大學(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ì)算等多種場(chǎng)景。基于虛擬化技術(shù)和現(xiàn)代網(wǎng)絡(luò)技術(shù)，云計(jì)算可以向用戶提供各種動(dòng)態(tài)資源服務(wù)。虛擬化技術(shù)就是指使多個(gè)操作系統(tǒng)和應(yīng)用程序可以在一個(gè)真實(shí)主機(jī)上同時(shí)運(yùn)行的技術(shù)，多個(gè)虛擬機(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ù)測(cè)調(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]針對(duì)峰值負(fù)荷時(shí)期的虛擬機(jī)調(diào)度問題，提出了一種基于網(wǎng)絡(luò)感知的調(diào)度策略，大幅度提高了系統(tǒng)的動(dòng)態(tài)性能。文獻(xiàn)[6]提出一種基于二次指數(shù)平滑預(yù)測(cè)和資源最佳適配技術(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ī)請(qǐng)求的網(wǎng)絡(luò)延遲基礎(chǔ)上，基于運(yùn)籌學(xué)優(yōu)先制M/M/1排隊(duì)模型，解決了針對(duì)虛擬機(jī)輸出的不同數(shù)據(jù)的優(yōu)先級(jí)問題。文獻(xiàn)[9]設(shè)計(jì)了一種HACC新型分析結(jié)構(gòu)，并在此基礎(chǔ)上提出了一種宇宙學(xué)N-body代碼，利用現(xiàn)場(chǎng)協(xié)同調(diào)度算法實(shí)現(xiàn)了PB級(jí)規(guī)模輸出的高效率調(diào)度。文獻(xiàn)[10]針對(duì)無線數(shù)據(jù)云中的工作流調(diào)度問題，提出了具備松散數(shù)據(jù)傳輸約束的長(zhǎng)時(shí)間尺度工作流分割方法，以及基于循環(huán)規(guī)則的短時(shí)間尺度工作流通信資源調(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)度工作流的完成時(shí)間，并改進(jìn)了計(jì)算資源的供應(yīng)與分配。文獻(xiàn)[13]提出了一種新型的基于靜態(tài)啟發(fā)式算法的數(shù)據(jù)主機(jī)預(yù)訂工作流調(diào)度策略，通過預(yù)測(cè)數(shù)據(jù)存儲(chǔ)服務(wù)器的可用性來提高數(shù)據(jù)主機(jī)應(yīng)對(duì)網(wǎng)絡(luò)延時(shí)的效率，并基于數(shù)據(jù)定位對(duì)虛擬機(jī)進(jìn)行了精準(zhǔn)的選擇與執(zhí)行。實(shí)驗(yàn)結(jié)果表明提出的算法在效率、精度等方面明顯優(yōu)于其他啟發(fā)式算法。

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

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

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

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

1.1 算法原理

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

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

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

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

S1={ri/(imodp)=1}

S2={ri/(imodp)=2}

?

Sp={ri/(imodp)=0}

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

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

1)開始

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

3)對(duì)于未處理作業(yè)中具有最短時(shí)間的作業(yè)請(qǐng)求ri， 如果ti1

4)結(jié)束

5)當(dāng)n

6)結(jié)束

7)當(dāng)n+1

8)結(jié)束

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

10)結(jié)束

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

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

(1)

所有工作請(qǐng)求的平均等待時(shí)間taw和平均周轉(zhuǎn)時(shí)間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個(gè)實(shí)例的虛擬機(jī)上對(duì)文獻(xiàn)[14]、文獻(xiàn)[15]以及本文提出的調(diào)度策略進(jìn)行性能評(píng)估與對(duì)比分析。虛擬機(jī)上作業(yè)請(qǐng)求的處理時(shí)間滿足高斯分布。首先，使用文獻(xiàn)[14]調(diào)度算法將作業(yè)隊(duì)列按照先后順序分解為p個(gè)子隊(duì)列，p根據(jù)給定的虛擬機(jī)實(shí)例的數(shù)量確定。其次，對(duì)于所有工作請(qǐng)求以遞增的順序進(jìn)行排序，并將調(diào)度隊(duì)列分解為自調(diào)度隊(duì)列。再次，對(duì)于給定的實(shí)例，應(yīng)用文獻(xiàn)[15]的調(diào)度算法。最后，利用本文提出的調(diào)度算法生成最優(yōu)調(diào)度序列，并將調(diào)度序列分解為p個(gè)調(diào)度子序列。通過計(jì)算上述調(diào)度策略的性能評(píng)估指標(biāo)，對(duì)各種算法的優(yōu)劣進(jìn)行分析。

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

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

在給定實(shí)例上使用文獻(xiàn)[14]的調(diào)度策略進(jìn)行調(diào)度并計(jì)算的評(píng)估指標(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è)違反了等待時(shí)間截止期限，包括{1,7}；有2項(xiàng)作業(yè)違反了響應(yīng)時(shí)間截止期限，包括{0,3}。

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

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

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

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

S1={0,1}

S2={4,7}

S3={3,6}

S4={2,5}

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

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

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

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

S1={6,7}

S2={3,5}

S3={0,4}

S4={1,2}

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

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

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

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

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

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

在n=8，p=2時(shí)，提出的調(diào)度策略的等待時(shí)間截止期限違反vw的數(shù)量?jī)H為3，而文獻(xiàn)[14]、[15]中的調(diào)度策略的等待時(shí)間截止期違反的數(shù)量分別為9和7。類似的，在響應(yīng)時(shí)間截止期違反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=時(shí)的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時(shí)的調(diào)度精度

3 總結(jié)

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