等價類劃分的粗粒度任務調度算法

劉東領, 袁景凌,2,陳旻騁

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

1 引 言

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

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

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

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

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

2 問題建模及等價類劃分

2.1 任務和資源模型

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

①length:表示任務指令長度.

②osType:表示了任務執行時最優匹配的系統類型.

③inSize:表示任務的輸入文件大小.

④outSize:表示任務執行完成后輸出文件大小.

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

①mips:表示虛擬機的執行能力MIPS.

②osType:表示了該虛擬機對應的系統類型.

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

④storage:表示虛擬機的內存,即隨機存取存儲器.

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

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

(1)

2.2 等價類劃分

等價類能按照多種規則對數據集進行劃分,如按區間劃分、按數值劃分、按處理方式劃分等.云環境下的任務和資源經過量化后,任務和資源序列可以近似的用一個決策表表示,而異構的任務和資源適合用等價類按區間劃分的方式進行處理.

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

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

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

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

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

表1 原始任務序列表
Table 1 Original task sequence

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

3 等價類劃分的粗粒度調度策略

3.1 粒度間能力匹配調度

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

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

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

輸出:任務組T={CGT1,CGT2,…,CGTm}調度方案

1.fortask←1toT.sizedo

2.CGTi←EqualClass_Algorithm(task)/*運用等價類,將任務序列劃分成任務組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/*計算平均執行能力*/

8.end

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

10.sort_desc(CGV,CGVi_avgMips)

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

12.whilet

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

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

15.t++/*任務組標識加一*/

16.end

3.2 粒度內貪心調度

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

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

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

算法2.greedySchedule

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

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

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

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

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

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

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

6.fort1tomdo

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

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

9.forvn-2to0do

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

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

/*若同時最優,選任務數較少虛擬機*/

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

17.end

18.end

3.3 等價類劃分的粗粒度調度模型

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

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

步驟2.粒度間能力匹配調度,任務組和資源組按平均指令長度和執行能力匹配調度;

步驟3.粒度內貪心調度,指定每組任務內單個任務具體調度策略.

圖1 整體調度流程圖Fig.1 Overall scheduling process

4 實驗設計及結果分析

4.1 實驗環境

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

4.2 任務及資源設置

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

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

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

4.3 仿真實驗流程

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

步驟2.在CloudSim主流程中讀取上述虛擬機和任務參數文件,創建虛擬機列表和任務列表并提交到數據中心,準備對任務進行調度.

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

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

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

4.4 實驗結果分析

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

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

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

圖3 等價類劃分的任務調度實驗結果Fig.3 Result of coarse-grain scheduling experiment

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

5 結束語

本文針對云計算環境下任務和資源的異構性,提出了等價類劃分的粗粒度任務調度算法.該算法將任務分成兩級調度模式:粒度間,運用等價類將異構的任務和資源進行劃分分類,使任務組和資源組按能力匹配進行調度;粒度內,每個任務組內具體任務采用貪心進行調度,進一步優化任務的執行時間.同時,運用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] 袁景凌,鐘 珞,楊 光,等.綠色數據中心不完備能耗大數據填補及分類算法研究[J].計算機學報,2015,38(12):2499-2516.

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

[6] 李智勇,陳少淼,楊 波,等.異構云環境多目標Memetic優化任務調度方法[J].計算機學報,2016,39(2):377-390.

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

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

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

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

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

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

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