劉東領(lǐng), 袁景凌,2,陳旻騁

1(武漢理工大學 計算機科學與技術(shù)學院, 武漢 430070) 2(交通物聯(lián)網(wǎng)技術(shù)湖北省重點實驗室 (武漢理工大學)，武漢 430070)

1 引 言

隨著信息技術(shù)的飛速發(fā)展,大量的數(shù)據(jù)進入人們的視野,數(shù)據(jù)的日益增加,使得傳統(tǒng)的數(shù)據(jù)處理方式已不再適用,于是基于大數(shù)據(jù)的處理手段—云計算[1]應(yīng)運而生.在對云計算數(shù)據(jù)中心的優(yōu)化研究中,節(jié)能的綠色數(shù)據(jù)中心[2]及高效的任務(wù)調(diào)度[3]算法是當前研究的重要方向.研究表明,任務(wù)調(diào)度是NP完全問題,它從m個任務(wù)分配到n個資源上的nm種可能中尋找最優(yōu)解,從而得到最佳的調(diào)度性能.

目前,關(guān)于任務(wù)調(diào)度的算法有傳統(tǒng)的Min-Min、Max-Min算法[4]和遺傳算法.合理有效的任務(wù)調(diào)度算法是保證用戶QoS的關(guān)鍵,也是研究人員和技術(shù)人員共同關(guān)注的一個熱點話題,如文獻[5]以時間作為衡量數(shù)據(jù)傳輸?shù)臉藴?提出了一種動態(tài)調(diào)整數(shù)據(jù)副本個數(shù)的數(shù)據(jù)放置與任務(wù)調(diào)度算法;文獻[6]以異構(gòu)環(huán)境下多目標優(yōu)化調(diào)度為目標,運用Memetic局部搜索算子的局部優(yōu)化能力來提高算法的收斂速度.文獻[7-9]運用模糊聚類將資源進行劃分,根據(jù)任務(wù)參數(shù)在不同的聚類中選擇資源,使任務(wù)選擇性能較好的資源簇;文獻[10]提出了一種模糊商空間理論的資源調(diào)度算法,結(jié)合模糊商空間理論建立模糊等價類和距離函數(shù),進行資源分配;文獻[11]提出了一種融合粒子群和遺傳算法的改進算法,根據(jù)云計算環(huán)境特點對資源進行分類,以遺傳算法來克服粒子群的局部最優(yōu)問題,擴展粒子的搜索空間,減少任務(wù)的完成時間.

本文結(jié)合粗糙集相關(guān)理論,根據(jù)任務(wù)與資源的特點,通過建立合適的任務(wù)和資源模型,提出了一種等價類劃分的粗粒度任務(wù)調(diào)度算法,主要工作如下:

1)對云計算環(huán)境下的任務(wù)和資源特點進行分析,選取任務(wù)和資源的一些關(guān)鍵特征屬性,對其進行量化.使用等價類劃分思想,給定屬性劃分依據(jù)和劃分區(qū)間,對多樣性的任務(wù)和資源進行粒度劃分.

2)計算任務(wù)組和資源組的平均指令長度和執(zhí)行能力,將任務(wù)調(diào)度分為兩級調(diào)度模式:粒度間每個任務(wù)組采用按能力匹配的方式進行調(diào)度;粒度內(nèi),即每個任務(wù)組內(nèi)具體任務(wù)采用貪心調(diào)度,最后完成實驗對比分析.

2 問題建模及等價類劃分

2.1 任務(wù)和資源模型

任務(wù)調(diào)度是將指定任務(wù)分配給合適的資源,調(diào)度性能會因任務(wù)資源屬性的差異而不同,所以在調(diào)度前應(yīng)對任務(wù)和資源進行建模.我們用三元組TS=(T,V,R)來表示云計算環(huán)境下的任務(wù)調(diào)度模型,T={t1,t2,…,tm}表示m個相互獨立、無優(yōu)先關(guān)系的任務(wù)集合,第i個任務(wù)可對其進一步細化特征ti={lengthi,osTypei,inSizei,outSizei},各特征描述如下:

①length:表示任務(wù)指令長度.

②osType:表示了任務(wù)執(zhí)行時最優(yōu)匹配的系統(tǒng)類型.

③inSize:表示任務(wù)的輸入文件大小.

④outSize:表示任務(wù)執(zhí)行完成后輸出文件大小.

V={v1,v2,…,vn}表示資源的集合.第i個資源可表示為vi={mipsi,osTypei,rami,storagei,bwi},各特征描述如下:

①mips:表示虛擬機的執(zhí)行能力MIPS.

②osType:表示了該虛擬機對應(yīng)的系統(tǒng)類型.

③ram:表示虛擬機的容量.

④storage:表示虛擬機的內(nèi)存,即隨機存取存儲器.

⑤bw:表示虛擬機的帶寬.

R=[rij](1≤i≤m,1≤j≤n)代表任務(wù)ti在虛擬機vj上的運行時間,此處時間計算公式為:

(1)

2.2 等價類劃分

等價類能按照多種規(guī)則對數(shù)據(jù)集進行劃分,如按區(qū)間劃分、按數(shù)值劃分、按處理方式劃分等.云環(huán)境下的任務(wù)和資源經(jīng)過量化后,任務(wù)和資源序列可以近似的用一個決策表表示,而異構(gòu)的任務(wù)和資源適合用等價類按區(qū)間劃分的方式進行處理.

IND(P)={(x,y)∈U×U|?a∈P,f(x,a)=f(y,a)}

關(guān)系IND(P)構(gòu)成了U的一個劃分,用U/IND(P)表示,簡記為U/P,則滿足[x]p={y|?a∈P,f(x,a)=f(y,a)}關(guān)系的元素構(gòu)成U/P上的等價類[12].

2)等價類劃分:等價類劃分是在任務(wù)調(diào)度前對任務(wù)和資源的預(yù)處理.表1代表了原始任務(wù)序列,結(jié)合上述等價類定義,對該任務(wù)實例進行等價類劃分.

設(shè)置任務(wù)長度length的區(qū)間梯度為100,輸入文件大小inSize和輸出文件大小outSize的區(qū)間梯度為10,并用0、1、2代表三種系統(tǒng)類型.按照上述區(qū)間劃分及分類標準,可將以上10個任務(wù)劃分成以下等價類:

{{t1,t5},{t4,t6,t8},{t3,t7},{t2,t10},{t9}}

表1 原始任務(wù)序列表
Table 1 Original task sequence

任務(wù)特征屬性lengthosTypeinSizeoutSizet1230112．716．8t2323023．226．9t3343224．127．4t4445130．835．6t5256114．819．3t6421132．237．5t7388222．525．8t8467134．839．1t9396132．538．3t10367021．125．0

3 等價類劃分的粗粒度調(diào)度策略

3.1 粒度間能力匹配調(diào)度

設(shè)CGT(coarse-grain tasks)表示一個粗粒度任務(wù)組,CGV(coarse-grain vms)表示一個粗粒度資源組.則經(jīng)過等價類劃分后,任務(wù)模型和資源模型可表示為:

T={CGT1(t1,t2,…,ta),CGT2(t1,t2,…,tb),…,CGTm(t1,t2,…,tk)}

V={CGV1(v1,v2,…,vx),CGV2(v1,v2,…,vy),…,CGVn(v1,v2,…,vz)}

算法1. coarseGrainSchedule

輸入:任務(wù)資源集合T={t1,t2,…,tm}、V={v1,v2,…,vn}

輸出:任務(wù)組T={CGT1,CGT2,…,CGTm}調(diào)度方案

1.fortask←1toT.sizedo

2.CGTi←EqualClass_Algorithm(task)/*運用等價類,將任務(wù)序列劃分成任務(wù)組CGTi(i = 1,2…m)*/

3.CGTi_avgLen←CGTLi/*計算CGTi平均長度*/

4.end

5.forvm←1toV.sizedo

6.CGVi←EqualClass_Algorithm(vm) /*等價類分組*/

7.CGVi_avgMips←CGVMi/*計算平均執(zhí)行能力*/

8.end

9.sort_desc(CGT,CGTi_avgLen) /*任務(wù)組、資源組分別按平均指令長度和執(zhí)行能力降序排列*/

10.sort_desc(CGV,CGVi_avgMips)

11.t,v←0 /*初始化任務(wù)組CGT和資源組CGV位置*/

12.whilet

13.STV(CGTt,CGVv)/*將CGTt分配給CGVv*/

14.v←(v+1)%CGV.Length/*循環(huán)遍歷粒度任務(wù)組*/

15.t++/*任務(wù)組標識加一*/

16.end

3.2 粒度內(nèi)貪心調(diào)度

貪心算法考慮到了任務(wù)和虛擬機之間配置不一樣的情況,這樣任務(wù)在不同虛擬機上執(zhí)行的時間就不同.此時,根據(jù)貪心算法的思想,任務(wù)在選擇虛擬機的時候使用貪心策略,確保每次選擇的虛擬機都是最佳的.

結(jié)合文中實際任務(wù)及資源模型,運用貪心策略主要有以下幾點合理性:貪心策略針對的是異構(gòu)環(huán)境下的任務(wù)和資源,而文中設(shè)置的任務(wù)和資源模型是異構(gòu)的;貪心算法的目標在于優(yōu)化任務(wù)的執(zhí)行時間,和任務(wù)的等價類調(diào)度目標一致;貪心算法具有靈活性,能根據(jù)具體不同的任務(wù)模型設(shè)置合適的貪心策略;貪心算法不僅能確保任務(wù)的總完成時間相對較優(yōu),也能兼顧每個資源組內(nèi)的負載均衡[13].

在上述等價類劃分的粒度間任務(wù)組調(diào)度中,假定任務(wù)組CGTm(t1,t2,…,tk)和資源組CGVn(v1,v2,…,vz)相匹配.用m=|CGTm|表示分解后任務(wù)的數(shù)量,ti表示第i個任務(wù),各任務(wù)之間相互獨立;用n=|CGVn|表示資源數(shù)量,vi表示第i個虛擬機資源.假設(shè)數(shù)據(jù)中心中的任務(wù)數(shù)量大于或等于虛擬機的數(shù)量(m≥n),一個任務(wù)只能分配給一個虛擬機執(zhí)行,而且一個虛擬機在執(zhí)行過程中,同時間段不能去執(zhí)行其他任務(wù).用上述定義的運行時間R[i][j]表示第i個任務(wù)在第j個虛擬機上的完成時間,則m個任務(wù)在n個虛擬機上的執(zhí)行時間對應(yīng)為一個m×n的矩陣,具體算法描述如下:

算法2.greedySchedule

輸入:任務(wù)組CGTm(t1,t2,…,tk)和資源組CGVn(v1,v2,…,vz)

輸出:任務(wù)組CGTm(t1,t2,…,tk)中每個任務(wù)的調(diào)度方案

1.CGTm←sortDescByLen(CGTm)/*按指令長度降序排序*/

2.CGVn←sortAscByMips(CGVn)/*按執(zhí)行能力升序排序*/

3.R[m][n] /*初始化運行時間矩陣*/

4.vmLoad[i],vmTasks[i] /*記錄虛擬機vi上任務(wù)運行總時間 及任務(wù)數(shù)*/

5.CGTm[0].setVm(CGVn[n-1])/*完成初始任務(wù)分配*/

6.fort1tomdo

7.bestLoc←n-1 /*記錄當前最優(yōu)虛擬機位置*/

8.minLoad←vmLoad[bestLoc]+R[t][bestLoc] /*記錄最優(yōu)分配值*/

9.forvn-2to0do

10.ifvmLoad[v] = 0then/*若當前虛擬機未分配任務(wù)*/

11.bestVm←CGVn[v] /*則直接分配*/

12.ifminLoad>vmLoad[v]+R[t][v]then

13.bestVm←CGVn[v] /*分配給負載少的虛擬機*/

14.minLoad←vmLoad[v]+R[t][v] /*更新minLoad*/

15.ifminLoad=vmLoad[v]+R[t][v]then

/*若同時最優(yōu),選任務(wù)數(shù)較少虛擬機*/

16.bestVm←min(vmTasks[v],vmTasks[bestLoc])

17.end

18.end

3.3 等價類劃分的粗粒度調(diào)度模型

等價類劃分的粗粒度任務(wù)調(diào)度算法采用了等價類對任務(wù)和資源進行粒度劃分分組,每組任務(wù)按其平均指令長度分配給計算能力相匹配的資源組,同時在每組任務(wù)的內(nèi)部調(diào)度過程中使用貪心算法.如圖1所示,整個調(diào)度流程可分為三個步驟:

步驟1.運用等價類劃分思想,對用戶任務(wù)請求和云計算資源進行粒度劃分;

步驟2.粒度間能力匹配調(diào)度,任務(wù)組和資源組按平均指令長度和執(zhí)行能力匹配調(diào)度;

步驟3.粒度內(nèi)貪心調(diào)度,指定每組任務(wù)內(nèi)單個任務(wù)具體調(diào)度策略.

圖1 整體調(diào)度流程圖Fig.1 Overall scheduling process

4 實驗設(shè)計及結(jié)果分析

4.1 實驗環(huán)境

為驗證基于等價類劃分的粗粒度任務(wù)調(diào)度算法的可行性,本文選用了CloudSim云計算仿真平臺.CloudSim是一個基于事件的仿真器,實體和實體間基于消息進行通訊,它使用戶可以在一臺主機上對大規(guī)模的集群進行仿真.實驗基礎(chǔ)環(huán)境包括:1)硬件:2.6GHz雙核CPU、4GB內(nèi)存、500G硬盤;2)軟件:windows8.1操作系統(tǒng)、Eclipse開發(fā)環(huán)境、java編程語言.

4.2 任務(wù)及資源設(shè)置

本算法是基于異構(gòu)環(huán)境下的算法,實驗中我們假設(shè)數(shù)據(jù)中心主機的數(shù)量為100,且每臺主機上只有唯一的一臺虛擬機,任務(wù)的總數(shù)隨實驗次數(shù)動態(tài)設(shè)置.為了模擬不同的任務(wù)需要調(diào)度到特定的虛擬機上執(zhí)行,我們對CloudSim中的Cloudlet類和Vm類進行了改寫,為它們添加一個新的字段:系統(tǒng)類型(OS),表明任務(wù)需提交到和其OS類型相同的虛擬機上執(zhí)行,否則會增加額外的時間開銷.以下為虛擬機、任務(wù)參數(shù)設(shè)置:

虛擬機的MIPS(執(zhí)行能力)和Bw(帶寬)的范圍是400-1000,OS類型考慮到三種情況:Linux、Windows和Mac,Ram和Storage設(shè)置為固定值.

任務(wù)長度的范圍為20000-80000,OS類型同虛擬機有三種取值,inSize(輸入文件大小)和outSize(輸出文件大小)的范圍為200-800.

4.3 仿真實驗流程

步驟1.指定任務(wù)和虛擬機的數(shù)目及參數(shù)的取值范圍,使用隨機函數(shù)構(gòu)建虛擬機和任務(wù)的參數(shù)列表文件.

步驟2.在CloudSim主流程中讀取上述虛擬機和任務(wù)參數(shù)文件,創(chuàng)建虛擬機列表和任務(wù)列表并提交到數(shù)據(jù)中心,準備對任務(wù)進行調(diào)度.

步驟3.改寫DatacenterBroker類,增加自定義調(diào)度方法bindCloudletToVmByOsCapacity(),該方法對接收到的虛擬機列表和任務(wù)列表進行等價類劃分,并以Map的形式存放.其中value為每一個粒度任務(wù)組或資源組,key對應(yīng)該任務(wù)組的平均指令長度或資源組的平均執(zhí)行能力.

步驟4.把所有任務(wù)組和資源組分別按平均指令長度和執(zhí)行能力降序排序,使排序后的任務(wù)組輪詢分配到資源組,實現(xiàn)按能力匹配調(diào)度策略.同時每個任務(wù)組內(nèi)具體任務(wù)采用貪心算法,實現(xiàn)兩級調(diào)度模式,提升調(diào)度性能.

步驟5.根據(jù)任務(wù)完成時間公式,計算任務(wù)執(zhí)行總時間之和及任務(wù)完成時間,進行實驗對比分析.

4.4 實驗結(jié)果分析

1)圖2展示了貪心算法和CloudSim自帶的順序調(diào)度算法在任務(wù)總執(zhí)行時間和任務(wù)完成時間上的對比圖,實驗是將40個參數(shù)配置不同的任務(wù)分配到10個不同的虛擬機上.從五次的實驗結(jié)果可以看出,貪心算法在任務(wù)的總執(zhí)行時間和完成時間上比普通的順序調(diào)度算法有明顯的效率提升,同時也證明了粒度內(nèi)部使用貪心算法的可行性.

圖2 貪心算法實驗結(jié)果Fig.2 Result of greedy algorithm experiment

2)等價類劃分的粗粒度調(diào)度實驗.實驗中根據(jù)任務(wù)總數(shù)的不同,分別做了五次實驗,任務(wù)總數(shù)分別2000、2500、3000、3500、4000.采用了三種調(diào)度方案對任務(wù)進行調(diào)度,并以任務(wù)總執(zhí)行時間和任務(wù)完成時間作為參考.

圖3 等價類劃分的任務(wù)調(diào)度實驗結(jié)果Fig.3 Result of coarse-grain scheduling experiment

從圖3中可以看出,將任務(wù)和虛擬機進行等價類劃分后,再使用貪心算法進行任務(wù)的調(diào)度,能明顯減少任務(wù)執(zhí)行的總時間和任務(wù)的完成時間.一方面是因為運用等價類進行粗粒度劃分后,降低了每一組任務(wù)在選擇資源上的時間開銷;另一方面是因為等價類劃分后的任務(wù)組和資源組的匹配調(diào)度,確保了任務(wù)在資源選取上的合理性,降低了任務(wù)的執(zhí)行時間.而Kmeans聚類調(diào)度,因聚類的模糊性,致使部分影響調(diào)度性能的屬性不能很好進行分類,導(dǎo)致任務(wù)總執(zhí)行時間較長;同時,因聚類后的部分簇任務(wù)數(shù)量較多,也會導(dǎo)致任務(wù)完成時間較長,甚至比順序調(diào)度更長.綜上,通過上述的實驗對比,我們可以得出,任務(wù)和資源的等價類劃分調(diào)度能有效的將任務(wù)和資源進行歸類,對于優(yōu)化任務(wù)的執(zhí)行時間具有可行的意義.

5 結(jié)束語

本文針對云計算環(huán)境下任務(wù)和資源的異構(gòu)性,提出了等價類劃分的粗粒度任務(wù)調(diào)度算法.該算法將任務(wù)分成兩級調(diào)度模式:粒度間,運用等價類將異構(gòu)的任務(wù)和資源進行劃分分類,使任務(wù)組和資源組按能力匹配進行調(diào)度;粒度內(nèi),每個任務(wù)組內(nèi)具體任務(wù)采用貪心進行調(diào)度,進一步優(yōu)化任務(wù)的執(zhí)行時間.同時,運用CloudSim進行模擬仿真實驗,驗證了本文算法的合理性與正確性.

[1] Botta A,De Donato W,Persico V,et al.Integration of cloud computing and Internet of things[J].Future Generation Computer Systems,2015,56(C):684-700.

[2] Yuan Jing-ling,Zhong Luo,Yang Guang,et al.Towards filling and classification of incomplete energy big data for green data centers[J].Chinese Journal of Computers,2015,38(12):2499-2516.

[3] Salot P.A survey of various scheduling algorithm in cloud computing environment[J].International Journal of Research and Engineering Technology,2013,2(2):131-135.

[4] Panda S K,Bhoi S K,Khilar P M.A semi-interquartile min-min max-min(SIM2)approach for grid task scheduling[C].Proceedings of International Conference on Advances in Computing,Springer India,2013:415-421.

[5] Wang Qiang,Li Xiong-fei,Wang Jing.A data placement and task scheduling algorithm in cloud computing[J].Journal of Computer Research and Development,2014,51(11):2416-2426.

[6] Li Zhi-yong,Chen Shao-miao,Yang Bo,et al.Mutil-objective memetic algorithm for task scheduling on heterogeneous cloud[J].Chinese Journal of Computers,2016,39(2):377-390.

[7] Li Wen-juan,Zhang Qi-fei,Ping Ling-di,et al.Cloud scheduling algorithm based on fuzzy clustering[J].Journal on Communications,2012,33(3):146-154.

[8] Guo Feng-yu,Yu Long,Tian Sheng-wei,et al.Workflow task scheduling algorithm based on resource clustering in cloud computing environment[J].Journal of Computer Applications,2013,33(8):2154-2157.

[9] Hu Meng,Yuan Ying-chun,Wang Xue-yang.Cloud task scheduling algorithm based on improved fuzzy clustering[J].Computer Engineering and Design,2015,36(9):2437-2441.

[10] Qi Ping,Li Long-shu.Task scheduling algorithm base on fuzzy quotient space theory in cloud environment[J].Journal of Chinese Computer Systems,2013,34(8):1793-1797.

[11] Wang Bo,Zhang Xiao-lei.Task scheduling algorithm based on particle swarm optimization genetic algorithms in cloud computing environment[J].Computer Engineering and Applications,2015,51(6):84-88.

[12] Xu Zhang-yan,Liu Zuo-peng,Yang Bing-ru,et al.A quick attribute reduction algorithm with complexity of max max(O(|C||U|),O(|C2|U/C|))[J].Chinese Journal of Computers,2006,29(3):391-399.

[13] Zhou Zhou,Hu Zhi-gang.Incorporate greedy strategy into scheduling algorithm for cloud computing[J].Journal of Chinese Computer Systems,2015,36(5):1024-1027.

附中文參考文獻：

[2] 袁景凌,鐘 珞,楊 光,等.綠色數(shù)據(jù)中心不完備能耗大數(shù)據(jù)填補及分類算法研究[J].計算機學報,2015,38(12):2499-2516.

[5] 王 強,李雄飛,王 婧.云計算中的數(shù)據(jù)放置與任務(wù)調(diào)度算法[J].計算機研究與發(fā)展,2014,51(11):2416-2426.

[6] 李智勇,陳少淼,楊 波,等.異構(gòu)云環(huán)境多目標Memetic優(yōu)化任務(wù)調(diào)度方法[J].計算機學報,2016,39(2):377-390.

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

[8] 郭鳳羽,禹 龍,田生偉,等.云計算環(huán)境下對資源聚類的工作流任務(wù)調(diào)度算法[J].計算機應(yīng)用,2013,33(8):2154-2157.

[9] 胡 蒙,苑迎春,王雪陽.改進模糊聚類的云任務(wù)調(diào)度算法[J].計算機工程與設(shè)計,2015,36(9):2437-2441.

[10] 齊 平,李龍澍.云環(huán)境下結(jié)合模糊商空間理論的資源調(diào)度算法[J].小型微型計算機系統(tǒng),2013,34(8):1793-1797.

[11] 王 波,張曉磊.基于粒子群遺傳算法的云計算任務(wù)調(diào)度研究[J].計算機工程與應(yīng)用,2015,51(6):84-88.

[12] 徐章艷,劉作鵬,楊炳儒,等.一個復(fù)雜度為max(O(|C||U|),O(|C2|U/C|))的快速屬性約簡算法[J].計算機學報,2006,29(3):391-399.

[13] 周 舟,胡志剛.云計算中融入貪心策略的調(diào)度算法研究[J].小型微型計算機系統(tǒng),2015,36(5):1024-1027.