云計算中基于M/Geom/C/∞排隊系統(tǒng)的任務(wù)調(diào)度模型研究

，，

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

0 引言

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

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

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

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

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

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

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

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

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

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

2.1 排隊系統(tǒng)

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

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

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

(1)

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

2.2 排隊模型描述

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

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

2.2.1 仿真模型組成部分

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

(2)

3)等待服務(wù)時間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)在時刻t排隊系統(tǒng)中恰有n個任務(wù)的概率為Pn(t)，而P0(t)為系統(tǒng)空閑率；

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

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

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

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

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

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

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

5)虛擬機服務(wù)臺壽命為X，服從參數(shù)為α(0≤α<∞)的負(fù)指數(shù)分布。服務(wù)臺失效后立即進(jìn)行修理，其修理時間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á)間隔長為k，則在這k個時隙上必有第r個時隙。該時隙開始時，系統(tǒng)任務(wù)數(shù)大于c；而該時隙結(jié)束時系統(tǒng)有l(wèi)個任務(wù)，j≤l≤c.并且在該時隙上恰好完成了m個服務(wù)，c-l+1≤m≤c.

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

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

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

而且

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

(5)

(6)

(7)

(8)

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

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

(9)

(10)

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

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

(11)

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

(12)

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

(13)

(14)

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

(15)

另外，在服務(wù)臺忙的條件下，討論系統(tǒng)中排隊等待任務(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時，M/Geom/C/∞系統(tǒng)中穩(wěn)態(tài)等待時間W可分解為兩個獨立隨機變量之和：

W=W0+Wd,

(19)

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

(20)

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

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

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

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

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

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

圖2 期望隊長隨服務(wù)率變化的趨勢

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

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

4 結(jié)論

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

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

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

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

[4]游卓浩.基于M/M/n排隊模型的云資源調(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/∞排隊網(wǎng)絡(luò)的Web服務(wù)組合性能分析[J].計算機學(xué)報，2013，36(1)：22-37.

[7]方 歡，陸 陽，黃鎮(zhèn)謹(jǐn)，等.基于CPN仿真的排隊系統(tǒng)建模及性能分析[J] . 系統(tǒng)仿真學(xué)報，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.