一種網格環境下的多級資源調度策略

摘要：網格計算是近年來得到快速發展的技術，其目標是把因特網整合成一種超大規模的巨大計算機系統，以實現各種資源的全面共享，闡述了網格調度的基本概念，分析了各種資源調度策略，并提出一種基于分布式調度算法的多級資源調度策略。通過對模擬仿真實驗中三種技術指標的分析，表明了該算法的高效性。

關鍵詞：網格；任務調度；調度算法

中圖分類號：TP301文獻標識碼：A文章編號：1009-3044(2008)32-1046-03

A Multi-level Resource Scheduling Strategy in a Grid Environment

XUE Dong-min

(Shanxi Water Techical Professional College， Yuncheng 044000， China)

Abstract: Grid computing is a new fast developing technique recently. Its objective is to combine internet into a whole very large-scale computer system in order to share all kinds of resources. Also， the concept of grid scheduling is introduced，all kinds of resources schedule strategy is analyzed， and a multi-level resource schedule strategy based on distributed scheduling algorithm is provided. This algorithm is proved to be effective by simulation experiments.

Key words: Grid; Task scheduling; Scheduling algorithm

1 引言

網格是利用互聯網把地理上廣泛分布的各種資源（包括計算資源、存儲資源、帶寬資源、軟件資源、數據資源、信息資源、知識資源等）連成一個邏輯整體，為用戶提供一體化信息和應用服務（計算、存儲、訪問等），虛擬組織最終實現在這個虛擬環境下進行資源共享和協同工作，最充分的實現信息共享。網格是一個集成的計算與資源環境，網格技術使得計算機網絡成為單個統一強大的計算機資源。

雖然網格技術經歷了數年的發展，并且出現了一些研究成果，但是還有很多的問題亟待解決，例如資源管理中的資源調度問題就是其中之一。由于網格系統存在著復雜性，一個優秀的資源調度算法就顯得至關重要，高效的調度策略可以充分地利用網絡資源和網格系統的處理能力，從而提高系統吞吐量和利用率。下文對一些主要的資源調度算法進行了分析與研究。

2 網格調度模型

2.1 網格任務調度

網格實質上是一種具有巨大計算功能的分步式系統，具有分布、異構和動態的特性， 將應用程序調度到異構的計算節點上運行，以獲得最優性能是應用程序調度模型研究的目標和方向。任務調度的過程就是將任務發送到指定機器上的執行隊列的過程，進入執行隊列的任務會被宿主機自動地啟動執行，在動態調度系統中，每個到達的任務根據任務映射算法分配到合適的機器上后，就立即進行調度。

2.2 網格任務調度算法分析

資源調度是資源管理中的核心問題，重要性也顯而易見。同時由于網格本身的特性，它也是資源管理中最困難的部分。基于此，目前已提出了為數不少的資源調度策略方面的研究，雖然很多都只是停留在模擬仿真階段，還沒有完整的理論依據，但對于進一步的研究有一定的參考價值。下面就目前存在的一些調度算法進行簡要分析：

2.2.1 螞蟻算法

螞蟻算法是一種基于螞蟻行為的新的啟發算法，由意大利學者提出，用于解決各種組合優化問題．當螞蟻覓食時，會在經過的路上放一些信息作為標記，每條路徑上的信息數量反映出其它螞蟻選擇此路徑的機率，最終導致所有螞蟻都能選擇最短的路徑。螞蟻算法具有的并發性和可擴充性，使它非常適合用于網格計算的任務調度，在同一時間內，所有影響資源狀態的因素都可描述出，那么調度程序就可以簡單快速地預測結果。

2.2.2 先進先出調度算法

先進先出調度算法是任務到達的順序即使任務執行的順序。每次挑出資源中最快的機器接受和執行任務。該算法的缺點是，既不考慮任務的優先級別。用戶提交任務是定義的最終完成期限。也不考慮任務的長短給任務執行時間帶來的影響。當網格中主機的數量增加時。該算法的復雜性將呈指數增長。

2.2.3 Min-min算法和Max-min算法

Min-min算法的目的是將大量的任務指派給不公完成最早，而且執行最快的機器，以使全部任務完成時間最小。該算法計算每個任務在各個機器上的期望完成時間，獲得每個任務的最早完成時間及其機器，再將具有最小最早完成時間的任務指派給獲得它的機器，指派完成后更新機器就緒時間，并將已分本的任務從任務集合中刪除。如此重復，直到全部任務被分配為止。

Max-min算法是啟發式算法，優先考慮長任務。一旦每個任務獲得最早完成時間的機器被找到，具有最大最早完成時間的任務將被指派給該機器，并更新期望完成時間矩陣和機器就緒時間向量。如此重復，直到所有任務分配完畢。顯然，Max-min算法和 Min-min算法有著同樣的計算復雜度。

2.2.4 中心式網格調度模型

在如圖1所示的中心式調度模型中，只有一個網格調度器，這個調度器跟蹤所有計算資源上的負載信息，獨立地在計算資源范圍內為應用作業或任務找到適合的節點集合。

中心式調度模型分為兩層，一個網格調度器自成一層，虛擬機群中的代理組成一層。中心式網格調度框架很容易修改為分布式調度模型，以適應資源動態增加的情況，從而提高網格可用性。中心式調度模型的網格調度器通過代理與所有計算節點進行通信。代理在中心式網格調度模型中扮演重要角色。在這里，代理負責接收調度器的請求信息，接收調度器分配的任務，負責任務的啟動執行，結果收集。此外，代理還負責監測各個計算節點，收集資源特性信息。

由于網格調度器是網格系統的單一中心，必須保證其安全和可靠，以防止單點失效。建立雙網格調度器是解決單點失效的一種有效方法。

在中小規模的單管理域的網格計算系統中，適合采用中央式網格調度模型。用戶通過Web入口，訪問網格調度器。

2.2.5 分步式網格調度模型

在分步式網格調度模型中，每個網格調度器僅維護本管理域的負載信息，通過調度之間的協作，才能為任務選擇到適合的節點。當網格規模不受限制地擴大，讓一個網格調度器去跟蹤所有節點的負載信息是困難的，所以，網格中使用分步式調度框架更具一般性。

分布式調度模型可以采用以下方法來實現

第一種方法是，將工作站網絡分為兩層，即WAN和LAN。每個LAN實現一個內部調度器和一個外部調度組件。當一個處部調度組件收到一個計算請求，它選擇一個LAN，并將該計算請求的作業發送給LAN，再由該LAN內的內部調度器進行調度。

第二種方法是，設置多個網格調度器和一個中心管理節點。當一個網格節點收到作業時，中心管理節點根據搜索開銷，確定作業遷移到周圍哪些網格調度器是可行的，并從中選擇最適合的網格調度器。

第三種方法是，將所有節點構成一棵樹，根節點的性能是最強大的，其他任一節點的性能都不大于其父節點。在這種結構中，任一個中間節點的失敗，均會導致該結構分裂成兩個獨立的調度空間。從這一點來說，樹結構是不合理的拓撲結構。

基于對以上資源調度算法的分析與綜合，以及對其優缺點的深入理解，本文提出了一種多級資源調度算法，可以更好地解決在網格環境下，調度過程中對資源的有效利用問題。

3 一種基于分布式調度算法的多級資源調度策略

多級資源調度策略基于分布式資源調度算法，在計算網格環境下，可以處理對多種資源的需求。多級資源調度算法中，不僅考慮了各個站點性能，也考慮了資源的需求。該算法的主要目的是通過對可利用網格資源的有效處理，得到一個最短執行時間。基于算法思想提出了一個模型，在這個模型中，任務屬性和站點資源的特性都可以被捕獲到并用于算法中，同時也可以滿足串并行的不同需求。

由于網格系統由不同的節點組成，這樣就有大量的資源可以利用，在任務執行之前，應該對這些資源進行適當的分配和組織。多級資源調度算法考慮到任務的需求和資源特性，如何為某一任務更好地匹配和分配站點，直接影響到任務是否能夠有效地執行。當可以為任務遠距離的分配站點時，該任務就可以被高效的執行。當一個單獨的串并行任務被分配到一個站點，而這個站點又不能滿足它對資源的需求，此時可以將任務進行拆分。因此，為了能夠成功而高效的完成任務，需要從遠距離站點獲取額外的資源。多級資源調度算法能為串行和并行任務分配最優的站點，即具有高帶寬和低通訊費的站點，它總是將每一個任務分配到站點并為其提供最好的資源，確保了任務的執行環境。

只要任務和站點資源具有相同的需求就可以進行無次序索引，但這必須依賴于多級資源調度算法中對所有資源的共享。即使將來對單個任務的需求有所變化，也不會影響到整個算法。就整個調度過程而言，不會有任何損失。

多級資源調度策略可以提高執行效率，更好的分配資源。但是用某一個單一的站點去滿足任務的需求時，也需要避免對它過多的資源分配，這需要保證這些資源在執行中的完成效率。以便使一個任務能夠得到最匹配的資源。在模擬仿真實驗中，通過對以下一些指標的分析表明，多級資源調度算法可以使網格環境下的資源調度得到優化。

1）平均等待時間（AWT）：任務在執行之前等待入隊需要持續的時間。一個單獨的任務實例的等待時間是由任務開始執行的時間（ej）與任務被提交的時間(sj)之差得到。在仿真環境下，計算所有任務的等待時間，就可以得到平均任務等待時間。如果總共有Ｊ個任務被提交，那么平均等待時間可用下面公式計算，計算所得的值可對策略機制做出響應。如果等待時間短，該算法可以潛在地增加交互時間，縮短任務在執行前的潛伏期。

2）隊列完成時間（QCT）：該調度算法處理隊列中所有任務需用的時間。是從每一個任務入隊到最后一個任務出隊所用的時間。在實驗過程中，將任務量輸入系統進行調試，模擬跟蹤。這樣可以定量的進行系統吞吐量的測量，時間花費越小越好。計算公式如下：

這里，ＥＪ-1是最后一個任務的執行時間。包括在任務執行過程中的輸入輸出和交互所需時間。加上平均任務等待時間時，允許減少系統所給的任務量中各個任務的最大時間花費。

3）平均網格資源利用率(AGU)：為了優化執行，該算法研究了如何更好的組織任務和網格資源。最大資源利用率可以更好地優化系統環境。在每一段執行時間內，對網格資源的利用可以用一公式描述，即U(t)=Mu/M，這里M是指可利用資源的總量。Mu是指已經用過的資源量。因此AGU可以用下面公式描述：

基于算法模型進行的嚴格的仿真實驗，實驗結果清楚地表明了多級資源調度算法的優越性。該算法和大部分已經提出的調度算法相比，在任務等待時間、隊列完成時間和平均資源利用率等方面占優勢。

4結束語

雖然網格技術是一門備受矚目的新興技術，還沒有被廣泛應用，對于它的研究還不夠成熟，但是其巨大的應用前景已經吸引了很多國內外的研究學者。從網格發展的過程來看，關于任務調度的研究還處于初步價段，還需要研究學者的繼續努力和不斷的實踐．而在網格技術的眾多問題中，資源調度是是最為集中的問題之一。本文提出了一種基于分布式資源調度算法的多級資源調度策略，采用該算法來實現網格資源調度可以最大限度地利用系統資源，提高系統吞吐量和執行效率。基于網格技術的特點和資源調度策略的重要進位，未來在該領域的研究還有待進一步的發展。

參考文獻：

[1] 桂小林.網格技術導論[M].北京:北京郵電大學出版社，2005:144-198.

[2] 張穎峰，李毓辟.基于進化算法的網格計算資源管理調度系統[J].計算機工程，2003，29(15):110-175.

[3] 楊駿賢，蔣秀鳳.基于任務的網格資源調度研究[J].福建電腦，2008(2):10-11.

[4] 楊長興，袁偉華.網格資源管理與調度研究[J].開發研究與設計技術，2007(1):166-247.

[5] Khoo B.T.Benjamin，Veeravalli Bharadwaj，Hung Terence，et al.A multi-dimensional scheduling scheme in a Grid computing environment[J].Science Direct，2007(67):659-673.

[6] Berman F.Wolski.Adaptive Computing on the Grid Using AppLeS[J].IEEE Transactions on Parallel and Distributed Systems，2003，14(4):369-382.