喬保軍,張稼祥,左憲禹

(河南大學 河南省大數(shù)據分析與處理重點實驗室;計算機與信息工程學院,河南 開封 475004)

隨著技術的發(fā)展，互聯(lián)網中的數(shù)據激增，大量的數(shù)據將人們帶入了大數(shù)據時代[1].大數(shù)據時代的數(shù)據不僅數(shù)據量大，而且流動性強.為了獲取數(shù)據中的價值所在，早期的單機計算已無法有效地進行處理.目前為了處理大量的數(shù)據獲取其內在的價值，無論是在研究領域還是商業(yè)領域，云計算、網格計算等分布式技術已經成為人們的重點研究對象.通過這些分布式技術可以將大量的計算任務分配至多個資源上面同時計算，從而快速獲取所需的結果.保證數(shù)據的時效性，提高人們對數(shù)據的利用率.在分布式計算中，任務調度問題始終是一個重難點問題.任務調度通常指的是在分布式、云計算環(huán)境中，根據用戶的需求，合理地將N個任務分配至M個資源，實現(xiàn)整個計算系統(tǒng)的負載均衡,提高整體的資源利用率.從而提高任務的處理速度.在以往的研究中已經證明任務調度是一個NP難問題[2].通常任務調度的目標是提高系統(tǒng)資源的使用率，縮短任務完成時間.在目前大多數(shù)的研究中，都是對整體的任務完成時間進行優(yōu)化，而對算法時間復雜度的研究偏少.本文提出一個基于任務執(zhí)行時間的啟發(fā)式獨立任務調度算法，降低算法時間復雜度的同時，優(yōu)化整體任務完成時間.

1 相關研究工作

任務調度作為分布式計算中一直存在的一個研究熱點，目前已有大量的學者、專家對其做了大量的工作[3].根據任務之間依賴性，可以將任務調度分為獨立任務調度與工作流調度[4-5].本文主要針對獨立任務調度進行研究.有關任務調度的算法可以分為3類算法：啟發(fā)式算法、元啟發(fā)式算法[6-10]與混合式算法[11-13].相較于元啟發(fā)式算法與混合式算法，啟發(fā)式算法具有實現(xiàn)簡單、冪等性、算法執(zhí)行較快等優(yōu)點.故本文提出一種新的啟發(fā)式算法.

在啟發(fā)式算法中，比較著名的兩個算法是MIN-MIN算法[14]與MAX-MIN算法[15].在MIN-MIN算法中，第一步需要找到每一個任務的最小完成時間，然后再在這些具有最小完成時間的任務中找到具有最小最小完成時間的任務，將其分配至對應資源中.循環(huán)上述過程，直至所有的任務分配完成.在MIN-MIN算法的每次分配任務中，所有的資源的可用時間是一樣的，任務越小，則完成時間越小.故MIN-MIN算法優(yōu)先調度小任務.MAX-MIN算法與MIN-MIN算法極其相似，不同之處在于，MAX-MIN算法是從具有最小完成時間的任務中找到具有最大最小完成時間的任務，并將其分配至相應的資源.上述MIN-MIN算法優(yōu)先小任務調度，MAX-MIN算法優(yōu)先大任務調度.這就導致針對不同的任務類型，上述算法可能出現(xiàn)調度效果不理想的情況.為了解決上述問題，文獻[16]提出了MIN-MAX算法.MIN-MAX算法類似MIN-MIN算法與MAX-MIN算法的結合體.在MIN-MAX算法中，第一步與上述兩種算法相同.在第二步中，結合這兩種算法，分別找到最小最小完成時間與最大最小完成時間.將兩個任務進行捆綁分配.Sufferage算法[17]是對MIN-MIN算法的改進.在Sufferage算法中，不僅需要計算出每個任務的最小完成時間，還需計算出每個任務的次小完成時間，然后計算每個任務最小與次小完成時間的差值.選擇具有差值最大的任務，將此任務分配到使其具有最小完成時間的資源上.ETSA算法[18]屬于對Sufferage算法的進一步改進.不同之處在于，ETSA算法中，還需計算最小執(zhí)行時間與第二小執(zhí)行時間的差值.然后對完成時間的差值進行排序，根據完成時間的順序相應對執(zhí)行時間差值進行排序.如果完成時間的差值大于執(zhí)行時間的差值則將任務進行分配.文獻[19]提出了二階段的MIN-MIN算法，此算法主要根據MIN-MIN算法的調度結果，進行二次分配，轉移負載較高的資源中的任務至負載較低的資源，以此來達到負載均衡的目的.

上述算法在針對各自的問題上都取得了良好的效果,然而未能很好地平衡算法時間復雜度與調度結果，同時在面對某些類型的任務時調度效果不理想.本文提出的一種基于任務執(zhí)行時間的啟發(fā)式獨立任務調度算法可以較好地平衡時間復雜度與調度結果，同時兼顧各種類型任務調度.

2 任務調度算法模型

在介紹本文算法之前首先對相關符號、概念進行說明.

ETC(n*m)：任務執(zhí)行時間矩陣，二維矩陣，n個任務m個資源，每個任務在每個資源上面的執(zhí)行時間矩陣，在任務調度前已知.

ETC1：ETC矩陣分解的第一個矩陣，此矩陣行列有序，由ETC中的部分行組成.ETC1[i,j]表示任務i在資源j上面的完成時間.

ETC2：ETC矩陣分解的第二個矩陣，此矩陣中的元素無固定規(guī)律，由ETC矩陣中的部分行組成.ETC2[i,j]表示任務i在資源j上面的執(zhí)行時間.

CON：主要用于記錄某個任務對應的行是否有序.CON[i]=true表示任務i在ETC矩陣中對應的行為有序.

CON_NUM：ETC1矩陣中包含的任務數(shù).

TR：任務分配矩陣，二維矩陣.如果TR[i,j]=true，表明任務i分配至資源j上面.

CT：資源可用時間矩陣，表示當前資源在分配下一個任務時，需多長時間可執(zhí)行到要分配的任務.為了簡化模型，在本文中，每個資源的可用時間簡化為分配在資源上面的任務的執(zhí)行時間之和.CT[i]代表資源i的資源可用時間.

Rfrom,Rto：泛指需要進行任務調整的兩個資源，擬將Rfrom中的任務調整至Rto中.

MAKESPAN:表示通過算法調度之后完成所有任務的時間,為所有資源完成時間的最大值.

Ti：表示任務i.

Rj：表示資源j.

任務完成時間：某個任務的完成時間為某個資源的可用時間與此任務的執(zhí)行時間之和.某個資源的任務完成時間為分配至該資源所有的任務執(zhí)行時間之和.

本文提出的獨立任務調度算法主要由4個階段組成.分別為預處理階段、分解階段、預調度階段、調整階段.算法的輸入即為ETC矩陣，輸出的結果為每個資源上面的任務完成時間矩陣以及任務分配矩陣.為了便于理解，本文將整個算法按照上述4個階段分別進行介紹.第一個階段的輸入為整個算法的輸入為ETC矩陣，接下來的每個階段的輸入分別為上一個階段的輸出.接下來分別介紹上述4個階段.

2.1 預處理階段

在預處理階段，主要是對原始的ETC進行調整.調整的目的在于給下一階段矩陣分解做準備.給定一個ETC矩陣，ETC矩陣中的每一行代表一個任務在每個資源上面的執(zhí)行時間.每一列代表所有任務在某一個資源上面的執(zhí)行時間.針對ETC矩陣中的第一行元素，從小到大對第一行元素進行排序處理，整個ETC矩陣的每一行排列的順序與第一行元素的順序相同.即根據ETC矩陣的首行元素的大小，從小到大對每一行進行排序處理.之后，根據首列元素的大小再次進行ETC矩陣的重組.經過兩次重組后的矩陣即為分解階段的輸入，進行算法的下一步處理.預處理階段偽代碼如算法1所示.

算法1 預處理階段算法

輸入：(ETC,n,m)

輸出：(ETC)/*預處理后的ETC*/

1.fori←1 tondo

2. forj←1 ton-i-1 do

3. ifETC[0,j]>ETC[0,j+1]

4. swap(j,j+1)/*交換ETC矩陣兩列*/

5.fori←1 tomdo

6. forj←1 tom-i-1 do

7. ifETC[j,0]>ETC[j+1,0]

8. swap(j,j+1)/*交換ETC矩陣兩行*/

2.2 分解階段

在分解階段主要的功能是將經過預處理階段的ETC矩陣分解為ETC1和ETC2兩個矩陣.在預調度階段會對分解后的矩陣采取不同的調度策略.ETC1矩陣中，任意一行、一列都滿足從小到大的排列順序，即整個矩陣行列有序.而ETC2矩陣則沒有限制.在分解階段首先是將ETC矩陣中滿足從小到大順序的行標記出來，若此行有序則CON[i]=true，若無序則CON[i]=false.標記完成后，遍歷整個CON矩陣，找到第一個標記為true的行.然后從標記的第二行開始與標記的第一行進行比較，如果在所有資源上，第二行的執(zhí)行時間都大于第一行，接下來的比較行，則會變成標記的第三行與第二行進行比較，依次類推.如果第二行中有元素小于第一行中的元素，則將CON[i]設置為false.接下來的比較則會變成標記的第三行與第一行進行比較.按照上述規(guī)則，直至比較完成.接下來再一次遍歷CON矩陣，如果CON[i]為true，則將任務Ti對應的行添加至ETC1中，否則添加至ETC2中.分解階段偽代碼如算法2所示.

算法2 分解階段算法

輸入：(ETC,n,m)

輸出：(ETC1,ETC2)

1./*判斷ETC的每一行是否有序*/

2.fori←1 tondo

3. ifi行有序

4.CON[i]=true

5.CON_NUM=CON_NUM+1

6. ifCON_NUM==1

7.TASKID=i/*記錄第一個行有序的任務ID*/

8.fori←1 tondo

9. ifCON[i]

10. if 任務i在所有的資源上面的執(zhí)行時間都大于TASKID的執(zhí)行時間

11.TASKID=i

12. else if

13.CON_NUM=CON_NUM-1

14.CON[i]=false

15.fori←1 tondo

16. ifCON[i]

17. 將ETC[i]添加至ETC1中

18. else if

19. 將ETC[i]添加至ETC2中

2.3 預調度階段

在預調度階段，主要的任務就將按照不同的調度策略，分別將ETC1,ETC2矩陣進行調度.首先在對ETC1矩陣進行調度的時候，從ETC1最后一行開始，依次進行直至整個ETC1矩陣調度完成.找到最后一行任務的最早完成時間，然后將此任務分配至相應的具有最小完成時間的資源，更新資源可用時間，更新任務分配矩陣.根據更新的資源可用時間矩陣，繼續(xù)計算尋找下一行的最小完成時間，直至ETC1矩陣中的任務全部分配完成.此時，資源可用時間與任務分配矩陣已得到更新.其次開始對ETC2進行任務調度.對ETC2矩陣進行調度時，直接按照每個任務的最小執(zhí)行時間進行調度.即，遍歷ETC2矩陣中的每一行，然后找到當前任務在所有資源中具有最小執(zhí)行時間的資源，直接將當前任務分配至對應的資源，更新資源可用時間矩陣與資源分配矩陣.預調度階段偽代碼如算法3所示.

算法3 預調度階段算法

輸入：(ETC1,ETC2,CON_NUM,nm)

輸出：(CT,TR)

1./*首先對ETC1矩陣進行調度*/

2.fori←CON_NUM-1 to 1 do

3. forj←1 tomdo

4.Ti在Rj上面具有最小完成時間

5. 更新CT矩陣CT[j]=CT[j]+ETC[i,j]

6. 更新TR矩陣TR[i,j]=true

7./*對ETC2矩陣進行調度*/

8.fori←1 ton-CON_NUMdo

9. forj←1 tomdo

10.Ti在Rj上具有最小執(zhí)行時間

11. 更新CT矩陣CT[j]=CT[j]+ETC[i,j]

12. 更新TR矩陣TR[i,j]=true

2.4 調整階段

調整階段主要是根據預調度的結果對任務分配重新進行調整.在調整階段可以分為如下3個階段.

1)首先尋找兩個需要調整任務的資源Rfrom與Rto，擬將資源Rfrom上面的任務重新調整至Rto中.在尋找這兩個資源Rfrom與Rto時，最開始所找的是具有最大資源完成時間的資源為Rfrom，具有最小資源完成時間的資源為Rto，如果資源Rfrom中的任務可以分配至資源Rto中，那么下次進行尋找兩個資源時依舊是以最大資源完成時間的資源為Rfrom，以最小資源完成時間的資源為Rto.如果Rfrom上面的任務無法分配至Rto，那么下一次尋找時Rfrom依舊為最大資源完成時間的資源，而Rto則變?yōu)榫哂械诙〉馁Y源完成時間，后續(xù)依次類推.如果在Rfrom為最大完成時間時，遍歷了除Rto之外的所有資源依舊無法分配任務，再進行下一次尋找兩個資源時，則Rfrom變?yōu)榈诙筚Y源完成時間，而Rto依舊從最小資源完成時間開始.只要發(fā)生一次Rfrom上面的任務可以調整至Rto，那么尋找這兩個資源時，則Rfrom重新為最大完成時間資源，Rto為最小完成時間資源.

2)找到資源Rfrom中分配的任務在Rto中具有最小執(zhí)行時間的任務T.

3)如果將任務T調度至Rto中，Rto的資源完成時間小于之前Rfrom中的完成時間，則將任務T分配至Rto中.更新對應資源的任務完成時間以及任務分配矩陣.如果無法進行重新調度，則回到1)繼續(xù)尋找Rfrom與Rto.共進行n次循環(huán)即可結束.

調整階段偽代碼如算法4所示.

算法4 調整階段算法

輸入：(ETC,TR,CT,n,m)

輸出：(CT,TR)

1.fori←1 tondo

2. forj←1 tomdo

3. 找到需要重新調度的資源Rfrom,Rto

4. fori←1 tondo

5. 找到資源Rfrom中任務在Rto中具有最小執(zhí)行時間的任務Ti

6. if 任務Ti調整至資源Rto中,Rto的資源完成時間<資源Rfrom之前的資源完成時間

7. 更新資源可用時間CT

8. 更新任務分配矩陣TR

3 算法調度實例

現(xiàn)有3個資源R1，R2，R3，6個任務T1，T2，T3，T4，T5，T6.每個任務在每個資源上面的執(zhí)行時間已知.首先開始進行第一階段進行ETC矩陣的預處理.ETC矩陣如表1所示.

表1 ETC矩陣

按照ETC矩陣的第一列進行排序，排序后的矩陣如表2所示.按照ETC矩陣第一行進行排序，排序后的矩陣如表3所示.

表2 按照第一列排序后的ETC矩陣

表3 按照第一行排序后的ETC矩陣

第二階段將ETC矩陣分解為兩個矩陣.由表3可知，T1,T4,T6滿足從小到大排列.T2,T3,T5不滿足.故所對應的CON矩陣如表4所示.

表4 CON矩陣

遍歷CON矩陣，第一個為true的任務為T1，第二個為true的任務為T4.任務T4對應的行與任務T1對應的進行比較.經過比較可知，在每一個資源上面，任務T4的執(zhí)行時間都要大于任務T1的執(zhí)行時間.故，將任務T1，T4添加至ETC1中.第三個標記為true的任務為T6.T6與任務T4進行比較.經過比較可知，任務T6在每個資源上面的執(zhí)行時間都要大于T4.故將T6加入ETC1中.遍歷完成后，原始的ETC矩陣即可分解為ETC1，ETC2分解后的矩陣如表5、表6所示.

表5 ETC1矩陣

表6 ETC2矩陣

第三階段首先將ETC1矩陣進行調度，對ETC1矩陣進行調度的時，從T6任務開始調度.T6任務具有最小的完成時間為100，對應的資源為R1，故將T6分配至資源R1中.T6任務分配完成后，任務T4開始分配，T4在R3具有最小完成時間45 ms，將T4分配至R3.T1在R2中具有最小完成時間6 ms，故將任務T1分配至R2.ETC1矩陣調度完成后.開始對ETC2矩陣進行調度.ETC2中的矩陣，按照任務執(zhí)行時間的大小進行分配，任務T2，T3，T5都在R1中具有最小執(zhí)行時間.故將任務T2，T3，T5都分配至R1.第三階段分配完成后，任務分配結果圖如圖1所示.

第四階段為調整階段.第一輪的調整，具有最大完成時間的資源為R1，具有最小完成時間的資源為R2，現(xiàn)在將分配至R1中的任務調整至R2中.R1中的任務在R2中具有最小執(zhí)行時間的任務為T2，T2在R2上的執(zhí)行時間為2.若將T2分配至R2，則R2中的完成時間為8，而R1之前的完成時間為166.8 ms(小于166)，故將任務T2調整至R2.第一輪調整后的任務分配圖如圖2所示.在本次實例中共進行6輪調整，最終R1任務完成時間為100 ms，R2完成時間為100 ms，R3完成時間為97 ms.最終任務分配圖如圖3所示.

4 仿真與結果分析

在文獻[20]中，根據資源與任務的異構性，將模擬仿真的ETC矩陣分為低任務異構-低資源異構、低任務異構-高資源異構、高任務異構-低資源異構、高任務異構-高資源異構4種.同時，根據整個ETC矩陣的一致性，將ETC矩陣分為非一致性、半一致性、一致性矩陣.共計12種ETC矩陣.在本文中的仿真實驗中，除了應用上述12種ETC矩陣外，還增加了另外八種不同的ETC矩陣.這8種ETC矩陣中，每個任務的執(zhí)行時間主要由任務大小除以資源處理能力得到.低異構資源處理能力的大小在[1,100]均勻分布隨機產生，高異構資源處理能力的大小在[1,1 000]均勻分布隨機產生.低異構任務大小在[1 000,10 000]均勻分布隨機產生，高異構任務大小在[1 000,300 000]均勻分布隨機產生.在這8種ETC矩陣中根據ETC矩陣的一致性分為，特殊一致性矩陣與特殊半一致性.特殊一致性主要是與一致性矩陣進行區(qū)分.特殊半一致性矩陣主要與半一致性矩陣進行區(qū)分.一致性矩陣主要指的是，如果任務Ti在資源Rn中的執(zhí)行時間小于Rm中的執(zhí)行時間，那么所有的任務在Rn中的執(zhí)行時間要小于Rm的執(zhí)行時間.在模擬的ETC矩陣中表現(xiàn)為行有序.本文中所提的特殊一致性，指的是不僅滿足一致性的條件，還要滿足，如果任務Ti在某一資源上的執(zhí)行時間小于任務Tj執(zhí)行時間，那么在所有的資源上面任務Ti執(zhí)行時間小于Tj執(zhí)行時間.在ETC矩陣中，特殊一致性矩陣表現(xiàn)為行列有序.特殊半一致性矩陣，指的是，ETC矩陣中，一半任務滿足本文所提的特殊一致性，一半不滿足特殊一致性.在構造特殊半一致性矩陣時，通過隨機打亂特殊一致性矩陣中一半的行來實現(xiàn).

4.1 實驗環(huán)境

實驗環(huán)境：CPU主頻3.40 GHz，硬盤：1 T，內存：16 GB，操作系統(tǒng)：Windows10 64位.

開發(fā)環(huán)境：開發(fā)平臺為Eclipse，開發(fā)語言為Java.

4.2 結果分析

本文實驗是在上述模型與實驗環(huán)境下進行的，選擇16個資源，256個任務產生的ETC矩陣.在上述基礎上比較MIN-MIN算法、MAX-MIN算法、本文算法.比較的結果為完成所有任務的時間MAKESPAN.每一種ETC矩陣產生4種最后求得4種調度結果的平均值為算法在某一ETC矩陣下的調度結果.圖4至圖7為根據文獻[20]提出的模擬數(shù)據實驗的結果.圖8至圖11為本文添加的8種ETC矩陣的調度結果.

與MIN-MIN算法進行比較.觀察圖5與圖7，由一致性矩陣、半一致性矩陣與高任務異構-高資源異構、低任務異構-高資源異構所組合成的4種條件下，本文算法MAKESPAN明顯高于MIN-MIN算法的MAKESPAN，由此可以得出結果，在上述條件下MIN-MIN算法明顯優(yōu)于本文所提出的算法.觀察圖4與圖6，由半一致性矩陣與低任務異構-低資源異構、高任務異構-低資源異構組合的兩種條件下，本文算法與MIN-MIN算法相差無幾.觀察圖4至圖11，除上述6種情況外，在余下的14種情況下，本文MAKESPAN均低于MIN-MIN算法的MAKESPAN.

與MAX-MIN算法進行比較，觀察圖8至圖11.矩陣為特殊一致性矩陣條件下，無論異構性大小，本文算法的MAKESPAN與MAX-MIN算法的MAKESPAN相同.由此可以得出結論，在特殊一致性矩陣的4種條件下本文算法與MAX-MIN算法調度結果相同.觀察圖10，在特殊半一致性-高任務異構-低資源異構條件下，本文算法的MAKESPAN高于MAX-MIN算法的MAKESPAN，說明在此條件下，MAX-MIN算法要優(yōu)于本文算法.觀察圖4至圖11，除上述5種情況，其余15種條件下，本文算法調度結果都要優(yōu)于MAX-MIN算法調度結果.

除上述之外，觀察圖4至圖11可以發(fā)現(xiàn)，本文提出的算法無論在那種情況下都不會出現(xiàn)極差的結果，相比MIN-MIN,MAX-MIN調度結果更加平穩(wěn)，表明本文算法的適應性也要優(yōu)于上述算法.

4.3 時間復雜度分析

在本文算法中，預處理階段需要對行與列進行排序，預處理階段的時間復雜度為O(n2).分解階段包含雙重迭代，時間復雜度為O(n*m).預調度階段包含雙重迭代時間復雜度為O(n*m).調整階段包含雙重迭代，時間復雜度為O(n2).因此本文算法時間復雜度為MAX(O(n2),O(n*m)).在MIN-MIN,MAX-MIN算法中包含三重迭代，他們的時間復雜度都為O(n2m).本文算法時間復雜度要優(yōu)于上述兩個算法.

圖12展示了模擬10 000個任務分別在16,32,64,128,256節(jié)點下的算法執(zhí)行時間.MIN-MIN,MAX-MIN的計算時間幾乎相當，這是因為其時間復雜度均為O(n2m).在本節(jié)的實驗中本文算法的計算時間分別是MIN-MIN或者MAX-MIN的計算時間的50.4%，32.0%，25.7%，18.0%，15.0%，與算法復雜度的理論結果MAX(O(n2),O(n*m))/O(n2m)并不一致.因為時間復雜度主要反映了程序執(zhí)行時間隨輸入規(guī)模增長而增長的量級.但從圖12中可以發(fā)現(xiàn)，本文算法隨著節(jié)點個數(shù)的增加，算法執(zhí)行時間的增長幅度明顯弱于MIN-MIN與MAX-MIN算法. 圖13展示了模擬128個節(jié)點分別在2 000,4 000,6 000,8 000,10 000任務下的算法執(zhí)行時間.從圖13中也可發(fā)現(xiàn)，本文算法隨著任務個數(shù)的增加，算法執(zhí)行時間的增長幅度也要明顯弱于MIN-MIN與MAX-MIN算法.

5 結束語

MIN-MIN,MAX-MIN算法是獨立任務調度中常見的算法.針對上述算法時間復雜度高以及調度結果不理想的等問題,本文提出了一種基于任務執(zhí)行時間的啟發(fā)式獨立任務調度算法.在降低分配算法時間復雜度的前提下，改善任務調度結果，縮短整體的任務完成時間.在本文提出的20種任務類型下，大多數(shù)條件下本文算法調度結果要優(yōu)于上述兩種算法.此外,優(yōu)化分解階段和調整階段，解決個別條件下本文算法劣于上述兩種算法的情況，將是下一步工作的重點.