一種基于統計思想的網格負載平衡調度算法
2009-01-01 00:00:00魯斌張紅彬
計算機應用研究 2009年3期
(華北電力大學 計算機科學與技術學院， 河北 保定 071003)
摘 要：針對層次化網格模型結構，運用統計思想提出了一種新的資源分配與任務調度算法，不僅能夠提高資源的利用率和系統的吞吐率，而且能夠實現網格系統內部的負載平衡。算法主要包含三個功能模塊，即負載跟蹤模塊、作業分配模塊和負載監視模塊。在解釋了方案中各功能部件的作用及其相互之間關系的基礎上，給出了相應的算法偽碼。仿真實驗表明，該算法是有效的。
關鍵詞：網格計算； 層次化； 任務調度； 負載平衡
中圖分類號：TP301.6 文獻標志碼：A
文章編號：10013695(2009)03089703
Grid load balancing scheduling algorithm based on statistics thinking
LU Bin， ZHANG Hongbin
(School of Computer Science Technology， North China Electric Power University， Baoding Hebei 071003， China)
Abstract:Aiming at the hierarchical grid model structure， following statistical thinking， this paper proposed a new resource allocation and task scheduling algorithm， which could not only increase the utilization of resources and system throughput， but also realize the load balancing within grid systems. This algorithm consisted of three main modules which were load tracking module， job distributing module and load monitoring module. On the basis of having explained the functions of the different functional parts and the relationships between them， gave the corresponding pseudocode algorithms. The results of simulative experiments show that the algorithm is effective.
Key words：grid computing; hierarchical; task scheduling; load balancing
網格是構筑在互聯網上的一組新興技術，把整個互聯網整合成一臺巨大的超級計算機，實現資源全面共享。這樣組織起來的虛擬的超級計算機有兩個優勢：數據處理能力超強；充分利用網上的閑置處理能力，去完成用戶提交的任務。顯然這種“螞蟻搬山”的方式將具有很強的數據處理能力[1]。因此，網格計算系統的發展與數據密集、大規模應用的發展相吻合，具有旺盛的生命力，發展前景良好。
網格資源管理與任務調度作為網格計算領域核心技術之一，自然成為國內外學者研究的熱點，已有大量的研究成果出現。其中，網格計算項目SETI@home是最有影響的項目之一，采用主—從模式進行任務調度；文獻[2]討論了具有大量任務數的一類應用在網格系統中的資源管理和控制問題，提出了具有層次化結構的資源分配與任務調度模型；文獻[3]結合已有的調度策略，提出了一種新的改進調度策略的三級模式。這方面的成果還有不少[4，5]，分別從不同角度針對不同問題（如任務劃分、資源發現、通信延遲、負載均衡等）進行了研究。需要指出的是，在異構網格和分布式并行計算環境下的大部分任務調度問題都是NP難題[6]，目前的研究雖取得了一定的成果，但仍很有限，進一步的研究是必要的。
本文工作基于層次化網格結構模型展開，重點討論網格資源的分配與任務調度策略，運用統計思想提出了一種新的資源分配與任務調度算法，不僅能夠提高資源的利用率和系統的吞吐率，而且能夠實現網格系統內部的負載平衡。本文首先闡述了層次化模型的結構；然后詳細分析了基于統計思想的網格資源分配與任務調度策略，并輔以偽碼實現；最后采用Gridsim 仿真工具進行模擬比較實驗，結果表明所提算法是有效的。
1 層次化網格模型
在分層的資源管理結構模型中，資源管理與調度是多級的，每個資源有自己的調度子系統，用戶只需把作業提交給網格資源管理器，而網格資源管理器后有多少資源提供者，以及該作業分配哪個資源，對于用戶來說都是透明的。資源提供者可以是單個PC機，可以是單個集群或多個集群，也可以是某個組織的一個中小型局域網。它們都有一個共同點， 即都有一個管理者——域資源管理器。單個PC機本身就是一個管理者；而集群和局域網一般都有一臺服務器專職管理內部各節點。用戶作業在網格資源管理器上進行一級調度，在域資源管理器上進行二級調度，如果下面存在更多的集群或局域網，則存在三、四級等多級調度。
圖1描述了模型的結構，它表明了模型中的各個部分和它們之間的層次關系。
2 網格資源分配與任務調度
本文將主要探討網格資源分配與任務調度策略，綜合考慮了域資源管理器和計算節點當前的負載平衡、執行性能以及作業數量等信息，采用統計思想以偽碼形式實現了該算法。
2.1 負載定義
為了更好地描述網格負載平衡算法，可將節點的負載狀態刻畫為輕載、重載和適度三種。其中一個計算節點是重載的(即繁忙的)，主要是指該節點的CPU利用率高、CPU就緒隊列長度長等。本文在這里規定兩個閾值Llow、Lhigh。該節點的負載超過規定的閾值Lhigh時，說明該節點的負載是重載。相應地，一個計算節點是輕載的(即空閑的)，主要是指該節點的CPU利用率低、CPU就緒隊列長度短等，該節點的負載均低于規定的閾值Llow時，說明這個節點的負載是輕載。一個計算節點是適度的是指該節點處于輕載和重載之間的一種狀態，此時該節點上的負載比較均衡，介于Llow、Lhigh之間，CPU利用率適度、CPU就緒隊列長度也不長等。
2.2 算法分析與實現
網格資源管理器集中接收所有用戶提交的作業請求，根據任務性質、通信狀況和各資源負載情況進行粗粒度調度，按照此算法尋求最佳分配方案，將任務提交給選中的域資源管理器。該算法主要由負載跟蹤模塊（load tracing module）、作業分配模塊(job distributing module)、負載監視模塊(load monitor module)三部分組成。為了實現算法，在網格資源管理器和域資源管理器上設置三張表：第一張表存放的是所有次級域資源管理器的負載信息，對于沒有次級域資源管理器的情形，即該資源管理器直接管理計算節點，則表中不僅存放各個計算節點的負載信息，而且存放計算資源的詳細數據，如CPU速度、CPU利用率、活動進程數、內存使用情況、I/O使用情況等；第二張表存放各個次級域資源管理器或計算節點正在處理的作業數；第三張表中的內容為各個域資源管理器或計算節點的吞吐率和平均應答延遲。
2.2.1 負載跟蹤模塊
該模塊用于得到各域資源管理器及計算節點的負載信息，周期性地監視作業的執行狀態，并向上一級資源管理器匯報，以便進行全局管理與調度。域資源管理器向網格資源管理器匯報它的負載信息，以及域資源管理器上運行的所有作業狀態或作業結束信息。當任務途中異常中斷或執行性能比預期要差時，網格資源管理器可進行再次調度，重新安排其他資源；當任務完成時，網格資源管理器會要求域資源管理器直接將作業結果返還給用戶，更新各資源管理器的當前作業數，同時根據計算節點的負載信息對各個域資源管理器進行數據更新。
2.2.2 作業分配模塊
動態作業分配用于網格資源管理器根據負載平衡選擇合適的域資源管理器進行作業分配。網格系統中，作業是動態產生的，作業分配算法是系統中最重要的算法，涉及網格資源分配與任務調度兩個方面。這里考慮的負載指標主要包括計算節點當前各項資源的使用情況，如CPU利用率、內存使用情況等?？梢造o態或動態地確定計算節點各項負載指標的權重，然后采用加權平方和方法計算該節點的負載。
節點負載的計算公式如下：
Li=∑nj=1ajL2ij(1)
其中:Li表示第i個計算節點的負載大?。籐ij為各項負載指標值；n表示負載指標個數；ai為相應權重。一般規定ai≥0且∑ai=1。
域資源管理器的負載可以根據次級域資源管理器或計算節點的負載取平均值得到，即
LDk=（1/m） ∑mi=1 Li(2)
其中：LDk表示第k個域資源管理器的負載大小；Li為該域中第i個次級域資源管理器或計算節點的負載大??；m表示該域中次級域資源管理器或計算節點的個數。
另外，在同一層次內，為合理選擇調度資源，當具有最小負載的域資源管理器或計算節點不惟一時，可通過計算負載的方差進一步判斷，即
varDk(L)=E[(Li-LDk)2](3)
其中：varDk表示第k個域資源管理器的負載方差；E為數學期望值運算。
作業分配算法如下，其具有負載消息的處理和作業分配的功能。
初始化；
for( ；；)
{do
{if(有來自域資源管理器或計算節點的消息)
/*域資源管理器定時更新負載及作業狀態信息*/
{
據式(1)~(3)更新域資源管理器或計算節點的負載信息；
計算吞吐率；
計算平均應答延遲；
if(有作業結束信息)
{相應域資源管理器作業數減1；}
}
if(用戶將作業交給網格資源管理器)
{
/*逐層按下述步驟執行*/
/*首先，計算同一層次最小負載值*/
Lmin=minK Lk
/*其次，根據負載為Lmin的節點個數分別予以處理*/
if(負載為Lmin的節點不惟一)
{
/*在負載為Lmin的節點中找出方差最大的節點*/
varmax=maxLDK=Lmin varDK
將方差為varmax的節點作為調度節點，若仍然不惟一，則選擇第一個節點即可；
}
else
{將負載為Lmin的節點作為調度節點；}
將作業交給其進行調度；
更新域資源管理器作業數；
}
}
}
2.2.3 負載監視模塊
負載監視用于監視各域資源管理器的當前負載是否過重或過輕并采取相應的措施。域資源管理器負載大小超過預定閾值時，該算法被觸發。當監視模塊檢測到各域資源管理器負載過大或過小時，通過啟用或撤下域資源管理器，從而達到系統內的負載平衡。
a)當所有資源管理器的負載都超過一定的閾值Lhigh時，說明各管理器的負載過重，負載監視模塊會自動啟用備用資源管理器。
b)如果所有代理的負載都低于一定的閾值Llow時，說明各管理器的負載過輕，負載監視模塊會撤下部分域資源管理器，將這些代理加入備用資源管理器列表，不再給它們分配作業。
監視模塊自動啟用或撤下域資源管理器的算法偽碼如下：
初始化；
for( ；；)
{if(sum /*bm是控制域資源管理器最少數目的常數，用于確定在同一時間內最少運行的域資源管理器數目*/ {啟用備用資源管理器；} 讀取各域資源管理器負載數據； 讀取配置文件中規定的上下閾值； if(負載均超過Lhigh) {啟用備用資源管理器；} if(負載均低于Llow) {撤下備用資源管理器；} else { 取出節點最近更新時間； if(當前時間－最近更新時間)>timeout) /*timeout為數據更新最長時間間隔*/ 說明域資源管理器失效，進行相應處理； } } 3 模擬實驗 算法提出后，需要進行驗證以確保其有效性。GridSim模擬工具可以對并行及分布式系統中的用戶、應用、資源和資源調度器等實體進行建模和模擬；它提供了創建用戶任務和不同類型的異構資源的方法，根據研究目的，可以模擬不同的資源分配和任務調度策略[7]。因此，這里采用GridSim進行算法模擬。 通過實驗對提出的負載平衡調度方法和選擇的兩種現有調度方法(MinMin算法、蟻群算法)的性能進行了對比。計算節點設為109個，并按照圖1結構配置了模擬環境，具體如表1所示。 分三次進行模擬實驗，分別指定任務的調度策略為MinMin算法、螞蟻算法和本文提出的算法，這樣任務調度引擎根據提交任務的不同策略進行調度。 實驗結果如圖2所示，采用本文算法執行任務所花費的時間明顯小于其他兩種算法，說明該算法是切實可行的。模型中各組成部件及其相互之間的關系在模擬器中都得到了很好的模擬。在模擬過程中，上面提到的資源分配與任務調度算法偽碼得到了很好的驗證。 4 結束語 有效的資源分配與任務調度方案對網格系統的性能提高能夠起到關鍵性的影響。本文基于層次式網格模型提出了一種統計負載平衡調度方案，在詳細分析負載平衡細節的前提下，設計并實現了一種綜合考慮各域資源管理器和計算節點負載、性能及任務數的作業分配算法。該算法具備如下特點：a)綜合考慮了網格所有節點的負載、性能及任務數，對進行有效的負載平衡提供了全面的參考依據；b)智能化監控節點負載，對計算資源的加入和退出進行動態管理，無須人工控制；c)用戶可在運行前根據作業種類的不同配置各項負載指標的權重，針對不同系統中的域資源管理器性能，用戶能在運行前設定閾值的大小。 在以后的研究中，筆者將引入粒度計算思想改進本文算法，進一步提高算法的靈活性和效率。 參考文獻： ［1］NAKADA H， SATO M， SEKIGUCHI S. Design and implementations of ninf：towards a global computing infrastructure[J].Future Generation Computing Systems， 1999， 15(56):649658. [2]黃瑾，金海，謝夏，等. 網格系統中的層次化資源分配與任務調度[J]. 華中科技大學學報：自然科學版，2006，34(10)：5154. [3]熊磊，李元香．網格計算資源調度策略的三級模式[J]. 計算機工程與應用，2005，41(1)：9698. [4]VEERAVALLI B， YAO J. Divisible load scheduling strategies on distributed multilevel tree networks with communication delays and buffer constrains[J]. Computer Communications， 2004， 27(1): 93110. [5]FOSTER I， KESSELMAN C， TUECKE S. The anatomy of the grid: enabling scalable virtual organizations[J]. International Journal of Supercomputer Applications， 2001，15(3):200222. [6]FOSTER I， KESSELMAN C. The grid: blueprint for a new computing infrastructure[M]. San Francisco: Morgan Kaufmann， 1999. [7]RAJKUMAR B， MANZUR M. GridSim: a toolkit for the modeling and simulation of distributed resource management and scheduling for grid computing[J]. Concurrency Computation：Pract Exper， 2002，14(1):11751220.
