基于負載平衡的任務調度算法

摘要:分布式計算中，一個好的任務調度算法不但要考慮所有任務的完成時間，使其值盡量小，同樣要考慮到整個系統機器間的負載平衡問題。文章對異構計算環境下的原子任務調度算法進行了分析，針對Min-min算法可能引發的負載不平衡問題，結合分布式計算環境的特點，提出了一種適用于分布式計算的任務調度算法。

關鍵詞:任務調度;完成時間;負載平衡

中圖分類號:TP393文獻標識碼:A文章編號:1009-3044(2009)33-9269-03

An Algorithm for Tasks Scheduling Based on Laod Balance

YIN Lu

(Department of Computer Science， Huaiyin Instiute of Technology， Huaian 223001， China)

Abstract: In grid computing， a good algorithm for tasks scheduling should not only decrease the makespan of all tasks but also balance the load among the resources in the grid system. We first analyse the scheduling of meta-tasks in the heterogeneous environment， then according to the load imbalance question in the Min-min algorithm， propose an improved algorithm that suits to be used in the grid environment.

Key words: tasks scheduling; makespan; load balance

當今計算機技術已進入以網絡為中心的計算時代，大量的應用都圍繞著網絡進行，對服務器的性能和可靠性提出越來越高的要求。例如，隨著Internet的飛速發展和用戶的劇烈增長，比較熱門的Web站點會因為被訪問次數急劇增長而不能及時處理用戶的請求，導致用戶長時間地等待甚至遭到拒絕，大大降低了服務質量。對于CPU密集型的應用，比如說帶有數據庫操作的Web服務，服務器性能瓶頸問題則更加突出。為了解決服務器的性能問題，分布式計算的概念就應用而生。

分布式計算研究如何把一個需要非常巨大的計算能力才能解決的問題分成許多小的部分，然后再分配給許多計算機進行處理這些小的部分問題，最后把這些小部分問題所對對應的計算結果綜合起來得到最終的結果。由此可見，分布式計算所需的資源不僅有計算資源、存儲資源還要有通信資源。那么如何使用這些資源高效的完成計算任務是分布式系統的研究重點之一。這就涉及到了計算任務的調度的問題。對于普通用戶而言，它僅向分布式系統提交任務，但如何快速的完成這些任務，這就是調度程序要做的事情了。因此，分布式調度程序就是按照某種調度策略把用戶提交的任務分配給分布式系統中的可用資源的重要模塊，也是分布式計算的核心。

從上述分析可以看出，任務調度應該包括任務映射和調度兩個方面。任務映射是邏輯地為每個任務匹配一個最合適的機器，以便最小化應用程序的執行時間或完成時間。任務調度則將任務傳輸到其映射的機器上運行。但本文所講的任務調度主要強調的是前者即任務到資源的映射。以最小完成時間為優化目標的任務調度問題一直以來都是NP完全問題[1]，針對這類問題科學家做了大量努力，但至今未能見到一個有效的解決辦法，然而隨著計算機技術的發展并考慮到計算機計算能力的提高，所以在工程實踐應用中解決這類問題時，常采用貪心法又叫靜態啟發式算法，這類算法基本思想就利用計算機的快速性來進行窮舉，但隨著問題規模的增加其效能會降低太快，所以在實際應用中常采用動態啟發式算法，針對于異構計算環境中原子任務的調度，動態啟發式算法又分為在線模式啟發式算法和批模式啟發式算法。但這二個算法優點和缺點都比較明顯，前者會導致負載不平衡，而后者會導致分配時間增加。為此，本文提出了一種算法來結合二者的優點從而保證任務調度的快速性和負載平衡性。

1 調度模型的建立

為了較好的描述分布式計算中的任務調度問題，我們采用數學模型的方法進行形式化的描述。分布式環境中資源的范圍很廣泛，它指加入到分布式系統中、所有可被共享的資源。所到達的任務可能是計算型也可能是數據存儲型。為了描述問題的簡單，本文所指的任務包括兩類子任務:計算子任務和數據傳輸子任務。計算子任務是該任務中需要消耗計算資源的部分;傳輸子任務代表獲得計算所需輸入的數據通信即該任務中需要消耗存儲資源和通信資源的部分。不考慮任務之間的依賴性。有如下定義:

1)參與調度的任務集合為T={t1，t2…tn}，其中ti代表的是任務i。

2)參與調度的異構機器集合為H={h1，h2…hm}，其中hj代表的是機器j。

3)定義任務ti在機器hj上的期望執行時間eij為機器hj在不考慮其它負載情況下執行任務ti所需要的時間。

4)定義任務ti在機器hj上的期望完成時間cij為任務ti映射到機器hj上執行完的時間。

5)定義機器hj的期望就緒時間為rj，則向量r存儲了所有機器的期望就緒時間。

6)據(3)(4)(5)的定義有cij=rj+eij。

7)定義系統中有f個文件服務器或者數據倉庫，S={s1，s2……sf}。

8)定義矩陣data，dataij表示子任務vi向文件服務器或數據倉庫sj存取數據所需要的數據傳輸時間。

2 算法描述

2.1 Min-min

Min-min算法是一種實現起來很簡單的算法，算法的執行時間也很快，具有較好的性能。該算法的目的是將大量的任務指派給不僅完成它最早，而且執行它最快的機器。算法的思想是首先映射小的任務，并且映射到執行快的機器上。執行過程為:計算要參與映射事件的任務集中每個任務在各個機器上的期望完成時間，找到每個任務的最早完成時間及其對應的機器;從中找出具有最小最早完成時間的任務，將該任務指派給獲得它的機器;指派完成后，更新機器期望就緒時間并將已完成映射的任務從任務集合中刪除。重復上面的過程，直到所有的任務都被映射完。該算法形式化描述如下:

假定T為所有未調度的任務的集合。

① 判斷任務集合T是否為空，不為空，執行②;否則跳到步驟⑦;

② 對于任務集中的所有任務，求出它們映射到所有可用機器上的最早完成時間cij;

③ 根據②的結果，找出最早完成時間最小的那個任務ti和所對應的機器hj;

④ 將任務ti映射到機器hj上;并將該任務從任務集合中刪除;

⑤ 更新機器hj的期望就緒時間rj;

⑥ 更新其他任務在機器hj上的最早完成時間;回到①。

⑦ 此次映射事件結束，退出程序。

Min-min算法完成一次映射事件的時間復雜度為O(n2m)，其中n為一次映射事件需要完成映射的任務總數，m為可用的機器總數。

2.2 Max-min

Max-min啟發算法非常類似于上面提到的Min-min啟發算法。同樣要計算每一任務在任意可用機器上的最早完成時間。不同的是Max-min算法首先調度大任務。任務到資源的映射是選擇最早完成時間最大的任務映射到所對應的機器上。時間復雜度同Min-min一樣也為O(n2m)，其中n為一次映射事件需要完成映射的任務總數，m為可用的機器總數。

在Min-min算法中，每次都是選擇小任務映射到執行快的機器上，這種映射會使得更多的任務映射到某一臺或幾臺機器上，從而使得整個分布式系統中可用機器的負載不平衡。而Max-min算法同Min-min相反，它首先調度大的任務，一定程度上平衡負載。因此綜合這兩種算法的思想提出一種新的算法，該算法在對任務集合執行一次映射事件的過程中，會根據當前系統的負載平衡情況，動態的選擇Min-min算法和Max-min算法中的一種來進行任務資源的映射。在本文中，稱這種改進的新算法為MM算法。

2.3 MM算法

MM算法的思想借鑒于SA(Switching Algorithm)算法，SA是異構計算環境下，用來對任務進行在線模式映射的一種啟發式算法。

分布式計算環境中，任一資源mi的期望就緒時間為ri，設所有機器的最大期望就緒時間為rmax，最小的期望就緒時間為rmin;設變量μ表示系統中機器間的負載平衡指數，μ=rmin/rmax，顯然μ∈[0，1]。rmin=rmax=0，表明當前系統中所有機器都處于空閑狀態，等待著任務的映射;μ=0，表明當前系統中存在處于空閑狀態的機器;μ=1，表明當前系統中任務的分配基本處于平均狀態。在算法中，為了輪回的調用Min-min和Max-min算法，設定了兩個邊界值rlow和rhigh。映射事件開始時，初始化變量μ=1。首先使用Min-min算法，當變量μ的值下降到rlow時，改用Max-min算法;當變量μ的值上升到rhigh時，在改用Min-min算法。如此輪回調用這兩個啟發式算法，直到此次映射事件結束。

另外Min-min算法和Max-min算法所執行的均是原子任務到資源的映射。在分布式系統中，一個計算任務所需要的數據往往是存放在另一個地方的數據庫或數據倉庫中，也就是說將一個任務分為計算子任務和數據傳輸子任務更為合理。但此處我們不將任務劃分為更多的子任務，不考慮更多任務之間的依賴關系。對于分布式環境中包含計算子任務和數據傳輸子任務這樣的任務，在調用Min-min啟發算法或Max-min啟發算法的過程中，需要同時考慮任務的數據傳輸和計算在存儲資源和計算資源上的綜合性能，所以需要修改這兩個算法中求最短完成時間的部分。將傳輸和計算子任務看作一個整體，計算總的完成時間，并統一調度[7]，即確定使之最快完成的一對(存儲和計算)資源。

MM算法的執行過程如下:

① 初始化變量μ=1;初始化機器的期望就緒時間向量r;給變量rlow和rhigh設定初值;

② 定義變量μ1，該變量代表系統機器間負載平衡走向;初始化μ1<=0;

③ 任務調度集合T是否為空，T不為空，執行步驟③;否則到步驟⑦;

④ 若μ1<=0，μ>rlow，調用Min-min映射算法進行任務的映射;

若μ1<=0，μ=rlow，改用Max-min映射算法進行任務的映射;

若μ1>0，μ>rlow，調用Max-min映射算法進行任務的映射;

若μ1>0，μ=rhigh，改用Min-min映射算法進行任務的映射;

⑤ 更新向量r;

⑥ 更新變量μ和μ1，回到步驟③;

⑦ 算法結束。

2.4 算法分析

MM算法是在不影響Min-min的最小完成時間的前提下，為了降低由該算法所引發的系統中機器間負載不平衡問題而提出的。在MM算法中，對于每一任務在映射前，都要首先判斷系統的當前負載平衡指數，最壞的情況下需花費O(m)(m為系統中計算資源總數)，在每次映射中，調用Min-min或Max-min的時間復雜度均為O(mfn2)，其中m為系統中計算資源總數、f為系統中存儲資源總數。

3 結束語

本文介紹了異構計算環境下適用于原子任務調度的經典的批模式的啟發算法:Min-min和Max-min。針對Min-min算法可能引發的負載不平衡，采用輪回調度Min-min和Max-min的策略，生成了一種新的映射算法MM。在分布式計算環境下，資源更是處于一種異構的環境，并且計算資源和存儲資源等往往處于一種分布的狀態。更多的任務不在是原子任務，而是包含計算和數據傳輸兩部分。考慮任務的數據傳輸和計算在存儲資源和計算資源上的綜合性能，在MM算法中，修改了Min-min算法和Max-min算法中求最早完成時間的方法。對計算資源和存儲資源進行統一調度，更好的適應于分布式計算系統。最后在Matlab 7的仿真平臺下進行模擬實驗，仿真結果表明該算法確實可行有效。當然對于任何啟發式算法，其性能都受很多因素的影響。比如任務到達的速度，任務中長短任務的比例，任務中計算和數據傳輸比例等，所以值得改進的地方也還有不少，重點研究各個因素對MM算法性能的影響。

參考文獻:

[1] 王磊，黃文奇.求解工件車間調度問題的一種新的鄰域搜索算法[J].計算機學報，2005，28(5):60-67.

[2] 張德富，李新.求解作業車間調度問題的快速啟發式算法[J].計算機集成制造系統-CIMS，2005(2):89-93.

[3] 謝志強，劉勝輝，喬佩利.基于ACPM和BFSM的動態Job-Shop調度算法[J].計算機研究與發展，2003，40(7):79-85.

[4] Casanova H.Simgrid:a Toolkit for the simulation of Application Scheduling[C]. Proceedings of the 1st International Symposium on Cluster Computing and the Grid (CCGRID'01)， 2001.