基于QoS分類的任務(wù)調(diào)度算法研究

趙科偉，洪 龍，周寧寧

(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210000)

基于QoS分類的任務(wù)調(diào)度算法研究

趙科偉，洪 龍，周寧寧

(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210000)

為了提高云服務(wù)供應(yīng)商提供服務(wù)的質(zhì)量和用戶對(duì)云服務(wù)的滿意度，文中提出了一種基于QoS分類的任務(wù)調(diào)度算法。該算法針對(duì)的是獨(dú)立任務(wù)的調(diào)度，也就是任務(wù)之間沒有依賴關(guān)系，因此該方法可以利用模糊聚類算法對(duì)任務(wù)集進(jìn)行分類，然后采用傳統(tǒng)的分段Min-Min算法進(jìn)行任務(wù)的分配。分段Min-Min算法相比Min-Min算法是以更小粒度來分配資源，因此能提高任務(wù)和資源之間的匹配程度，在此基礎(chǔ)上針對(duì)某些節(jié)點(diǎn)負(fù)載過重的情況采取優(yōu)化方法，這樣能進(jìn)一步降低完成時(shí)間，同時(shí)取得了一定程度的負(fù)載均衡。實(shí)驗(yàn)結(jié)果表明，提出的改進(jìn)方法既能滿足用戶的QoS需求，又能取得較短的完成時(shí)間。

云計(jì)算；任務(wù)調(diào)度；Min-Min；模糊聚類；負(fù)載均衡

1 概 述

云計(jì)算是一個(gè)用時(shí)付費(fèi)的模型，用戶根據(jù)這個(gè)模型按需訪問網(wǎng)絡(luò)提供的共享的、可配置的計(jì)算機(jī)資源池(如網(wǎng)絡(luò)、服務(wù)器、存儲(chǔ)、應(yīng)用和服務(wù))[1]。云計(jì)算的承諾是為用戶提供按需服務(wù)，因此特別注重QoS，而任務(wù)調(diào)度策略的優(yōu)劣直接影響著服務(wù)質(zhì)量，毫無疑問這成為研究云計(jì)算的一個(gè)重要組成部分[2-3]。

為了解決任務(wù)到資源節(jié)點(diǎn)的映射問題，國內(nèi)外許多專家學(xué)者做了大量的工作。由于調(diào)度問題是NP完全問題，所以許多啟發(fā)式算法被提出。這些映射啟發(fā)式算法大致分為兩類：最小化任務(wù)完成時(shí)間的算法和人工智能的調(diào)度算法。最小化任務(wù)完成時(shí)間算法主要有最小完成時(shí)間(MCT)算法[4]、最小執(zhí)行時(shí)間(MET)算法、最小最小(Min-Min)算法、最大最小(Max-Min)算法[5]，這些算法都是靜態(tài)的調(diào)度算法。對(duì)Min-Min[6]算法來說，它的主要思想是，假設(shè)云計(jì)算環(huán)境由n個(gè)任務(wù)T={T1,T2,…,Tn}和m個(gè)虛擬機(jī)R={R1,R2,…,Rm}組成，當(dāng)集合T不空時(shí)，一直執(zhí)行如下步驟直到集合T為空：

(1)計(jì)算每個(gè)任務(wù)在每臺(tái)虛擬機(jī)上的完成時(shí)間，找出每個(gè)任務(wù)對(duì)應(yīng)的最小完成時(shí)間，把此最小完成時(shí)間放到一個(gè)數(shù)組completeTime[n]中；

(2)從completeTime[n]中選擇最小的完成時(shí)間對(duì)應(yīng)的任務(wù)Ti(1≤i≤n,其中i為正整數(shù))進(jìn)行調(diào)度；

(3)從集合T中刪除前面已經(jīng)調(diào)度過的任務(wù)；

(4)重復(fù)步驟1～3，直到集合T為空。

可以看出Min-Min算法的不足之處：

(1)忽略了任務(wù)的QoS需求，不能滿足任務(wù)的多樣化需求；

(2)總是優(yōu)先調(diào)度短任務(wù)，而且總是把任務(wù)調(diào)度到運(yùn)行速度最快的虛擬機(jī)上面。

針對(duì)這些缺點(diǎn)，Max-Min算法從最小完成時(shí)間的數(shù)組中選擇最大的完成時(shí)間的任務(wù)進(jìn)行調(diào)度。針對(duì)Min-Min算法容易造成負(fù)載不均衡的問題，Min-Min-Opt算法將負(fù)載重的虛擬機(jī)上的任務(wù)調(diào)度到負(fù)載輕的虛擬機(jī)上來平衡負(fù)載。SegmentedMin-Min[7]首先將每個(gè)任務(wù)在所有虛擬機(jī)上運(yùn)行時(shí)間的平均值作為任務(wù)的關(guān)鍵字，其次將關(guān)鍵字按照降序排列，并且將關(guān)鍵字劃分為N段，最后針對(duì)每一段分別調(diào)用Min-Min算法，能很好地提高算法的運(yùn)行效率。而人工智能調(diào)度算法主要有遺傳算法[8]、蟻群算法[9]、粒子群算法[10]等。

以上這些算法在將任務(wù)與資源進(jìn)行匹配時(shí)，大多考慮的是計(jì)算型任務(wù)，沒有考慮任務(wù)的其他屬性。傳統(tǒng)的聚類算法把每個(gè)對(duì)象嚴(yán)格地劃分到各個(gè)類別當(dāng)中，然而實(shí)際生活中有許多對(duì)象沒有嚴(yán)格的屬性，模糊聚類主要針對(duì)這些對(duì)象進(jìn)行聚類。文中采用的模糊聚類算法是模糊C均值算法[11-12]，根據(jù)任務(wù)對(duì)時(shí)間、帶寬、存儲(chǔ)的需求將任務(wù)分為3類，然后針對(duì)不同任務(wù)采用不同的調(diào)度算法。

2 調(diào)度模型

2.1 任務(wù)模型

用戶指請(qǐng)求云計(jì)算資源的實(shí)體。第i個(gè)用戶ui采用三元組形式表示為(ui-Id,ui-name,ui-task)。其中，ui-Id作為該用戶的唯一標(biāo)識(shí)，ui-name表示用戶的名字，ui-task表示該用戶提交的任務(wù)集合。如此，請(qǐng)求云計(jì)算資源的用戶集合為U={u1,u2,…,un}。設(shè)任務(wù)集合中的任務(wù)是相互獨(dú)立的，則ui-task可以描述為ui-task={ti-1,ti-2,…,ti-m}，ti-j代表第i個(gè)用戶的第j個(gè)子任務(wù)，而ti-j又可表示為(ti-j-length,ti-j-time,ti-j-bw,ti-j-store)。其中，ti-j-length代表第i個(gè)用戶的第j個(gè)子任務(wù)的長度，ti-j-time代表第i個(gè)用戶的第j個(gè)子任務(wù)對(duì)時(shí)間的需求，ti-j-bw代表第i個(gè)用戶的第j個(gè)子任務(wù)對(duì)帶寬的需求，ti-j-store代表第i個(gè)用戶的第j個(gè)子任務(wù)對(duì)存儲(chǔ)的需求。假設(shè)每個(gè)用戶最多有m個(gè)子任務(wù)，然后將所有用戶的所有任務(wù)按順序編號(hào)，因此T={t1,t2,…,tmn}代表需要調(diào)度的所有子任務(wù)的集合。

2.2 資源模型

云系統(tǒng)中的資源由資源池中虛擬機(jī)表示，第j個(gè)vmj采用三元組形式表示為(vmj-Id,vmj-type,vmj-perform)。其中，vmj-Id作為虛擬機(jī)的唯一標(biāo)識(shí)，vmj-type表示虛擬機(jī)的類型，vmj-perform表示虛擬機(jī)的性能。如此，云計(jì)算資源集合為V={vm1,vm2,…,vmk}。虛擬機(jī)的性能又可以采用四元組形式表示為(vmj-perform-comp,vmj-perform-price,vmj-perform-fault,vmj-perform-ram)。其中，vmj-perform-comp表示第j臺(tái)虛擬機(jī)的計(jì)算能力，vmj-perform-price表示第j臺(tái)虛擬機(jī)的價(jià)格，vmj-perform-fault表示第j臺(tái)虛擬機(jī)的故障率，vmj-perform-ram表示第j臺(tái)虛擬機(jī)的內(nèi)存容量。

2.3 任務(wù)分配模型

傳統(tǒng)調(diào)度算法主要包括在線模式調(diào)度算法、批處理模式調(diào)度算法、啟發(fā)式調(diào)度算法。在線模式中，一個(gè)任務(wù)一旦到達(dá)調(diào)度系統(tǒng)就立馬分配虛擬機(jī)。批處理模式中，任務(wù)到達(dá)時(shí)沒有被立即調(diào)度，而是放入一個(gè)預(yù)調(diào)度的集合中，這個(gè)集合中的任務(wù)叫元任務(wù)，這些元任務(wù)將在一個(gè)預(yù)定時(shí)間進(jìn)行統(tǒng)一調(diào)度，在統(tǒng)一調(diào)度之前如何找到一種分配策略來縮短任務(wù)完成的總時(shí)間是調(diào)度問題的關(guān)鍵。因此元任務(wù)的分配由元任務(wù)到虛擬機(jī)的映射表示。例如，圖1就表示元任務(wù)到虛擬機(jī)的一種分配策略。

圖1 元任務(wù)到虛擬機(jī)的放置示意圖

是所有元任務(wù)的集合，V'是所有虛擬機(jī)的集合，E'?T'×V'，E'是T'和V'之間的邊集，一條邊e(t,v)代表元任務(wù)t∈T'被調(diào)度到虛擬機(jī)v∈V'上。分配策略是一個(gè)函數(shù)f:T'→V'，表示分配一個(gè)元任務(wù)t給虛擬機(jī)f(t)，假如對(duì)每一個(gè)元任務(wù)t∈T'，f(t)都有定義，那么這種分配是一種全局分配。在一種全局分配α中，一些虛擬機(jī)分配了一些元任務(wù)，假定元任務(wù)在虛擬機(jī)上是順序執(zhí)行的，因此一臺(tái)虛擬機(jī)的負(fù)載表示這臺(tái)虛擬機(jī)完成上面的所有元任務(wù)的總的時(shí)間。

假設(shè)在初始時(shí)刻三臺(tái)虛擬機(jī)的負(fù)載如表1所示。

表1 虛擬機(jī)初始負(fù)載

各個(gè)元任務(wù)在所分配的虛擬機(jī)上的執(zhí)行時(shí)間如表2所示。

表2 任務(wù)執(zhí)行時(shí)間

3 任務(wù)模糊聚類

模糊C均值聚類(FCM)是由Dumm第一個(gè)提出的，并且由Bezdek將其發(fā)展和推廣。FCM可以描述為最小化指標(biāo)函數(shù)的優(yōu)化迭代算法。設(shè)集合由X={x1,x2,…,xn}是樣本集合，把X分為c類，進(jìn)一步設(shè)定c個(gè)聚類中心的集合V={v1,v2,…,vc}。

FCM的目標(biāo)函數(shù)如下：

(1)

文中使用FCM算法將用戶需求模糊劃分為3個(gè)類別，主要步驟如下：

(1)以任務(wù)的需求向量t建立初始化樣本矩陣。

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

(3)對(duì)模糊偽劃分矩陣U進(jìn)行初始化。

(4)計(jì)算簇質(zhì)心，并更新模糊偽劃分。

(5)如果聚類的目標(biāo)函數(shù)收斂，則算法停止。否則，返回步驟(4)。

由于文中是根據(jù)任務(wù)對(duì)時(shí)間需求、帶寬需求、存儲(chǔ)需求來建模的，經(jīng)過模糊C均值聚類之后，得到每個(gè)任務(wù)屬于時(shí)間型任務(wù)、帶寬型任務(wù)、存儲(chǔ)型任務(wù)的百分比，再根據(jù)一定的閾值將任務(wù)分配到三種類型的任務(wù)集合Sj中。表3表示任務(wù)根據(jù)模糊C均值聚類得到的每個(gè)任務(wù)相對(duì)應(yīng)于各個(gè)類別的隸屬程度，選取其中的5個(gè)任務(wù)，其中類別1代表時(shí)間型任務(wù)，類別2代表帶寬型任務(wù)，類別3代表存儲(chǔ)型任務(wù)。

表3 類別比例 %

根據(jù)任務(wù)相對(duì)應(yīng)于各個(gè)類別的隸屬程度，文中選定一個(gè)閾值范圍[a,b]，如果任務(wù)的最大占比小于a，那么將任務(wù)分配給類別1，如果任務(wù)的最大占比大于b，那么將任務(wù)分配給類別3，如果任務(wù)的最大占比在閾值[a,b]之間，那么將任務(wù)分配給類別2。因此任務(wù)按照模糊聚類分為三類，第一類為偏好時(shí)間的任務(wù)，第二類為偏好帶寬的任務(wù)，第三類為偏好存儲(chǔ)的任務(wù)。

4 資源分配

針對(duì)上面劃分的三個(gè)任務(wù)類別，對(duì)于不同的任務(wù)需求采取不同的調(diào)度算法，這樣能更好地滿足用戶的個(gè)性化需求。對(duì)偏好完成時(shí)間的任務(wù)來說，為其分配較高計(jì)算能力的虛擬機(jī)能夠降低任務(wù)的整體完成時(shí)間。Min-Min算法是一種簡(jiǎn)單的算法，它運(yùn)行時(shí)間相對(duì)較短，能取得相對(duì)好的性能，然而Min-Min算法總是優(yōu)先調(diào)度短任務(wù)，造成虛擬機(jī)的利用率較低。文中提出的改進(jìn)的分段Min-Min算法主要思想是盡量將長任務(wù)分配到處理能力強(qiáng)的虛擬機(jī)上，短任務(wù)分配到處理能力弱的虛擬機(jī)上，這樣長任務(wù)花費(fèi)的時(shí)間相對(duì)會(huì)減少。如果將長任務(wù)分配到處理能力弱的虛擬機(jī)上，那么長任務(wù)執(zhí)行時(shí)間會(huì)相對(duì)拉高整體任務(wù)的完成時(shí)間。但是如果長任務(wù)和短任務(wù)的比例不均勻，容易造成各個(gè)虛擬機(jī)上面負(fù)載的極度不平衡，因此在前面分配的基礎(chǔ)上，將負(fù)載較重的虛擬機(jī)上的任務(wù)重新分配到負(fù)載較輕的虛擬機(jī)上不但能降低任務(wù)的總完成時(shí)間，而且能平衡各個(gè)虛擬機(jī)上面的負(fù)載。改進(jìn)的分段Min-Min算法分為兩個(gè)階段，第一個(gè)階段采用分段Min-Min，步驟如下：

(1)計(jì)算每個(gè)任務(wù)的關(guān)鍵字：計(jì)算每個(gè)任務(wù)在每臺(tái)虛擬機(jī)上的執(zhí)行時(shí)間，對(duì)每個(gè)任務(wù)對(duì)應(yīng)的所有執(zhí)行時(shí)間求平均值。

(2)將任務(wù)按照關(guān)鍵字降序排列。

(3)將所有任務(wù)劃分為N段。

(4)將虛擬機(jī)按照處理能力降序排列，也劃分為N段。

(5)將任務(wù)N段順序映射到虛擬機(jī)的N段上。

(6)每個(gè)映射采用Min-Min調(diào)度算法。

第二階段將重負(fù)載虛擬機(jī)的任務(wù)分配給輕負(fù)載虛擬機(jī)。

改進(jìn)算法將第一階段取得的makespan的虛擬機(jī)定義為重負(fù)載的虛擬機(jī)。

1)將重負(fù)載虛擬機(jī)上的任務(wù)按升序排列。

2)假如將任務(wù)集中的第一個(gè)任務(wù)(也就是最小的任務(wù))分配給其他虛擬機(jī)，更新該負(fù)載虛擬機(jī)及其他虛擬機(jī)的完成時(shí)間。

(1)如果其他虛擬機(jī)的最大完成時(shí)間小于makespan，那么將該任務(wù)分配給完成時(shí)間最小的虛擬機(jī)；

(2)如果其他虛擬機(jī)的最大完成時(shí)間大于makespan，那么選擇任務(wù)集中的其他任務(wù)。

若步驟(1)、(2)中有任務(wù)分配出去，則更新makespan。

3)重復(fù)步驟1)、2)，直到重負(fù)載虛擬機(jī)的任務(wù)不再分配出去，則算法結(jié)束。

對(duì)偏好帶寬的任務(wù)來說，采取輪轉(zhuǎn)調(diào)度的方法。該算法的最大優(yōu)點(diǎn)在于簡(jiǎn)單易行，但由于任務(wù)對(duì)于寬帶的實(shí)際需求不同，采用加權(quán)輪轉(zhuǎn)調(diào)度算法，這樣能根據(jù)不同任務(wù)的需求分配合適的帶寬資源。對(duì)偏好存儲(chǔ)的任務(wù)來說，為每個(gè)任務(wù)分配一定的優(yōu)先級(jí)，然后按照優(yōu)先級(jí)別高低依次調(diào)度各個(gè)任務(wù)。

5 QOSFCM調(diào)度算法流程圖

QOSFCM算法流程圖如圖2所示。

6 實(shí)驗(yàn)結(jié)果與分析

CloudSim[13]是澳大利亞墨爾本大學(xué)Rajkumar Buyya博士領(lǐng)導(dǎo)開發(fā)的云計(jì)算仿真平臺(tái)，對(duì)不同應(yīng)用和服務(wù)模型的調(diào)度策略進(jìn)行性能測(cè)試。

圖2 QOSFCM算法流程圖

伯格模型[14]將社會(huì)個(gè)體的正義性定義為一個(gè)評(píng)價(jià)函數(shù)JEF=θln(AR/JR)。其中，AR表示實(shí)際分配到的社會(huì)財(cái)富；JR表示期望分配到的社會(huì)財(cái)富；θ表示均衡性常數(shù)。當(dāng)函數(shù)值為0，認(rèn)為是正義；函數(shù)值大于0，表示行為者的期待分配小于實(shí)際分配，認(rèn)為非正義；函數(shù)值小于0，表示行為者的期待分配多于實(shí)際分配，也認(rèn)為是非正義的。文中用戶滿意度采用伯格模型來描述。

用戶對(duì)云服務(wù)的需求為：

(2)

其中，tAP代表用戶對(duì)云服務(wù)的整體性能需求；tCal，tCom，tStor分別代表用戶對(duì)云服務(wù)的計(jì)算能力、通信能力、存儲(chǔ)能力的需求；t1,t2,t3分別代表用戶對(duì)云服務(wù)的計(jì)算能力、通信能力、存儲(chǔ)能力的需求的經(jīng)驗(yàn)系數(shù)。

圖3是文中提出的算法相對(duì)于經(jīng)典算法用戶滿意度的實(shí)驗(yàn)圖。

圖3 不同數(shù)量的用戶滿意度

由于Min-Min算法只考慮了任務(wù)整體的完成時(shí)間，沒有考慮用戶任務(wù)的其他性能需求，文中提出的算法很明顯優(yōu)于Min-Min算法。

針對(duì)用戶期望在較短時(shí)間內(nèi)提供服務(wù)的特點(diǎn)，在Segment-Min-Min的基礎(chǔ)上，對(duì)任務(wù)調(diào)度的結(jié)果進(jìn)行二次優(yōu)化調(diào)度，這樣在整體上降低了任務(wù)的完成時(shí)間。

比較Min-Min(MM)、Min-MinOPT(MMOPT)、Min-MinSegment(MMSEG)、QOSFCM四種算法，如圖4～6所示。前三種傳統(tǒng)算法只考慮了用戶的總體執(zhí)行時(shí)間，而沒有考慮用戶對(duì)于計(jì)算性能、帶寬、存儲(chǔ)的差異化需求，因而不能很好地提高用戶的滿意度。QOSFCM針對(duì)用戶的不同需求分配相應(yīng)的虛擬機(jī)，不但提高了資源利用率，而且提高了用戶滿意度，因而此算法有一定程度的優(yōu)越性。針對(duì)前三種算法要么優(yōu)先考慮短任務(wù)，要么優(yōu)先考慮長任務(wù)的特點(diǎn)，文中采用長任務(wù)分配高計(jì)算能力的虛擬機(jī)，短任務(wù)分配低計(jì)算能力的虛擬機(jī)，再在此基礎(chǔ)上采取優(yōu)化的方法對(duì)任務(wù)調(diào)度進(jìn)行二次調(diào)度，能很好地提高全體任務(wù)的總的完成時(shí)間。實(shí)驗(yàn)證明QOSFCM在完成時(shí)間方面有一定的優(yōu)越性。

圖4 200個(gè)任務(wù)分配到七臺(tái)虛擬機(jī)節(jié)點(diǎn)

圖5 500個(gè)任務(wù)分配到七臺(tái)虛擬機(jī)節(jié)點(diǎn)

圖6 1 000個(gè)任務(wù)分配到七臺(tái)虛擬機(jī)節(jié)點(diǎn)

7 結(jié)束語

文中提出了一種采用基于模糊聚類的任務(wù)調(diào)度算法。算法針對(duì)不同用戶的不同需求采用相應(yīng)的調(diào)度算法，比較實(shí)驗(yàn)結(jié)果說明，文中提出的QOSFCM算法相比傳統(tǒng)算法有一定程度的改進(jìn)。

[1]BuyyaR,BrobergJ,GoscinskiA.云計(jì)算原理與范式[M].李紅軍,李冬梅,張秀程,等,譯.北京:機(jī)械工業(yè)出版社,2013:1-10.

[2]ArmbrustM,FoxA,GriffithR,etal.Aviewofcloudcomputing[J].CommunicationsoftheACM,2010,53(4):50-58.

[3] 劉 鵬.云計(jì)算[M].北京:電子工業(yè)出版社,2011:3-9.

[4]FreundRF,GherrityM,AmbrosiusS,etal.Schedulingresourcesinmulti-user,heterogeneous,computingenvironmentswithSmartNet[C]//Procof7thIEEEheterogeneouscomputingworkshop.[s.l.]:IEEE,1998:184-199.

[5]BraunTD,SiegalHJ,BeckN,etal.Acomparisonstudyofstaticmappingheuristicsforaclassofmeta-tasksonheterogeneouscomputingsystems[C]//Proceedingsofeighthheterogeneouscomputingworkshop.[s.l.]:IEEE,1999:15-29.

[6]AnoushaS,AhmadiM.Anewheuristicalgorithmforimprovingtotalcompletiontimeingridcomputing[J].LectureNotesinElectricalEngineering,2014,308:17-26.

[7]MerajiS,SalehnamadiMR.Abatchmodeschedulingalgorithmforgridcomputing[J].JournalofBasicandAppliedScientificResearch,2013,3(4):173-181.

[8] 熊聰聰,馮 龍,陳麗仙,等.云計(jì)算中基于遺傳算法的任務(wù)調(diào)度算法研究[J].華中科技大學(xué)學(xué)報(bào):自然科學(xué)版,2012(S1):1-4.

[9] 華夏渝,鄭 駿,胡文心.基于云計(jì)算環(huán)境的蟻群優(yōu)化計(jì)算資源分配算法[J].華東師范大學(xué)學(xué)報(bào):自然科學(xué)版,2010(1):127-134.

[10] 封良良.云計(jì)算環(huán)境下基于改進(jìn)粒子群的任務(wù)調(diào)度算法[D].烏魯木齊:新疆大學(xué),2013.

[11] 李文娟,張啟飛,平玲娣,等.基于模糊聚類的云任務(wù)調(diào)度算法[J].通信學(xué)報(bào),2012,33(3):146-154.

[12]MiyamotoS,IchihashiH,HondaK.Algorithmsforfuzzyclustering—methodsinc-meansclusteringwithapplications[M].Berlin:Springer-Verlag,2008.

[13]BuyyaR,MurshedM.GridSim:atoolkitforthemodelingandsimulationofdistributedresourcemanagementandschedulingforgridcomputing[J].ConcurrencyandComputation:PracticeandExperience,2002,14(13-15):1175-1220.

[14] 趙春燕.云環(huán)境下作業(yè)調(diào)度算法研究與實(shí)現(xiàn)[D].北京：北京交通大學(xué),2009.

Research on Task Scheduling Algorithm Based on QoS Classification

ZHAO Ke-wei，HONG Long，ZHOU Ning-ning

(School of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210000，China)

In order to improve the quality of cloud service providers and the satisfaction of users about cloud services,a task scheduling algorithm based on QoS classification is put forward.This algorithm is suited with independent tasks.Firstly,fuzzy clustering algorithm is used to classify task set.Then the traditional segmented Min-Min algorithm is applied for task allocation.Segmented Min-Min algorithm is more granular for resource allocation compared with the Min-Min algorithm,so it can improve the matching degree between task and resource.Only in this way can further reduce the completion time,and achieve a certain load balancing.The experimental results show that the proposed method can not only meet the needs of the user’s QoS,but also obtain shorter completion time.

cloud computing;task scheduling;Min-Min;fuzzy clustering;load balance

2015-09-07

2015-12-10

時(shí)間：2016-05-25

國家自然科學(xué)基金資助項(xiàng)目(61170322，61373065,61302157)；軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室開放課題(SKLSDE-2011KF-04)

趙科偉(1988-)，男，碩士生，研究方向?yàn)樵朴?jì)算與大數(shù)據(jù)處理；洪 龍，教授，博士，碩士生導(dǎo)師，研究方向?yàn)閿?shù)理邏輯與分布式系統(tǒng)；周寧寧，博士，副教授，通訊作者，研究方向?yàn)閳D像分析與處理。

http://www.cnki.net/kcms/detail/61.1450.TP.20160525.1706.026.html

TP301.6

A

1673-629X(2016)07-0065-05

10.3969/j.issn.1673-629X.2016.07.014