一種改進的wRR獨立任務調度算法研究

劉林東

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

0 引言

分布式異構處理機環境中，按任務之間的依賴關系，可以將任務調度分為獨立任務調度[1-3]和相關任務調度[4-5]兩種，獨立任務調度的任務之間沒有相關性，任務調度沒有先后順序限制，也不存在數據通信；相關任務調度的任務存在先后關系，一般DAG圖對任務進行描述，且任務間存在數據通信. 常用的獨立任務調度算法包括RR[6]、wRR、LC、Min-Min、Min-Max、Sufferage以及遺傳算法[7]等，wRR調度算法[8]通過隊列優先級來區別對待不同QoS需求的任務調度，沒有考慮異構處理器的計算性能對不同優先級隊列的公平性的影響.

1 問題描述

1.1 任務描述

分布式異構環境中任務集T包括n個獨立任務，分別為t0,t1,…,tn-1，處理機集P包括m個性能異構的處理機，分別為P0,P1,…,Pm-1，表1描述了7個任務在4個處理機上執行開銷. 設任務ti被調度的處理機不受限制，每個處理機同時只能調度1個任務，1個任務不能在多個處理機上調度. 如何將n個獨立任務調度到m個處理機，且滿足任務集T在處理機集P上的執行跨度、平均等待時間優于同類算法是文中需要主要研究的問題.

表1 任務在處理機上的執行開銷

ms任務P0P1P2P3t0200211180223t110212291130t281928895t355595761t432332936t5155160149173t6135142122160

1.2 wRR任務調度算法

w0w1w2w3P0P1P2P3t0t1t2t3t4t5t6Q0Q1Q2Q3a.隊列調度b.處理機調度t4t0t1t2t3t5t6P0P1P2P3

圖1 wRR算法任務調度

2 任務調度模型及算法

為解決wRR算法在獨立任務調度過程中出現的問題，提出一種改進的任務調度模型及iwRR任務調度算法.

2.1 任務調度模型

帶閾值的加權輪轉任務調度模型包括處理機池初始化和任務調度兩個階段，如圖2所示. 處理機池中的處理機均被調度之后，根據隊列中的任務調度請求，處理機調度模塊根據當前處理機的調度情況，將任務調度結束時間最晚的處理機Pj從處理機池中刪除，其余處理機均加入處理機池中；在任務調度階段，更新處理機池中的每個處理機的權值，然后按照wRR調度隊列中的所有任務.

t0t4t1t3t2t5t6處理機集P處理機池P1wRR算法任務調度模塊任務集T

圖2 改進的加權輪轉調度模型

2.2 任務調度算法

改進的加權輪轉調度算法iwRR算法如下：

輸入：任務集T,處理機集P,任務在處理機上的執行開銷T[n][m],權值w[m];

輸出：任務調度關系表S[n][m],任務調度跨度makespan,任務平均等待時間AWT;

初始化處理機池P;

while任務集T非空{

for(i=0;i

計算處理機Pi的結束時間E[i];

}

找出最小的E[j]對應的處理機Pj;

從處理機池P中刪除處理機Pj;

for(i=0;i

計算每個處理機上分配的任務數ai;

}

對于當前任務ti{

ifcj

調度任務到處理機Pj;

elsej=(j+1)mod(m-1);

}

計算輸出makespan和AWT;

}

3 實驗分析

為驗證iwRR算法的性能，將iwRR算法與wRR算法在相同的實驗條件下進行性能比較，主要對任務調度跨度Makespan值進行比較. 利用SimGrid[9-11]環境下的集群環境仿真分布式異構環境，分布式異構計算環境中的處理機對應SimGrid中的處理機，對SimGrid模擬器進行設置：處理機之間通過高速網絡互連；每個任務只能在1個處理機上執行，且任務被調度后不能中止；每個處理機同時只能調度1個任務；處理機的任務調度性能異構.

仿真實驗中的軟硬件環境為：Intel Core(TM) i5-8265U 1.6 1.8GHzCPU、4GB內存硬件環境、操作系統為Ubuntu12.

3.1 測試數據集

iwRR算法輸入有兩個，分別是任務執行時間矩陣和被調度任務. 有兩種不同的任務集執行時間矩陣，任務數均為10個任務，處理機數為4和6兩種情況；任務在處理機上的執行開銷通過隨機程序生成；被調度任務集的任務數為50，100，…，1 000；任務編號通過程序隨機產生；任務到達時間為0.

3.2 實驗結果分析

1)4個處理機

4個處理機情況下兩種算法任務調度跨度對比情況如圖3所示，iwRR算法在不同任務數情況下，任務調度跨度要比wRR算法長，wRR算法的性能總體上要優于iwRR算法，wRR算法任務調度跨度要比iwRR算法少0.177%. 由于iwRR算法在調度過程中會從處理機池中放棄一個調度結束時間最晚的處理機，在處理機數量較少的情況下，處理機池中的處理機數量變得更少，iwRR算法的優勢不能體現出來，因此導致wRR算法性能總體上要優于iwRR算法.

50000400003000020000100000iwRRwRR調度跨度/ms1000200400600800任務數/個iwRRwRR100020040060080035000300002500020000150001000050000任務數/個調度跨度/ms

圖3 任務調度跨度對比 圖4 任務調度跨度對比

2)6個處理機

6個處理機情況下兩種算法任務調度跨度對比情況如圖4所示，iwRR算法在不同任務數情況下，任務調度跨度要比wRR算法短，iwRR算法的性能總體上要優于wRR算法，iwRR算法任務調度跨度要比wRR算法最小少0.98%，最高少9.98%，iwRR算法的優勢在處理機數量較多的情況較好地體現了出來.

4 結束語

通過對wRR算法的改進，提出了一種改進的iwRR獨立任務調度算法，在相同的實驗環境下，利用測試數據集對任務集進行調度，得出兩種算法的任務調度跨度，得出在處理機數量較少的情況下，wRR算法要優于iwRR算法，但優勢并不明顯；而當處理機數量較大時，iwRR算法明顯優于wRR算法.

對iwRR算法進一步完善，將iwRR算法應用于在線任務調度問題以及相關任務調度問題. 另外，在真實異構環境中對獨立任務進行調度是后續需要進一步研究的問題.