，，

( 廣東工程職業(yè)技術(shù)學(xué)院 信息工程學(xué)院，廣州 510520)

0 引言

云計(jì)算中任務(wù)調(diào)度主要研究的是如何將合適的虛擬機(jī)調(diào)度分配給用戶提交的任務(wù)使用。用戶提交的任務(wù)被分割成n個(gè)子任務(wù)，形成n個(gè)子任務(wù)的排隊(duì)隊(duì)列，隊(duì)列中的任務(wù)通過調(diào)度器發(fā)送到m個(gè)虛擬機(jī)上執(zhí)行計(jì)算[1]。云任務(wù)調(diào)度就是以實(shí)時(shí)掌握云環(huán)境下虛擬機(jī)的負(fù)載狀態(tài)為前提，根據(jù)云任務(wù)排隊(duì)狀態(tài)將虛擬機(jī)資源進(jìn)行科學(xué)調(diào)度、分配，均衡各虛擬機(jī)的負(fù)載，達(dá)到云任務(wù)執(zhí)行效率最高且成本低的目標(biāo)。具體執(zhí)行過程是：根據(jù)執(zhí)行效率高的虛擬機(jī)與執(zhí)行效率低的虛擬機(jī)之間的負(fù)載狀態(tài)及云任務(wù)排隊(duì)狀態(tài)，均衡排隊(duì)隊(duì)列的隊(duì)長(zhǎng)，優(yōu)先使用執(zhí)行效率高的虛擬機(jī)，目的就是使得那些處于排隊(duì)狀態(tài)的任務(wù)能夠得到最快響應(yīng)并開始執(zhí)行，從而大大縮短任務(wù)執(zhí)行時(shí)間和服務(wù)成本，有效提高任務(wù)執(zhí)行效率。云計(jì)算中的任務(wù)調(diào)度問題已被證明為一類Np-hard問題，傳統(tǒng)調(diào)度算法在有效時(shí)間內(nèi)得到滿意解的效果并不理想，但是，通過對(duì)云任務(wù)調(diào)度問題進(jìn)行建模，分析影響虛擬機(jī)服務(wù)性能的因素，獲取該模型中的任務(wù)等待時(shí)間、系統(tǒng)資源利用率等性能指標(biāo)來評(píng)估模型的綜合性能。

目前，一些學(xué)者從多方面入手來求解云計(jì)算任務(wù)調(diào)度問題，但是，在云任務(wù)調(diào)度模型分析與研究并不多。參考文獻(xiàn)[2]根據(jù)M/G/1排隊(duì)論，給出了求解云任務(wù)調(diào)度的可靠性的均衡調(diào)度算法。參考文獻(xiàn)[3]提出了一種基于M/M/n/n+r排隊(duì)系統(tǒng)的云計(jì)算中心任務(wù)調(diào)度分析模型，求解該模型的用戶請(qǐng)求響應(yīng)時(shí)間及QoS性能指標(biāo)，參考文獻(xiàn)[4]確定了基于M/M/n排隊(duì)模型的云計(jì)算資源調(diào)度模型，以降低任務(wù)服務(wù)時(shí)間和能耗為調(diào)度目標(biāo)。參考文獻(xiàn)[5]給出了一種適用于云計(jì)算服務(wù)的有效QoS約束調(diào)度方案。

不同于已有的研究工作，本文設(shè)計(jì)了一種基于M/Geom/C/∞排隊(duì)系統(tǒng)的云任務(wù)調(diào)度模型，以虛擬機(jī)的服務(wù)可靠性為效用函數(shù)，運(yùn)用排隊(duì)論分析任務(wù)在虛擬機(jī)上執(zhí)行的任務(wù)調(diào)度策略。該調(diào)度策略保證了排隊(duì)隊(duì)長(zhǎng)較短、任務(wù)等待時(shí)間較短、平均響應(yīng)時(shí)間較快，仿真結(jié)果證實(shí)了其有效性。

1 云計(jì)算中的任務(wù)調(diào)度

云計(jì)算任務(wù)調(diào)度描述：

云計(jì)算中任務(wù)調(diào)度的實(shí)質(zhì)是把用戶提交的任務(wù)分解為n個(gè)獨(dú)立的子任務(wù)集合T={t1,t2,…tn}，并通過調(diào)度器將子任務(wù)發(fā)送到m個(gè)虛擬機(jī)vm={vm1,vm2,…vmm}上去執(zhí)行，任務(wù)調(diào)度的目標(biāo)是盡量讓排隊(duì)隊(duì)列中任務(wù)的等待時(shí)間較短、響應(yīng)時(shí)間較快，在虛擬機(jī)上執(zhí)行時(shí)間相對(duì)較短。具體描述如下：

定義1：云任務(wù)調(diào)度系統(tǒng)中有k個(gè)用戶，其中Ui(1≤i≤k)為第i個(gè)用戶提交的任務(wù)，用戶Ui提交任務(wù)的平均速率λi服從負(fù)指數(shù)分布。

定義2：對(duì)用戶提交的任務(wù)進(jìn)行分割，獲得n個(gè)待調(diào)度的云任務(wù)隊(duì)列T={t1,t2,…tn}，其中ti(1≤i≤n)為第i個(gè)子任務(wù)，這n個(gè)子任務(wù)被調(diào)度器分配到虛擬機(jī)上執(zhí)行，子任務(wù)ti并行發(fā)送，每個(gè)子任務(wù)只能分配到一個(gè)虛擬機(jī)上執(zhí)行。

定義3：VM={vm1,vm2,…vmm}是云環(huán)境中m個(gè)虛擬機(jī)的集合，其中m

2 基于M/Geom/C/∞排隊(duì)系統(tǒng)的云任務(wù)調(diào)度算法

2.1 排隊(duì)系統(tǒng)

排隊(duì)問題可以描述為服務(wù)與被服務(wù)的關(guān)系，由輸入過程、排隊(duì)規(guī)則和服務(wù)規(guī)則這3個(gè)部分組成。輸入過程是指任務(wù)到達(dá)排隊(duì)系統(tǒng)的過程，考察的是任務(wù)到達(dá)排隊(duì)系統(tǒng)的規(guī)律?？梢杂靡欢〞r(shí)間內(nèi)任務(wù)到達(dá)數(shù)的概率分布或前后兩個(gè)任務(wù)相繼到達(dá)的間隔時(shí)間等來描述。排隊(duì)規(guī)則則可采用最常見的先到者先服務(wù)模式。服務(wù)機(jī)構(gòu)就是指排隊(duì)系統(tǒng)中多個(gè)虛擬機(jī)。

L={L-c|L≥c,J=1},

W={W|L≥c,J=1}

(1)

其中:L是期望隊(duì)長(zhǎng)，系統(tǒng)中排隊(duì)等待的任務(wù)數(shù)。W是在服務(wù)臺(tái)全忙時(shí)請(qǐng)求服務(wù)的期望等待時(shí)間，根據(jù)上述性能指標(biāo)確定服務(wù)臺(tái)的平均利用率[6-7]。

2.2 排隊(duì)模型描述

排隊(duì)模型的選擇對(duì)提高云任務(wù)調(diào)度的效率非常關(guān)鍵作用，它還決定了調(diào)度系統(tǒng)對(duì)資源的利用率。所以要根據(jù)目標(biāo)與現(xiàn)狀，加入一定的目標(biāo)約束條件，設(shè)計(jì)一種適合云任務(wù)調(diào)度系統(tǒng)的排隊(duì)模型，提高調(diào)度系統(tǒng)運(yùn)行效能[8-10]。由于排隊(duì)系統(tǒng)的特征，排隊(duì)模型可以有許許多多的組合，本文采用M/Geom/C/∞形式表示云任務(wù)調(diào)度中的排隊(duì)模型。其中：M表示任務(wù)到達(dá)間隔時(shí)間服從負(fù)指數(shù)概率分布，Geom表示服務(wù)時(shí)間服從幾何概率分布，C為虛擬機(jī)臺(tái)數(shù)，∞表示任務(wù)來源總體數(shù)無限。M/Geom/C/∞排隊(duì)模型屬于等待制排隊(duì)模型，模型如圖1所示。

圖1 云任務(wù)調(diào)度中排隊(duì)系統(tǒng)仿真模型

2.2.1 仿真模型組成部分

1)任務(wù)請(qǐng)求服務(wù)到達(dá)為固定速率λ的負(fù)指數(shù)分布，負(fù)指數(shù)分布用“M”表示，有無記憶性，即Markov性。

(2)

3)等待服務(wù)時(shí)間X服從參數(shù)p幾何分布P{X=k}=(1-p)pk,0

k=0,1,…

(3)

的數(shù)學(xué)期望和概率母函數(shù)分別是：

(4)

2.2.2 模型所使用到的數(shù)量指標(biāo)

3)在時(shí)刻t排隊(duì)系統(tǒng)中恰有n個(gè)任務(wù)的概率為Pn(t)，而P0(t)為系統(tǒng)空閑率；

4)排隊(duì)隊(duì)列中平均任務(wù)數(shù)稱為隊(duì)長(zhǎng)，記作L；

5)排隊(duì)隊(duì)列中等待服務(wù)的平均任務(wù)數(shù)稱為等待隊(duì)長(zhǎng)，記作Lq；

6)任務(wù)從進(jìn)入排隊(duì)隊(duì)列到接受完服務(wù)后離開系統(tǒng)的平均時(shí)間稱為平均逗留時(shí)間，記作W；

7)任務(wù)在系統(tǒng)內(nèi)排隊(duì)等待服務(wù)的平均時(shí)間稱為平均等待時(shí)間，記作Wq。

2.2.3 云任務(wù)調(diào)度流程

1)在M/Geom/C/∞排隊(duì)系統(tǒng)中，任務(wù)到達(dá)間隔服從負(fù)指數(shù)分布，以{Qn,n≥0}表示時(shí)隙分點(diǎn)n處觀察到的隊(duì)長(zhǎng)(隊(duì)列中的任務(wù)數(shù))過程。當(dāng)時(shí)刻n落在某到達(dá)間隔之內(nèi)時(shí)，Qn的值取決于時(shí)刻n處剩余到達(dá)間隔的長(zhǎng)度，剩余到達(dá)間隔分布滿足Markov性質(zhì)；

4)kj是一個(gè)到達(dá)間隔內(nèi)恰好完成j個(gè)任務(wù)的概率，{kj,j≥0}是一個(gè)概率分布，νj是到達(dá)間隔大于休假時(shí)間V，并且在休假結(jié)束后的剩余到達(dá)間隔內(nèi)恰好完成j個(gè)任務(wù)的概率；

5)虛擬機(jī)服務(wù)臺(tái)壽命為X，服從參數(shù)為α(0≤α<∞)的負(fù)指數(shù)分布。服務(wù)臺(tái)失效后立即進(jìn)行修理，其修理時(shí)間Y是任意分布。

2.3 模型分析

2.3.1 嵌入馬爾可夫鏈

2.3.2 系統(tǒng)平衡條件和系統(tǒng)轉(zhuǎn)移率陣

下面分兩種情況，導(dǎo)出MC的轉(zhuǎn)移概率：

1) 0≤i

2)i≥c,j≤c.到達(dá)間隔長(zhǎng)為k，則在這k個(gè)時(shí)隙上必有第r個(gè)時(shí)隙。該時(shí)隙開始時(shí)，系統(tǒng)任務(wù)數(shù)大于c；而該時(shí)隙結(jié)束時(shí)系統(tǒng)有l(wèi)個(gè)任務(wù)，j≤l≤c.并且在該時(shí)隙上恰好完成了m個(gè)服務(wù)，c-l+1≤m≤c.

注意到轉(zhuǎn)移概率的時(shí)齊性，嵌入馬爾可夫鏈的初始概率分布為平穩(wěn)分布，因此該排隊(duì)系統(tǒng)為平穩(wěn)分布。

2.3.3 系統(tǒng)穩(wěn)態(tài)分布

下面應(yīng)用矩陣幾何技術(shù)來討論該模型的平穩(wěn)結(jié)果。

而且

1) 當(dāng)θ≠μ(1-δ)時(shí)，有

(5)

(6)

(7)

(8)

在系統(tǒng)達(dá)到統(tǒng)計(jì)平衡下(ρ<1)，任務(wù)到達(dá)時(shí)看到隊(duì)長(zhǎng)的平均數(shù)為

1)當(dāng)θ≠μ(1-δ)時(shí)，有

(9)

(10)

2.3.4 條件隨機(jī)分解結(jié)果

對(duì)于一個(gè)多虛擬機(jī)服務(wù)臺(tái)排隊(duì)系統(tǒng)，只有當(dāng)所有服務(wù)臺(tái)全忙時(shí)，才能充分地反映出這個(gè)系統(tǒng)的本質(zhì)特征。對(duì)應(yīng)的無休假經(jīng)典M/M/C排隊(duì)系統(tǒng)中，同名條件隨機(jī)變量記為L(zhǎng)0和W0,它們的PGF分別是

(11)

當(dāng)ρ<1時(shí)，M/Geom/C/∞排隊(duì)中(L-,J)的分布是

(12)

1) 當(dāng)ρ<1時(shí)，M/Geom/C/∞排隊(duì)中到達(dá)前夕的穩(wěn)態(tài)隊(duì)長(zhǎng)L-可分解成兩個(gè)獨(dú)立隨機(jī)變量之和：

(13)

(14)

由穩(wěn)態(tài)隊(duì)長(zhǎng)的隨機(jī)分解結(jié)構(gòu)，容易得出下列平均隊(duì)長(zhǎng)公式：

(15)

另外，在服務(wù)臺(tái)忙的條件下，討論系統(tǒng)中排隊(duì)等待任務(wù)數(shù)的分布。設(shè)：

Q(1)={L--1|j=1}

(16)

由常數(shù)σ的定義，有：

(17)

根據(jù)定理可得出：

P{Q(1)=j}=P{L-=j+1|J=1}=

(18)

(2) 當(dāng)ρ<1時(shí)，M/Geom/C/∞系統(tǒng)中穩(wěn)態(tài)等待時(shí)間W可分解為兩個(gè)獨(dú)立隨機(jī)變量之和：

W=W0+Wd,

(19)

其中:W0是對(duì)應(yīng)經(jīng)典無休假系統(tǒng)中的等待時(shí)間，其分布由穩(wěn)態(tài)等待時(shí)間給出；附加延遲與休假時(shí)間V同分布，有PGF:

(20)

3 算法仿真與結(jié)果分析

本節(jié)通過Matlab編程繪圖，以圖表的形式展示基于M/Geom/C/∞排隊(duì)系統(tǒng)的云任務(wù)調(diào)度模型的一些穩(wěn)態(tài)概率變化曲線圖。

假定參數(shù)設(shè)置如下：到達(dá)率0.7個(gè)/分，服務(wù)率(0.03，0.5)個(gè)/分，平均服務(wù)時(shí)間0.6分/個(gè)，期望服務(wù)水平80%。

結(jié)合數(shù)值例子，表1給出了期望隊(duì)長(zhǎng)和期望等待時(shí)間隨著服務(wù)率變化的數(shù)據(jù)，從表中也可以看出仿真系統(tǒng)的服務(wù)臺(tái)平均利用率較高。

表1 系統(tǒng)的穩(wěn)態(tài)指標(biāo)仿真值

圖2和圖3分別給出了排隊(duì)系統(tǒng)的期望隊(duì)長(zhǎng)、期望等待時(shí)間隨著服務(wù)率變化的理論值與仿真值。

圖2 期望隊(duì)長(zhǎng)隨服務(wù)率變化的趨勢(shì)

圖3 等待時(shí)間隨服務(wù)率變化的趨勢(shì)

從圖2和圖3可以看出，隨著服務(wù)率的增大，隊(duì)長(zhǎng)和等待時(shí)間均減小。并且從圖中可以看出排隊(duì)系統(tǒng)期望隊(duì)長(zhǎng)、期望等待時(shí)間的理論值與仿真值比較接近，驗(yàn)證了本文中云任務(wù)調(diào)度模型的有效性、合理性。

4 結(jié)論

本文將排隊(duì)論相關(guān)知識(shí)應(yīng)用于云環(huán)境下的任務(wù)調(diào)度模型分析與研究中，提出了一個(gè)基于M/Geom/C/∞排隊(duì)系統(tǒng)的云任務(wù)調(diào)度模型。結(jié)合排隊(duì)論工具對(duì)云任務(wù)調(diào)度過程的分析，利用嵌入馬爾可夫鏈理論方法研究任務(wù)調(diào)度排隊(duì)系統(tǒng)，尋找到既可以縮短調(diào)度過程中任務(wù)排隊(duì)等待的時(shí)間，又能提高系統(tǒng)虛擬機(jī)資源利用率的調(diào)度方案。仿真實(shí)驗(yàn)得到了該模型的平穩(wěn)分布及相關(guān)性能指標(biāo)，驗(yàn)證了其有效性。

[1]胡德敏、戶 靜、余 星.云計(jì)算環(huán)境下基于微粒群的虛擬機(jī)任務(wù)調(diào)度算法[J].計(jì)算機(jī)測(cè)量與控制，2014，22(4)：1189-1192.

[2]王 勇，等.云環(huán)境下基于可靠性的均衡任務(wù)調(diào)度算法研究[J].計(jì)算機(jī)科學(xué)，2015，42(6A)：325-330.

[3]何懷文，等. 基于M/M/n/n+r排隊(duì)模型的云計(jì)算中心服務(wù)性能分析[J].計(jì)算機(jī)應(yīng)用，2014，34(7)：1843-1847.

[4]游卓浩.基于M/M/n排隊(duì)模型的云資源調(diào)度策略研究[D] .成都：電子科技大學(xué)，2014，6.

[5]Lee Liangteh, Liu Kangyuan, Chiang Mingjen. An Effective QoS-Constrained Scheduling Scheme for Cloud Computing Services[J] . Journal of Electronic Science and Technology，2013，11(2)：161-168.

[6]汪 浩，黃明和，龍 浩.基于G/G/1-FCFS、M/G/1-PS和M/G/∞排隊(duì)網(wǎng)絡(luò)的Web服務(wù)組合性能分析[J].計(jì)算機(jī)學(xué)報(bào)，2013，36(1)：22-37.

[7]方 歡，陸 陽，黃鎮(zhèn)謹(jǐn)，等.基于CPN仿真的排隊(duì)系統(tǒng)建模及性能分析[J] . 系統(tǒng)仿真學(xué)報(bào)，2013，25(2)：228-234.

[8]Pandey S,Nepal S. Cloud computing and scientific application: Big data, scalable analytics, and beyond[J].Future Generation Computer Systems,2013,29(7):1774-1776.

[9]Zhang Qi, Cheng Lu, Boutaba Raouf. Cloud computing:state-of-the-art and research challenges[J].Internet Serv Appl,2010,6(1):7-18.

[10]Gu J, Hu J, Zhao T, et at. A new resource scheduling strategy based on genetic algorithm in cloud computing environment[J]. Journal of Computers, 2012, 7(1): 42-52.