趙科偉，洪 龍，周寧寧

(南京郵電大學 計算機學院，江蘇 南京 210000)

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

趙科偉，洪 龍，周寧寧

(南京郵電大學 計算機學院，江蘇 南京 210000)

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

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

1 概 述

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

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

(1)計算每個任務在每臺虛擬機上的完成時間，找出每個任務對應的最小完成時間，把此最小完成時間放到一個數(shù)組completeTime[n]中；

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

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

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

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

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

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

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

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

2 調(diào)度模型

2.1 任務模型

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

2.2 資源模型

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

2.3 任務分配模型

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

圖1 元任務到虛擬機的放置示意圖

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

假設在初始時刻三臺虛擬機的負載如表1所示。

表1 虛擬機初始負載

各個元任務在所分配的虛擬機上的執(zhí)行時間如表2所示。

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

3 任務模糊聚類

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

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

(1)

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

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

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

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

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

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

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

表3 類別比例 %

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

4 資源分配

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

(1)計算每個任務的關鍵字：計算每個任務在每臺虛擬機上的執(zhí)行時間，對每個任務對應的所有執(zhí)行時間求平均值。

(2)將任務按照關鍵字降序排列。

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

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

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

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

第二階段將重負載虛擬機的任務分配給輕負載虛擬機。

改進算法將第一階段取得的makespan的虛擬機定義為重負載的虛擬機。

1)將重負載虛擬機上的任務按升序排列。

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

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

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

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

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

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

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

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

6 實驗結果與分析

CloudSim[13]是澳大利亞墨爾本大學Rajkumar Buyya博士領導開發(fā)的云計算仿真平臺，對不同應用和服務模型的調(diào)度策略進行性能測試。

圖2 QOSFCM算法流程圖

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

用戶對云服務的需求為：

(2)

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

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

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

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

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

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

圖4 200個任務分配到七臺虛擬機節(jié)點

圖5 500個任務分配到七臺虛擬機節(jié)點

圖6 1 000個任務分配到七臺虛擬機節(jié)點

7 結束語

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

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

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

[3] 劉 鵬.云計算[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] 熊聰聰,馮 龍,陳麗仙,等.云計算中基于遺傳算法的任務調(diào)度算法研究[J].華中科技大學學報:自然科學版,2012(S1):1-4.

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

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

[11] 李文娟,張啟飛,平玲娣,等.基于模糊聚類的云任務調(diào)度算法[J].通信學報,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)度算法研究與實現(xiàn)[D].北京：北京交通大學,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

時間：2016-05-25

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

趙科偉(1988-)，男，碩士生，研究方向為云計算與大數(shù)據(jù)處理；洪 龍，教授，博士，碩士生導師，研究方向為數(shù)理邏輯與分布式系統(tǒng)；周寧寧，博士，副教授，通訊作者，研究方向為圖像分析與處理。

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