基于負載平衡的任務(wù)調(diào)度算法

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

關(guān)鍵詞:任務(wù)調(diào)度;完成時間;負載平衡

中圖分類號:TP393文獻標(biāo)識碼: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

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

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

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

1 調(diào)度模型的建立

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

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

2)參與調(diào)度的異構(gòu)機器集合為H={h1，h2…h(huán)m}，其中hj代表的是機器j。

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

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

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

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

7)定義系統(tǒng)中有f個文件服務(wù)器或者數(shù)據(jù)倉庫，S={s1，s2……sf}。

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

2 算法描述

2.1 Min-min

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

假定T為所有未調(diào)度的任務(wù)的集合。

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

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

③ 根據(jù)②的結(jié)果，找出最早完成時間最小的那個任務(wù)ti和所對應(yīng)的機器hj;

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

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

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

⑦ 此次映射事件結(jié)束，退出程序。

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

2.2 Max-min

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

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

2.3 MM算法

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

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

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

MM算法的執(zhí)行過程如下:

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

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

③ 任務(wù)調(diào)度集合T是否為空，T不為空，執(zhí)行步驟③;否則到步驟⑦;

④ 若μ1<=0，μ>rlow，調(diào)用Min-min映射算法進行任務(wù)的映射;

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

若μ1>0，μ>rlow，調(diào)用Max-min映射算法進行任務(wù)的映射;

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

⑤ 更新向量r;

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

⑦ 算法結(jié)束。

2.4 算法分析

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

3 結(jié)束語

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

參考文獻:

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

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

[3] 謝志強，劉勝輝，喬佩利.基于ACPM和BFSM的動態(tài)Job-Shop調(diào)度算法[J].計算機研究與發(fā)展，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.