劉林東

(廣東第二師范學(xué)院 計算機科學(xué)系， 廣東 廣州 510303)

0 引言

分布式異構(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)先級隊列的公平性的影響.

1 問題描述

1.1 任務(wù)描述

分布式異構(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

1.2 wRR任務(wù)調(diào)度算法

w0w1w2w3P0P1P2P3t0t1t2t3t4t5t6Q0Q1Q2Q3a.隊列調(diào)度b.處理機調(diào)度t4t0t1t2t3t5t6P0P1P2P3

圖1 wRR算法任務(wù)調(diào)度

2 任務(wù)調(diào)度模型及算法

為解決wRR算法在獨立任務(wù)調(diào)度過程中出現(xiàn)的問題，提出一種改進(jìn)的任務(wù)調(diào)度模型及iwRR任務(wù)調(diào)度算法.

2.1 任務(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)度模型

2.2 任務(wù)調(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;

}

3 實驗分析

為驗證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.

3.1 測試數(shù)據(jù)集

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.

3.2 實驗結(jié)果分析

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)了出來.

4 結(jié)束語

通過對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)一步研究的問題.