一種改進(jìn)的wRR獨(dú)立任務(wù)調(diào)度算法研究

劉林東

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

0 引言

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

1 問題描述

1.1 任務(wù)描述

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

表1 任務(wù)在處理機(jī)上的執(zhí)行開銷

ms任務(wù)P0P1P2P3t0200211180223t110212291130t281928895t355595761t432332936t5155160149173t6135142122160

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

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

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

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

為解決wRR算法在獨(dú)立任務(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)度模型包括處理機(jī)池初始化和任務(wù)調(diào)度兩個(gè)階段，如圖2所示. 處理機(jī)池中的處理機(jī)均被調(diào)度之后，根據(jù)隊(duì)列中的任務(wù)調(diào)度請(qǐng)求，處理機(jī)調(diào)度模塊根據(jù)當(dāng)前處理機(jī)的調(diào)度情況，將任務(wù)調(diào)度結(jié)束時(shí)間最晚的處理機(jī)Pj從處理機(jī)池中刪除，其余處理機(jī)均加入處理機(jī)池中；在任務(wù)調(diào)度階段，更新處理機(jī)池中的每個(gè)處理機(jī)的權(quán)值，然后按照wRR調(diào)度隊(duì)列中的所有任務(wù).

t0t4t1t3t2t5t6處理機(jī)集P處理機(jī)池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,處理機(jī)集P,任務(wù)在處理機(jī)上的執(zhí)行開銷T[n][m],權(quán)值w[m];

輸出：任務(wù)調(diào)度關(guān)系表S[n][m],任務(wù)調(diào)度跨度makespan,任務(wù)平均等待時(shí)間AWT;

初始化處理機(jī)池P;

while任務(wù)集T非空{(diào)

for(i=0;i

計(jì)算處理機(jī)Pi的結(jié)束時(shí)間E[i];

}

找出最小的E[j]對(duì)應(yīng)的處理機(jī)Pj;

從處理機(jī)池P中刪除處理機(jī)Pj;

for(i=0;i

計(jì)算每個(gè)處理機(jī)上分配的任務(wù)數(shù)ai;

}

對(duì)于當(dāng)前任務(wù)ti{

ifcj

調(diào)度任務(wù)到處理機(jī)Pj;

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

}

計(jì)算輸出makespan和AWT;

}

3 實(shí)驗(yàn)分析

為驗(yàn)證iwRR算法的性能，將iwRR算法與wRR算法在相同的實(shí)驗(yàn)條件下進(jìn)行性能比較，主要對(duì)任務(wù)調(diào)度跨度Makespan值進(jìn)行比較. 利用SimGrid[9-11]環(huán)境下的集群環(huán)境仿真分布式異構(gòu)環(huán)境，分布式異構(gòu)計(jì)算環(huán)境中的處理機(jī)對(duì)應(yīng)SimGrid中的處理機(jī)，對(duì)SimGrid模擬器進(jìn)行設(shè)置：處理機(jī)之間通過高速網(wǎng)絡(luò)互連；每個(gè)任務(wù)只能在1個(gè)處理機(jī)上執(zhí)行，且任務(wù)被調(diào)度后不能中止；每個(gè)處理機(jī)同時(shí)只能調(diào)度1個(gè)任務(wù)；處理機(jī)的任務(wù)調(diào)度性能異構(gòu).

仿真實(shí)驗(yàn)中的軟硬件環(huán)境為：Intel Core(TM) i5-8265U 1.6 1.8GHzCPU、4GB內(nèi)存硬件環(huán)境、操作系統(tǒng)為Ubuntu12.

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

iwRR算法輸入有兩個(gè)，分別是任務(wù)執(zhí)行時(shí)間矩陣和被調(diào)度任務(wù). 有兩種不同的任務(wù)集執(zhí)行時(shí)間矩陣，任務(wù)數(shù)均為10個(gè)任務(wù)，處理機(jī)數(shù)為4和6兩種情況；任務(wù)在處理機(jī)上的執(zhí)行開銷通過隨機(jī)程序生成；被調(diào)度任務(wù)集的任務(wù)數(shù)為50，100，…，1 000；任務(wù)編號(hào)通過程序隨機(jī)產(chǎn)生；任務(wù)到達(dá)時(shí)間為0.

3.2 實(shí)驗(yàn)結(jié)果分析

1)4個(gè)處理機(jī)

4個(gè)處理機(jī)情況下兩種算法任務(wù)調(diào)度跨度對(duì)比情況如圖3所示，iwRR算法在不同任務(wù)數(shù)情況下，任務(wù)調(diào)度跨度要比wRR算法長(zhǎng)，wRR算法的性能總體上要優(yōu)于iwRR算法，wRR算法任務(wù)調(diào)度跨度要比iwRR算法少0.177%. 由于iwRR算法在調(diào)度過程中會(huì)從處理機(jī)池中放棄一個(gè)調(diào)度結(jié)束時(shí)間最晚的處理機(jī)，在處理機(jī)數(shù)量較少的情況下，處理機(jī)池中的處理機(jī)數(shù)量變得更少，iwRR算法的優(yōu)勢(shì)不能體現(xiàn)出來，因此導(dǎo)致wRR算法性能總體上要優(yōu)于iwRR算法.

50000400003000020000100000iwRRwRR調(diào)度跨度/ms1000200400600800任務(wù)數(shù)/個(gè)iwRRwRR100020040060080035000300002500020000150001000050000任務(wù)數(shù)/個(gè)調(diào)度跨度/ms

圖3 任務(wù)調(diào)度跨度對(duì)比 圖4 任務(wù)調(diào)度跨度對(duì)比

2)6個(gè)處理機(jī)

6個(gè)處理機(jī)情況下兩種算法任務(wù)調(diào)度跨度對(duì)比情況如圖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ì)在處理機(jī)數(shù)量較多的情況較好地體現(xiàn)了出來.

4 結(jié)束語

通過對(duì)wRR算法的改進(jìn)，提出了一種改進(jìn)的iwRR獨(dú)立任務(wù)調(diào)度算法，在相同的實(shí)驗(yàn)環(huán)境下，利用測(cè)試數(shù)據(jù)集對(duì)任務(wù)集進(jìn)行調(diào)度，得出兩種算法的任務(wù)調(diào)度跨度，得出在處理機(jī)數(shù)量較少的情況下，wRR算法要優(yōu)于iwRR算法，但優(yōu)勢(shì)并不明顯；而當(dāng)處理機(jī)數(shù)量較大時(shí)，iwRR算法明顯優(yōu)于wRR算法.

對(duì)iwRR算法進(jìn)一步完善，將iwRR算法應(yīng)用于在線任務(wù)調(diào)度問題以及相關(guān)任務(wù)調(diào)度問題. 另外，在真實(shí)異構(gòu)環(huán)境中對(duì)獨(dú)立任務(wù)進(jìn)行調(diào)度是后續(xù)需要進(jìn)一步研究的問題.