劉林東
(廣東第二師范學(xué)院 計算機科學(xué)系, 廣東 廣州 510303)
分布式異構(gòu)處理機環(huán)境中,按任務(wù)之間的依賴關(guān)系,可以將任務(wù)調(diào)度分為獨立任務(wù)調(diào)度[1-3]和相關(guān)任務(wù)調(diào)度[4-5]兩種,獨立任務(wù)調(diào)度的任務(wù)之間沒有相關(guān)性,任務(wù)調(diào)度沒有先后順序限制,也不存在數(shù)據(jù)通信;相關(guān)任務(wù)調(diào)度的任務(wù)存在先后關(guān)系,一般DAG圖對任務(wù)進(jìn)行描述,且任務(wù)間存在數(shù)據(jù)通信. 常用的獨立任務(wù)調(diào)度算法包括RR[6]、wRR、LC、Min-Min、Min-Max、Sufferage以及遺傳算法[7]等,wRR調(diào)度算法[8]通過隊列優(yōu)先級來區(qū)別對待不同QoS需求的任務(wù)調(diào)度,沒有考慮異構(gòu)處理器的計算性能對不同優(yōu)先級隊列的公平性的影響.
分布式異構(gòu)環(huán)境中任務(wù)集T包括n個獨立任務(wù),分別為t0,t1,…,tn-1,處理機集P包括m個性能異構(gòu)的處理機,分別為P0,P1,…,Pm-1,表1描述了7個任務(wù)在4個處理機上執(zhí)行開銷. 設(shè)任務(wù)ti被調(diào)度的處理機不受限制,每個處理機同時只能調(diào)度1個任務(wù),1個任務(wù)不能在多個處理機上調(diào)度. 如何將n個獨立任務(wù)調(diào)度到m個處理機,且滿足任務(wù)集T在處理機集P上的執(zhí)行跨度、平均等待時間優(yōu)于同類算法是文中需要主要研究的問題.
表1 任務(wù)在處理機上的執(zhí)行開銷
ms任務(wù)P0P1P2P3t0200211180223t110212291130t281928895t355595761t432332936t5155160149173t6135142122160
w0w1w2w3P0P1P2P3t0t1t2t3t4t5t6Q0Q1Q2Q3a.隊列調(diào)度b.處理機調(diào)度t4t0t1t2t3t5t6P0P1P2P3
圖1 wRR算法任務(wù)調(diào)度
為解決wRR算法在獨立任務(wù)調(diào)度過程中出現(xiàn)的問題,提出一種改進(jìn)的任務(wù)調(diào)度模型及iwRR任務(wù)調(diào)度算法.
帶閾值的加權(quán)輪轉(zhuǎn)任務(wù)調(diào)度模型包括處理機池初始化和任務(wù)調(diào)度兩個階段,如圖2所示. 處理機池中的處理機均被調(diào)度之后,根據(jù)隊列中的任務(wù)調(diào)度請求,處理機調(diào)度模塊根據(jù)當(dāng)前處理機的調(diào)度情況,將任務(wù)調(diào)度結(jié)束時間最晚的處理機Pj從處理機池中刪除,其余處理機均加入處理機池中;在任務(wù)調(diào)度階段,更新處理機池中的每個處理機的權(quán)值,然后按照wRR調(diào)度隊列中的所有任務(wù).
t0t4t1t3t2t5t6處理機集P處理機池P1wRR算法任務(wù)調(diào)度模塊任務(wù)集T
圖2 改進(jìn)的加權(quán)輪轉(zhuǎn)調(diào)度模型
改進(jìn)的加權(quán)輪轉(zhuǎn)調(diào)度算法iwRR算法如下:
輸入:任務(wù)集T,處理機集P,任務(wù)在處理機上的執(zhí)行開銷T[n][m],權(quán)值w[m];
輸出:任務(wù)調(diào)度關(guān)系表S[n][m],任務(wù)調(diào)度跨度makespan,任務(wù)平均等待時間AWT;
初始化處理機池P;
while任務(wù)集T非空{(diào)
for(i=0;i 計算處理機Pi的結(jié)束時間E[i]; } 找出最小的E[j]對應(yīng)的處理機Pj; 從處理機池P中刪除處理機Pj; for(i=0;i 計算每個處理機上分配的任務(wù)數(shù)ai; } 對于當(dāng)前任務(wù)ti{ ifcj 調(diào)度任務(wù)到處理機Pj; elsej=(j+1)mod(m-1); } 計算輸出makespan和AWT; } 為驗證iwRR算法的性能,將iwRR算法與wRR算法在相同的實驗條件下進(jìn)行性能比較,主要對任務(wù)調(diào)度跨度Makespan值進(jìn)行比較. 利用SimGrid[9-11]環(huán)境下的集群環(huán)境仿真分布式異構(gòu)環(huán)境,分布式異構(gòu)計算環(huán)境中的處理機對應(yīng)SimGrid中的處理機,對SimGrid模擬器進(jìn)行設(shè)置:處理機之間通過高速網(wǎng)絡(luò)互連;每個任務(wù)只能在1個處理機上執(zhí)行,且任務(wù)被調(diào)度后不能中止;每個處理機同時只能調(diào)度1個任務(wù);處理機的任務(wù)調(diào)度性能異構(gòu). 仿真實驗中的軟硬件環(huán)境為:Intel Core(TM) i5-8265U 1.6 1.8GHzCPU、4GB內(nèi)存硬件環(huán)境、操作系統(tǒng)為Ubuntu12. iwRR算法輸入有兩個,分別是任務(wù)執(zhí)行時間矩陣和被調(diào)度任務(wù). 有兩種不同的任務(wù)集執(zhí)行時間矩陣,任務(wù)數(shù)均為10個任務(wù),處理機數(shù)為4和6兩種情況;任務(wù)在處理機上的執(zhí)行開銷通過隨機程序生成;被調(diào)度任務(wù)集的任務(wù)數(shù)為50,100,…,1 000;任務(wù)編號通過程序隨機產(chǎn)生;任務(wù)到達(dá)時間為0. 1)4個處理機 4個處理機情況下兩種算法任務(wù)調(diào)度跨度對比情況如圖3所示,iwRR算法在不同任務(wù)數(shù)情況下,任務(wù)調(diào)度跨度要比wRR算法長,wRR算法的性能總體上要優(yōu)于iwRR算法,wRR算法任務(wù)調(diào)度跨度要比iwRR算法少0.177%. 由于iwRR算法在調(diào)度過程中會從處理機池中放棄一個調(diào)度結(jié)束時間最晚的處理機,在處理機數(shù)量較少的情況下,處理機池中的處理機數(shù)量變得更少,iwRR算法的優(yōu)勢不能體現(xiàn)出來,因此導(dǎo)致wRR算法性能總體上要優(yōu)于iwRR算法. 50000400003000020000100000iwRRwRR調(diào)度跨度/ms1000200400600800任務(wù)數(shù)/個iwRRwRR100020040060080035000300002500020000150001000050000任務(wù)數(shù)/個調(diào)度跨度/ms 圖3 任務(wù)調(diào)度跨度對比 圖4 任務(wù)調(diào)度跨度對比 2)6個處理機 6個處理機情況下兩種算法任務(wù)調(diào)度跨度對比情況如圖4所示,iwRR算法在不同任務(wù)數(shù)情況下,任務(wù)調(diào)度跨度要比wRR算法短,iwRR算法的性能總體上要優(yōu)于wRR算法,iwRR算法任務(wù)調(diào)度跨度要比wRR算法最小少0.98%,最高少9.98%,iwRR算法的優(yōu)勢在處理機數(shù)量較多的情況較好地體現(xiàn)了出來. 通過對wRR算法的改進(jìn),提出了一種改進(jìn)的iwRR獨立任務(wù)調(diào)度算法,在相同的實驗環(huán)境下,利用測試數(shù)據(jù)集對任務(wù)集進(jìn)行調(diào)度,得出兩種算法的任務(wù)調(diào)度跨度,得出在處理機數(shù)量較少的情況下,wRR算法要優(yōu)于iwRR算法,但優(yōu)勢并不明顯;而當(dāng)處理機數(shù)量較大時,iwRR算法明顯優(yōu)于wRR算法. 對iwRR算法進(jìn)一步完善,將iwRR算法應(yīng)用于在線任務(wù)調(diào)度問題以及相關(guān)任務(wù)調(diào)度問題. 另外,在真實異構(gòu)環(huán)境中對獨立任務(wù)進(jìn)行調(diào)度是后續(xù)需要進(jìn)一步研究的問題.3 實驗分析
3.1 測試數(shù)據(jù)集
3.2 實驗結(jié)果分析
4 結(jié)束語