基于模糊聚類的云任務(wù)調(diào)度算法

李文娟，張啟飛，平玲娣，潘雪增

（1. 浙江大學(xué) 計算機(jī)學(xué)院，浙江 杭州 310018；2. 杭州師范大學(xué) 錢江學(xué)院，浙江 杭州 310012）

1 引言

云計算（cloud computing）是在網(wǎng)格計算、并行計算、P2P和虛擬化等技術(shù)基礎(chǔ)上發(fā)展起來的一種新型的共享信息基礎(chǔ)設(shè)施的模式，也是未來提供網(wǎng)絡(luò)服務(wù)的重要形式[1～3]。云計算的宗旨是為企業(yè)和其他終端用戶提供廉價按需服務(wù)，因而特別強(qiáng)調(diào)QoS。而任務(wù)調(diào)度模型的優(yōu)劣直接影響云服務(wù)質(zhì)量，毋庸置疑是云計算研究的重要組成部分[4～6]。云計算研究目前仍處于初級階段，有關(guān)云調(diào)度的算法還非常稀少，但傳統(tǒng)的其他并行分布式系統(tǒng)中的調(diào)度模型[7,8]有很多。其中以最小化作業(yè)完成時間為目標(biāo)的元任務(wù)調(diào)度算法有OLB、貪心（greedy）算法、最大最小（max-min）、最小最?。╩in-Min）、Sufferage算法[9～12]等以及基于人工智能的調(diào)度算法（遺傳算法、蟻群算法）[13,14]等。上述算法將任務(wù)與資源綁定時，更多的是考慮如何縮短任務(wù)執(zhí)行時間，但云計算的目標(biāo)是提供按需服務(wù)，這樣無法反映用戶真實的QoS要求。另外，傳統(tǒng)的任務(wù)調(diào)度算法在選擇資源時，其針對的對象是全體服務(wù)資源，未考慮資源本身的特性和用戶或任務(wù)的偏好，導(dǎo)致資源選擇的開銷大且存在盲目性。因此找到一種合適的方法對資源進(jìn)行一定程度的劃分能夠縮小資源選擇范圍，從而降低任務(wù)調(diào)度開銷。聚類方法是對目標(biāo)進(jìn)行分類的有效手段。聚類的主要方法有：譜系聚類法、基于等價關(guān)系的聚類方法、圖論聚類法和基于目標(biāo)函數(shù)的聚類方法等[15～17]。資源模糊聚類[18～20]的研究集中于最近幾年，比如杜曉麗等人提出的網(wǎng)格DAG任務(wù)圖調(diào)度算法[18]、陳志剛等提出的網(wǎng)格服務(wù)資源多維性能聚類任務(wù)調(diào)度[19]等，為資源聚類和任務(wù)調(diào)度提供了有益的參考。但之前的聚類調(diào)度算法大多只考慮計算任務(wù)，并且僅對資源進(jìn)行綜合性能優(yōu)劣的劃分，主要目標(biāo)是減少總執(zhí)行時間，沒有考慮資源的其他屬性也沒有考慮任務(wù)的期望。

為更好地體現(xiàn)云計算“廉價按需”服務(wù)的宗旨，反映資源公平公正分配的原則，在對云提供商的資源按性能進(jìn)行模糊聚類的基礎(chǔ)上，采用兩級調(diào)度模式，按照任務(wù)的期望進(jìn)行按需公平調(diào)度，本文提出了一種云環(huán)境下基于模糊聚類的兩級任務(wù)調(diào)度（FCTLBS, fuzzy clustering and two level based task scheduling）算法。理論與實驗分析表明，該算法在提高云系統(tǒng)整體效率和實現(xiàn)調(diào)度公平上具備一定的優(yōu)越性。

本文的創(chuàng)新之處在于：1) 用模糊聚類方法對云資源進(jìn)行劃分，在實際分配時減少了資源搜索的空間，降低了算法復(fù)雜度，同時更能充分有效發(fā)揮對應(yīng)資源的優(yōu)勢；2) 提出任務(wù)偏好的計算方法，能夠更好分析任務(wù)的實際需求；3) 提出一種模糊聚類基礎(chǔ)上的兩級任務(wù)調(diào)度算法，依據(jù)資源聚類結(jié)果及任務(wù)偏好，最大限度體現(xiàn)調(diào)度公平性。同時對用戶實施整體調(diào)度，對任務(wù)實施微觀調(diào)度，有助于減小問題規(guī)模，并為未來在調(diào)度中加入安全及其他機(jī)制奠定基礎(chǔ)。

2 調(diào)度模型

2.1 用戶模型

用戶是指請求云服務(wù)、提交云任務(wù)的實體。使用U={u0,u1,u2,…,uk-1}表示用戶集合，k=|U|代表用戶數(shù)。其中第i個用戶ui(i∈[0，k-1])又可以進(jìn)一步表示為ui={uID,uName,uUAid,uTaskSet}，各屬性的含義如下。

1) uID表示用戶編號，用戶編號在云系統(tǒng)中是唯一的。

2) uName表示用戶名稱。

3) uUAid表示用戶代理的編號。

4) uTaskSet表示用戶提交的任務(wù)集。

2.2 任務(wù)模型

云計算植根于并行系統(tǒng)之上，云任務(wù)可以由有向無環(huán)圖（DAG）：G=（T，E）來表示。其中，T={t0,t1,t2,…,tn-1}表示任務(wù)集，n=|T|代表任務(wù)數(shù)；E表示任務(wù)間執(zhí)行先序關(guān)系的邊集。第i個任務(wù)ti(i∈[0，n-1])又可以進(jìn)一步刻畫為ti={tID, tLength, tStatus,tRRes, tORSet, tDeadLine, tData}，各屬性的含義如下。

1) tID表示任務(wù)編號，任務(wù)編號對于同一用戶的任務(wù)而言是唯一的。

2) tLength表示任務(wù)的長度，用于判斷任務(wù)的計算量。

3) tStatus表示任務(wù)狀態(tài)，任務(wù)可能的狀態(tài)包括創(chuàng)建（CREATED）、就緒（READY）、執(zhí)行（INEXEC）、完成（FINISH）、等待（WAITING）、撤銷（CANCELED）、掛起（PAUSED）、喚醒（RESUMED）和失?。‵ALSE）。任務(wù)剛創(chuàng)建時被賦予 CREATED狀態(tài)；當(dāng)執(zhí)行條件滿足時轉(zhuǎn)為READY狀態(tài)；獲得處理機(jī)執(zhí)行時進(jìn)入INEXEC狀態(tài)；因等待資源或其他協(xié)作任務(wù)完成轉(zhuǎn)為WAITING狀態(tài)；若從內(nèi)存中調(diào)出的任務(wù)為PAUSED狀態(tài)，相應(yīng)地調(diào)入內(nèi)存狀態(tài)為RESUMED；任務(wù)執(zhí)行完畢轉(zhuǎn)為FINISH狀態(tài)；若任務(wù)請求的資源在本系統(tǒng)中無法達(dá)成或缺乏執(zhí)行可能則成為FALSE狀態(tài)。

4) tRRes表示任務(wù)的資源需求。資源需求tRRes又可以進(jìn)一步刻畫為tRRes={tComp,tBW,tStor}，其中tComp、tBW、tStor分別表示任務(wù)對資源計算能力、通信能力和存儲能力的需求。

5) tORSet表示任務(wù)已分配的資源集合。

6) tDeadLine表示任務(wù)的最晚完成時間，用于輔助評判調(diào)度策略的成功與否。

7) tData表示處理任務(wù)所需要的相關(guān)數(shù)據(jù)，包括tInputData和 tOutputData。

2.3 資源模型

R={r0,r1,r2,…,rm-1}表示云系統(tǒng)中的資源集合。m=|R|代表資源數(shù)。其中，第 j個資源 rj(j∈[0，m-1])又可以進(jìn)一步刻畫為rj={rID, rUser, rCap}，各屬性的含義如下。

1) rID表示資源編號。

2) rUser表示資源隸屬的云提供商。

3) rCap表示資源的性能。本文使用3維向量來刻畫資源的性能，包括計算能力、網(wǎng)絡(luò)傳輸能力、存儲能力。

因此，資源性能rCap又可以進(jìn)一步刻畫為rCap={rComp, rBW, rStor}，rComp、rBW、rStor分別表示資源的計算能力、通信能力和存儲能力。

定義1 資源綜合性能rGP：由資源的各項性能需求綜合計算得出，計算公式如下：

其中，參數(shù)α、β、δ分別表示計算、帶寬和存儲能力的經(jīng)驗系數(shù)。

定義2 資源相似度ijPDTr ：表示資源i與資源j綜合性能的相似度，由資源之間綜合性能的距離計算得出，公式如下：

定義 3 聚類資源綜合性能 crGP：某一類型資源聚類的綜合性能均值，公式如下：

其中，參數(shù)n表示類內(nèi)資源數(shù)。

2.4 資源模糊聚類

模糊C均值聚類方法（FCM）是Bezdek 提出用來對數(shù)據(jù)進(jìn)行模糊聚類的方法[21]。給定數(shù)據(jù)集X={x1,x2,…,xn}，F(xiàn)CM 算法的目標(biāo)是找到該數(shù)據(jù)集的一個模糊劃分聚類Uc×n，即劃分原數(shù)據(jù)為c個模糊組，并使得每組樣本與其組聚類中心的非相似性指標(biāo)達(dá)到最小。聚類目標(biāo)函數(shù)的一般定義如下：

其中，uij表示數(shù)據(jù)j隸屬于模糊組i的隸屬度，其值介于 0，1之間；而ci是模糊組 i的聚類中心，dij=||ci-xj||為第i個聚類中心與第j個數(shù)據(jù)點間的歐氏距離；m∈[1,∞）是一個加權(quán)指數(shù)。

本文使用 FCM 方式將資源按照性能模糊劃分為3個類別。聚類的主要步驟如下。

1) 以系統(tǒng)中資源性能向量 rCap建立初始化樣本矩陣。

2) 對原始數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理，將數(shù)據(jù)壓縮到[0,1]之間。

3) 將資源隨機(jī)分為4個類別，初始化模糊劃分矩陣U。

4) 計算聚類中心 ci，i∈{1,2,3}。

5) 計算類內(nèi)各節(jié)點與聚類中心的目標(biāo)函數(shù)值。若小于某個確定的閾值，或它相對上次目標(biāo)函數(shù)值的改變量小于某個閾值，則算法停止。

6) 計算新的劃分矩陣U。返回步驟4）。

以包含8個資源節(jié)點的云系統(tǒng)為例，假定初始狀態(tài)下資源的各種性能指標(biāo)如表1所示。

表1 資源性能參數(shù)

原始數(shù)據(jù)及經(jīng)標(biāo)準(zhǔn)化處理后的資源性能數(shù)據(jù)如圖1所示。

圖1 資源性能數(shù)據(jù)

經(jīng)過設(shè)定閾值和若干次迭代運算，最終將8個資源劃分為3個聚類，分別為Cluster0= {r1,r4,r8}，Cluster1={r3,r6}，Cluster2={r2,r5,r7}。其中Cluster0標(biāo)識為計算型資源集，Cluster1標(biāo)識為帶寬型資源集，而Cluster2標(biāo)識為存儲型資源集。

2.5 任務(wù)偏好系數(shù)

定義4 任務(wù)綜合資源期望tGR：由任務(wù)對資源的各項性能需求綜合計算得出，公式如下：

其中，參數(shù)a、b、c分別表示計算、帶寬和存儲能力的經(jīng)驗系數(shù)。

定義5 任務(wù)偏好系數(shù)tRC：經(jīng)過量化的任務(wù)對資源性能的敏感度。對應(yīng)于資源的3種類別，本文中將任務(wù)區(qū)分為計算敏感型、帶寬敏感型和存儲敏感型。

任務(wù)偏好系數(shù)的計算：任務(wù)綜合資源期望 tGR與各種類型的資源之間綜合性能的最短距離。

其中，cGPjr表示第j類資源聚類的綜合性能。

3 FCTLBS調(diào)度算法

在資源按性能模糊聚類的基礎(chǔ)上，設(shè)計了基于兩級調(diào)度模型的調(diào)度算法。算法將云調(diào)度分為兩級：用戶調(diào)度和任務(wù)調(diào)度。用戶調(diào)度是指以云用戶為單位的調(diào)度。用戶調(diào)度模塊根據(jù)用戶的整體需求和當(dāng)前云市場中各提供商的情況，實現(xiàn)用戶與若干提供商及資源集的綁定。任務(wù)調(diào)度實現(xiàn)同一用戶內(nèi)部任務(wù)與用戶所獲得的虛擬資源的綁定。用戶調(diào)度的層面高于任務(wù)調(diào)度。

3.1 實施框圖

新的調(diào)度模型在開放云系統(tǒng)中設(shè)立云信息服務(wù)中心（CISC, cloud information service center）以及云用戶中心（CUC, cloud user center）。以各提供商的單云平臺為依據(jù)劃分服務(wù)域，域代理由提供商設(shè)立，域代理代表提供商實施域管理策略，包括資源模糊聚類算法的實施，資源任務(wù)的綁定等。用戶首次登錄時向 CUC注冊，而后每次登錄時，依據(jù)注冊賬號向 CUC提交本次登錄的各項需求，包括服務(wù)類型、資源需求、時間期限和費用約束等。云提供商（通過域代理）向CISC注冊。CISC與CUC可以交互。因而用戶可以獲取提供商列表，云提供商也可以向用戶發(fā)布資源廣告。

在模型實施過程中，首先實現(xiàn)以云用戶為單位的整體調(diào)度，根據(jù)用戶的整體需求為其選擇云服務(wù)商或其組合。當(dāng)用戶與特定的幾個提供商綁定之后，將獲得提供商分配的若干虛擬資源以完成用戶任務(wù)。在任務(wù)調(diào)度中，事先將云提供商的資源模糊劃分為3個類別：計算型、帶寬型和存儲型。當(dāng)任務(wù)提交時計算任務(wù)的偏好系數(shù)，根據(jù)任務(wù)偏好在合適的資源聚類中為其選擇資源。模型的具體實施過程如圖2所示。

圖2 FCTLBS算法實施

3.2 FCTLBS算法流程

以各云提供商的單云平臺為域進(jìn)行資源模糊聚類。云資源模糊聚類的算法如下。

RCluster(resourceList rlist){

設(shè)定停止閾值ε和最大迭代次數(shù)MaxTimes；迭代次數(shù)i=0；

根據(jù)輸入的資源列表中資源性能為原始數(shù)據(jù)初始化并進(jìn)行數(shù)據(jù)標(biāo)準(zhǔn)化處理

將資源隨機(jī)分入3個類別，生成初始化劃分矩陣U0；

計算初始聚類中心；

計算Jvalue0

更新聚類中心

計算新的目標(biāo)函數(shù)值Jvalue;i

用戶調(diào)度的算法如下。

CUserS(userList ulist, providerList plist){ //用戶調(diào)度實現(xiàn)用戶與提供商的綁定

While(ulist.iterator().hasNext()){ //需要分配資源的用戶列表非空

CloudUser cuser = (CloudUser) iter.next(); //取出列表中的一個用戶

//用戶登錄云系統(tǒng)時出示要求的服務(wù)類型和各項需求，據(jù)此計算用戶的整體資源需求

requiredResource=cuser. computeRequireCapability ();

List＜CloudProvider＞ chosenPList=new Array-List＜ CloudProvider ＞(); //創(chuàng)建選中的提供商列表

/* findProvider函數(shù)將根據(jù)該用戶的服務(wù)類型、自身的等級、安全級別以及本次運行的資源需求，在現(xiàn)有的提供商列表中尋找最合適的提供商或組合來為該用戶服務(wù)。*/

NodifyProvider(chosenPList，cuser); //通知云提供商需要服務(wù)的用戶

NodifyUser(cuser,chosenPList); //通知云用戶為其分配的提供商列表

在資源模糊聚類的基礎(chǔ)上，任務(wù)調(diào)度算法如下。

FCTLBS(taskList tlist, resourceList rlist){ //任務(wù)調(diào)度實現(xiàn)任務(wù)與資源的綁定

RCluster(rlist); //實現(xiàn)某一云提供商資源的模糊聚類，生成計算型、帶寬型和存儲型資源聚類

Sort(comrlist); //對計算型資源聚類按照類內(nèi)資源性能降序排列

Sort(bwrlist); //對帶寬型資源聚類按照類內(nèi)資源性能降序排列

Sort(storrlist); //對存儲型資源聚類按照類內(nèi)資源性能降序排列

crGP1=ComputClusterGP(comrlist); //按照式(3)計算計算型資源聚類的綜合性能crGP1

crGP2=ComputClusterGP(bwrlist); //按照式(3)計算帶寬型資源聚類的綜合性能crGP2

crGP3=ComputClusterGP(storrlist); //按照式(3)計算存儲型資源聚類的綜合性能crGP3

While(tasklist.iterator().hasNext()){ //任務(wù)列表非空

CloudTask cloudt= (CloudTask)iter.next(); //取出任務(wù)集中的一個任務(wù)

/* ComputeTRC函數(shù)根據(jù)任務(wù)的各項資源需求按照式(5)計算任務(wù)綜合資源期望 tGR，并根據(jù)式(6)確定任務(wù)的資源偏好*/

//根據(jù)任務(wù)類型從虛擬機(jī)列表中尋找合適的虛擬機(jī)

3.3 算法性能分析

在云系統(tǒng)中，某一云用戶在一次登錄時的完成時間取決于該用戶所申請執(zhí)行的云任務(wù)集的最終完成時間，即完成時間最遲的任務(wù)的完成時間。使用uCTi表示用戶i的完成時間， tCTj表示任務(wù)j的完成時間，則 uCTi可以表示為

對于云任務(wù)而言，其預(yù)期完成時間取決于任務(wù)的執(zhí)行時間、通信時間和存儲時間。任務(wù)j的通信時間如下：

其中，tORSetj表示任務(wù)j已分配的資源集合，tDatajk表示任務(wù)j使用資源k傳輸?shù)臄?shù)據(jù)量，相應(yīng)地，tInputDatajk和tOutputDatajk表示通過k輸入及輸出的數(shù)據(jù)量。rBWk表示資源k的網(wǎng)絡(luò)傳輸能力。

任務(wù)j的處理時間為

其中，tLengthjk表示任務(wù)j在資源k上的計算量，rCompk表示資源k的計算能力。

其中，tSDjk表示任務(wù)j在資源k上的存儲量，rStork表示資源k的存儲能力。因此任務(wù)的預(yù)期完成時間為

云系統(tǒng)的吞吐量取決于單位時間內(nèi)系統(tǒng)服務(wù)的云用戶總量，縮短各用戶完成時間可以達(dá)到此目標(biāo)。用戶完成時間取決于該用戶隸屬的用戶任務(wù)集的完成時間?？s短任務(wù)完成時間應(yīng)從縮短任務(wù)的計算、傳輸和存儲時間入手。本文將資源分為計算型、帶寬型和存儲型3類，同時將任務(wù)也按照其對資源需求的特點歸為對應(yīng)的計算偏好型、帶寬偏好型和存儲偏好型3個類別，從而使得對資源某種能力要求高、需求量大的任務(wù)獲得在此能力上性能較好的資源，更好地體現(xiàn)了按需分配的原則，也從一般意義上縮短了任務(wù)的完成時間。

RCluster算法在最壞情況下的時間復(fù)雜度為o(m×MaxTimes)，m表示某一云提供商擁有的資源數(shù)，MaxTimes為最大迭代次數(shù)。用戶調(diào)度程序CUserS在最壞情況下的時間復(fù)雜度為o(n×k)，其中n表示云用戶數(shù)，k表示云提供商數(shù)。任務(wù)調(diào)度程序FCTLBS是在RCluster基礎(chǔ)上對任務(wù)與資源進(jìn)行綁定，因此其在最壞情況下的時間復(fù)雜度為o(x×m×MaxTimes)，其中x表示任務(wù)數(shù)，m與MaxTimes的含義同前。

4 實驗設(shè)計與分析

云系統(tǒng)中的任務(wù)調(diào)度算法目前還比較稀少，在已有的分布式元任務(wù)調(diào)度算法中，Min-Min是很多其他調(diào)度模型的基礎(chǔ)，另外，考慮到本調(diào)度算法的目標(biāo)之一是實現(xiàn)資源的按需分配，也可以說是實踐資源分配的公平性原則，而趙春燕等人提出的基于伯格模型的云任務(wù)調(diào)度算法[22]其宗旨即分配公平，因此本文將FCTLBS與Min-Min及基于伯格模型的任務(wù)調(diào)度算法相比較，以獲得相對客觀的評價。

4.1 實驗設(shè)計

實驗?zāi)M包含2個云提供商和若干云用戶構(gòu)成的云計算環(huán)境。以提供商的單云平臺作為劃分域的依據(jù)，由提供商設(shè)立域代理節(jié)點，域代理是代表提供商管理域資源和進(jìn)行云交易的主體。仿真系統(tǒng)由任務(wù)生成器、資源發(fā)生器、云交互環(huán)境、用戶調(diào)度器和任務(wù)調(diào)度器幾部分構(gòu)成。任務(wù)生成器按照輸入的任務(wù)數(shù)、任務(wù)各項參數(shù)基值和對應(yīng)的任務(wù)差異度隨機(jī)生成任務(wù)，并部署任務(wù)參數(shù)。資源發(fā)生器則按照要求的資源數(shù)目、資源性能基數(shù)以及資源差異度隨機(jī)產(chǎn)生資源節(jié)點，并部署資源性能。云交互環(huán)境主要實現(xiàn)仿真云環(huán)境中不同實體的交互和消息傳遞。交互系統(tǒng)中包含3.1節(jié)提到的云信息服務(wù)中心CISC和云用戶中心CUC。提供商（通過域代理）向CISC注冊、獲取用戶信息，用戶向CUC注冊并間接獲取提供商的信息。用戶調(diào)度器是實現(xiàn)用戶與提供商綁定的程序，而任務(wù)調(diào)度器是實現(xiàn)用戶任務(wù)集中的任務(wù)與用戶已經(jīng)獲得的資源綁定的程序。仿真系統(tǒng)模擬50～1 500個任務(wù)在5～200個資源節(jié)點上的執(zhí)行情況。通過任務(wù)生成器的控制，任務(wù)的長度控制在[tLength,Ldif×tLength]之間的值，任務(wù)的計算需求控制在[tComp,Cdif×tComp]之間，帶寬需求量控制在[tBW, Tdif×tBW]，存儲需求控制在[tStor,Sdif×tStor]之間。同理，通過資源發(fā)生器的控制，將資源的計算能力控制在[rComp,Cdifr×rComp]之間，將資源的網(wǎng)絡(luò)能力控制在[rBW,Tdifr×rBW]之間，將資源的計算能力控制在[rStor,Sdifr×rStor]之間。其中，tLength表示任務(wù)長度，Ldif表示任務(wù)長度差異度。tComp表示任務(wù)計算量，Cdif表示任務(wù)計算量差異度。tBW表示任務(wù)帶寬需求，Tdif表示任務(wù)帶寬需求差異度。tStor表示任務(wù)存儲需求量，Sdif表示任務(wù)存儲需求差異度。資源的各項指標(biāo)類似。

4.2 評價指標(biāo)

調(diào)度的目標(biāo)是實現(xiàn)資源任務(wù)的合理匹配，從而一方面提高系統(tǒng)的整體工作效率，另一方面提高系統(tǒng)使用者的滿意度。為了判斷新的調(diào)度算法在實踐調(diào)度目標(biāo)上的性能，仿真實驗主要設(shè)置了2個評價指標(biāo)：一是任務(wù)集的最終完成時間，用來評價系統(tǒng)的吞吐量；二是用戶滿意度，用于評價資源分配和調(diào)度的合理性。本文中用戶滿意度是根據(jù)任務(wù)的實際占有資源水平與期望占有水平的相比較計算得出的。

單個任務(wù)的滿意度 tJvaluei的計算方法如下所示：

其中，tORSet如前所述表示任務(wù)實際分配得到的資源集合，ρ、ω、τ分別表示計算、帶寬和存儲資源需求的經(jīng)驗系數(shù)。由式（12）可以很容易推導(dǎo)出任務(wù)集的整體滿意度，即用戶滿意度 uJvalue的計算方法如下所示：

其中，uTaskSet表示歸屬于該用戶的任務(wù)集，n表示任務(wù)的個數(shù)。

4.3 實驗結(jié)果分析

由于基于伯格模型的任務(wù)調(diào)度算法開銷很大，當(dāng)任務(wù)數(shù)增加時，其執(zhí)行時間呈急速上升趨勢，因而對于任務(wù)完成時間的比較分兩次進(jìn)行。任務(wù)數(shù)較少時，比較3種調(diào)度算法的性能；任務(wù)數(shù)較多時，比較FCTLBS和Min-Min的性能。比較結(jié)果如圖3和圖4所示。

圖3 任務(wù)數(shù)較少時，3種算法完成時間比較

圖4 任務(wù)數(shù)較多時，2種算法完成時間比較

相應(yīng)地，對用戶滿意度的比較也分成兩次進(jìn)行，比較結(jié)果如圖5和圖6所示。

圖5 任務(wù)數(shù)較少時，3種算法滿意度比較

圖6 任務(wù)數(shù)較多時，2種算法滿意度比較

從仿真實驗結(jié)果可以看出，當(dāng)問題規(guī)模較?。ū疚闹?～120個任務(wù)）時，F(xiàn)CTLBS與Min-Min調(diào)度模型的時間效率相當(dāng)，優(yōu)于伯格模型，在用戶滿意度上 FCTLBS與伯格模型相當(dāng)，優(yōu)于Min-Min；當(dāng)問題規(guī)模較大（本文中大于 150個任務(wù)）時，F(xiàn)CTLBS在完成時間和用戶滿意度上均較優(yōu)。Min-Min調(diào)度算法的主要思想是不斷尋找并優(yōu)先調(diào)度任務(wù)集中在所有資源上擁有最小完成時間最小的任務(wù)，因而執(zhí)行速度較快，但由于其總是優(yōu)先調(diào)度短任務(wù)，無法保證整體用戶滿意度。伯格模型將歐氏距離最短的任務(wù)資源進(jìn)行匹配，以期達(dá)到用戶期待分配資源與實際分配資源的最大一致性，整體用戶滿意度較高，但無法保證系統(tǒng)吞吐量，且實現(xiàn)全體任務(wù)與全體資源的匹配計算開銷大，在實際系統(tǒng)中實現(xiàn)困難。FCTLBS算法采取兩級調(diào)度模式，以提供商的單云平臺為單位實施資源聚類算法，降低了問題的規(guī)模。同時在資源綜合性能聚類的基礎(chǔ)上，按照任務(wù)的資源需求進(jìn)行資源和任務(wù)的綁定，更好地體現(xiàn)了按需分配的原則，也從整體上縮短了任務(wù)集的完成時間。由此可見，F(xiàn)CTLBS算法具備更好的性能和可操作性。

5 結(jié)束語

本文提出了一種云計算環(huán)境中使用的任務(wù)調(diào)度算法。該算法將調(diào)度分為用戶調(diào)度和任務(wù)調(diào)度兩級。以用戶為單位進(jìn)行的整體調(diào)度，可以更好地發(fā)揮用戶的自主資源選擇權(quán)，反映不同用戶的需求，也有利于后續(xù)安全措施的引入。任務(wù)調(diào)度中，采用模糊聚類的方法對不同提供商的資源按照其綜合性能進(jìn)行聚類，并計算任務(wù)資源偏好，以任務(wù)的偏好為依據(jù)在對應(yīng)資源聚類中進(jìn)行選擇。聚類任務(wù)調(diào)度算法降低了資源選擇的空間，也保證了分配的公平合理性。最后，通過實驗與分析可知，新的調(diào)度算法在確保系統(tǒng)整體吞吐量的同時保證了較高的用戶滿意度。

[1] 劉鵬. 云計算[M]. 北京：電子工業(yè)出版社, 2010.LIU P. Cloud Computing[M]. Beijing: Electronic Industry Press, 2010.

[2] FOSTER I, KESSELMAN C. The Grid: Blueprint for a New Computing Infrastructure[M]. Morgan Kaufmann, San Francisco,1999.

[3] FOSTER I, ZHAO Y, IOAN R, et al. Cloud computing and grid computing 360-degree compared[A]. Grid Computing Environments Workshop, 2008. GCE '08 (2008)[C]. 2008.1-10.

[4] 王鵬. 云計算的關(guān)鍵技術(shù)與應(yīng)用實例[M]. 北京：人民郵電出版社,2010.WANG P. The Key Technologies of Cloud Computing and Its Application [M]. Beijing: Posts & Telecom Press, 2010.

[5] 中國云計算論壇[EB/OL]. http://bbs.chinacloud.cn.Chinese cloud forum[EB/OL]. http://bbs.chinacloud.cn.

[6] MLADEN A, VOU K. Cloud computing-issues research and implementations[A]. Proceedings of the ITI 2008, 30th Int Conf on Information Technology Interfaces[C].2008.31-40.

[7] 朱福喜，何炎祥. 并行分布式計算中的調(diào)度算法理論與設(shè)計[M].武漢：武漢大學(xué)出版社, 2003.ZHU F X, HE Y X. Parallel Scheduling Algorithm in Distributed Computing Theory and Design[M]. Wuhan: Wuhan University Press,2003.

[8] CRREA R C．Scheduling multiprocessor tasks with genetic algorithms[J]. IEEE Transactions on Parallel and Distributed Systems,1999,10(8):825-837．

[9] FREUND R, GHENITY M, AMBROSIUS S, et al．Scheduling resources in multi-user heterogeneous computing environments with SmartNet[A]. Proceedings of the 7th IEEE Heterogeneous Computing Workshop[C]. Orlando, Florida, USA,1998.184-199．

[10] HOU E S H, ANSARI N，REN H. A genetic algorithm for multiprocessor scheduling[J]. IEEE Trans on Parallel and Distributed Systems,1994,5(2):113-120．

[11] IBARRA O H, KIM C E. Heuristic algorithms for scheduling independent tasks on non identical processors[J]．Journal of ACM，l997,24(2):280-289.

[12] TRACY D B, HOWARD J S, NOAH B. A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems[J]. Journal of Parallel and Distributed Computing,2001,61(6):810-837.

[13] HOLLAND J H. Adaptation in Natural and Artificial Systems[M].Michigan, USA: Ann Arbor University of Michigan Press,1975.228-234.

[14] GAMBARDELLA L M, DORIGO M. Solving symmetric and asymmetric TSPs by ant colonies[A]. Proceedings of the IEEE Conference on Evolutionary Computation[C]. 1996.622-627.

[15] 曲紹云.分布式異構(gòu)系統(tǒng)中任務(wù)調(diào)度問題的研究[D]. 青島:青島大學(xué), 2005.QU S Y. Research on Task Scheduling Problems in Distributed and Heterogeneous Systems[D]. Qindao: Qindao University, 2005.

[16] 高新波.模糊聚類分析及其應(yīng)用[M]. 西安: 西安電子科技大學(xué)出版社, 2004.GAO X B. Fuzzy Clustering Analysis and Applications[M]. Xi’an:Xi’an Electronic and Technology University Press,2004.

[17] 嚴(yán)駿,姚敏.模糊聚類算法應(yīng)用研究[D].杭州:浙江大學(xué),2006.YAN J, YAO M. Research on the Applications of Fuzzy Clustering Algorithms[D]. Hangzhou: Zhejiang University, 2006.

[18] 杜曉麗, 蔣昌俊, 徐國榮等. 一種基于模糊聚類的網(wǎng)格 DAG 任務(wù)圖調(diào)度算法[J].軟件學(xué)報,2006, 17(11): 2277-2288.DU X L, JIANG C J, XU G R, et al. A grid DAG scheduling algorithm based on fuzzy clustering[J]. Journal of Software, 2006, 17(11): 2277-2288.

[19] 陳志剛,楊博.網(wǎng)格服務(wù)資源多維性能聚類任務(wù)調(diào)度[J]. 軟件學(xué)報,2009,20(10):2766-2774.CHEN Z G, YANG B. Task scheduling based on multidimensional performance clustering of grid service resources[J]. Journal of Software, 2009,20(10):2766-2774.

[20] 任大娟,張忠平.基于模糊聚類的網(wǎng)格資源發(fā)現(xiàn)方法研究[D]. 秦皇島：燕山大學(xué),2009.REN D J, ZHANG Z P. Research on Grid Resource Discovery Based on Fuzzy Clustering[D]. Qinhuangdao: Yanshan University,2009.

[21] BEZDEK J C. Pattern Recognition with Fuzzy Objective Function Algorithms[M]. New York: Plenum Press, 1981.10-18.

[22] 趙春燕. 云環(huán)境下作業(yè)調(diào)度算法研究與實現(xiàn)[D]. 北京:北京交通大學(xué), 2009.ZHAO C Y. Research and Realization of Job Scheduling Algorithm in Cloud Environment[D]. Beijing: Beijing Jiaotong University, 2009.