基于網格計算的資源調度研究

摘要：本文對資源調度的特點、相關技術及面臨的挑戰等難點進行了初步探討，并將在未來繼續探索和試驗。

關鍵詞：網格

資源管理

資源調度

中圖分類號：TP393

文獻標識碼：B

文章編號：1002-2422(2010)03-0004-03

1網格資源

1，1網格資源的分類

網格資源種類繁多，功能各異。根據不同的角度分成不同的類別：

(1)能否移動?？蓪①Y源分為可移動資源和不可移動資源。可移動資源包括數據、程序、代碼等，不可移動資源是無法通過網格操作實現地理位置移動的資源，如各種硬件、設備。

(2)是否可重復使用。可將資源分為可重復使用的資源和不可重復使用的資源。可重復使用的資源包括人類資源。

(3)是否可復制?？蓪⒕W格資源分為可復制資源和不可復制資源，可復制是指可以通過指令或服務請求把一份資源變為多份，如數據、應用程序、服務等。

1，2網格資源存在的三個問題

這三個問題也是目前網格所存在的問題。首先是異構性。由于網格由分布在廣域網上不同管理域的各種計算資源組成，怎樣實現異構機器間的合作和轉換是首要問題。其次可擴展性。要在網格資源規模不斷擴大、應用不斷增長的情況下，不降低性能。最后動態自適應性。當某一資源出現故障或失敗的可能性較高時，資源管理必須能動態監視和管理網格資源，從可利用的資源中選取最佳資源服務。

網格資源的這些特點決定了網格資源管理系統應當隱藏異構性，為用戶提供統一的訪問接口；要屏蔽動態性，保證用戶使用的質量；要尊重資源的本地管理機制和策略；要仔細審查網格用戶的請求，確保網格資源的安全和資源擁有者的權益。此外網格資源管理模型主要分為分層模型、抽象所有者模型和經濟市場模型三類。計算網格的資源管理任務分為四個層次：作業并行分析、全局資源分配、局部資源分配和本地資源管理。

1，3Globus資源管理結構

Globus是目前網格技術的產品。是由Argonne國家實驗室、南加州大學信息科學院、芝加哥大學聯合開發的一個項目。其中GlobusToolkit是GlobuS項目最重要的成果。Globus是一個分層式的體系結構，主要由資源中介、資源協同分配器、資源規范語言和網格資源分配管理器組成，其體系結構如圖1所示。

GRAM與本地資源管理器，如圖中的LSF、Condor等打交道，負責處理來自遠程應用的資源請求，為請求資源的應用分配所請求的資源，并管理作業的執行過程。GRAM也負責向MDS報告資源的有關信息。GRAM主要由門衛和作業管理器兩部分構成。門衛是資源上所有遠程請求的一個單一入口點，負責用戶認證，把遠程用戶映射到本地的一個安全環境中，讓本地資源開始為其服務。作業管理器是門衛的一個服務，門衛啟動作業管理器的一個實例之后就把作業的管理和作業執行的整個過程都交給了作業管理器。門衛則可以在簡單地處理應用請求之后快速返回，繼續監聽消息，為用戶提供快速響應。作業管理器可直接與本地資源管理系統連接，處理與作業的遠程交互。

2資源調度

2，1資源調度的目的和特點

網格的目的是滿足分布在不同地域的用戶共享資源和協同工作的需求。而資源調度的目的在于完成用戶提交的任務和滿足用戶提出的要求，把網格中所有可用資源進行匹配，找到最好最合理的資源分配方式和資源調度策略。

良好的調度是實現高效使用共享資源的重要環節。通過調度，可以把應用所需的計算隱藏于網格中，降低了上層應用的復雜性，使用戶不必關心任務所需的計算放到什么地方去執行，從而把更多的精力投入到業務本身的開發中。參考文獻中給出了基本的調度模型，如圖2所示。

假定系統中有n個作業需要處理，記為：J={J1，J2，J3，……，Jn}；同時，系統中存在t個機器能夠處理這些作業，記為：M={M1，M2，M3，……，Mt}。那么對于每個作業而言，調度則是將一個或者多個機器上的一個或多個時間間隔分配給該作業的過程。

2，2資源調度系統的組成

資源調度系統如圖3所示由三部分組成的。分別是調試策略、應用模型、資源模型。這三部分各有特點。調度策略是一些調度的規則和算法，使應用能夠按照規則找到最優的資源；應用模型是對所調度的應用的抽象描述和度量；資源模型是對計算資源的描述和度量。

調度跟網格的拓撲結構有很大關系。在研究調度時首先一定要確認是哪個層次的，然后建模和設計算法。

從大的方面講，調度有兩部分。

(1)調度的策略。用來確定相對目前的任務，什么服務是最優的。

(2)調度的算法。用來處理資源隊列中的任務提交的順序。

2，3資源調度方式

網格資源調度方式有兩種，分別是集中式和分布式。集中式調度是在網格中只有一個調度中心，負責調度網格中的所有資源。優點是調度系統知道網格中的所有資源，對于一個應用可以高效的產生資源調度方案。缺點：

(1)當網絡比較大時，調度系統很難掌握所有的資源。(2)調度系統會成為瓶頸，比如由于錯誤使得調度系統出現故障，就會影響整個網格系統。

集中式調度比較適合小型網格。分布式調度在網格中有多個調度中心，各個中心是平等的。其優點是健壯性、可靠性和可用性比較高；其缺點：(1)調度中心之間的通信量比較大。(2)由于不能掌握網格中的所有資源，所以很難找到全局最優的資源分配方式。

在資源調度的過程中，常常是兩種方式相結合。如圖4所示，就是集中式與分布式相結合。

3資源調度相關技術

3，1網格資源調度相關算法

資源調度算法是網格研究必須解決的關鍵問題之一。目前，圍繞著網格中的資源調度算法，國內外已做了大量的研究工作，先后提出了各種靜態和動態調度算法。比如：FGFS(fwst come first served)，SF(shonest job first)、FCFS+back filling、level-by-level算法、greedy算法、遺傳算法、貪心算法等。

SF算法是優先滿足最小服務需求的動態網格資源調度算法。該調度算法優先滿足現有任務對資源的最小要求，從而減小單個任務的等待時間。實驗結果表明，該方法不但可以有效減少單個任務的延遲，而且在任務的吞吐豐及CPU效率方面都比較好。

遺傳算法，其本身的執行時間較長，所以這是個關鍵問題，其次就是任務執行時間的預測。遺傳算法相對于其他的尋優算法而言其優點在于對目標問題的求解完全依賴于解空間的個體及其適應度，而不需要其他知識，所以對解決復雜的非線性、非結構問題有很強的求解能力，遺傳算法具有快速隨機的全局搜索能力，但對于系統中的反饋信息利用卻無能為力，當求解到一定范圍時往往作大量無為的冗余迭代，求精確解效率低。

螞蟻算法是通過信息素的累積和更新收斂于最優路徑上，具有分布式并行全局搜索能力，但初期信息素匱乏，求解速度慢。

3，2網格資源調度相關仿真軟件

目前用于網格模擬的仿真工具很多，例如MicroGrid、Bricks、SimGrid、GridSim、OptorSim、ChieagoSim等。每種仿真工具各有特點。Bricks是由日本Ochanomizu大學和東京工業大學等在1999年發布的基于Java的通用網格仿真工具，主要用于對高性能全局計算系統中的不同調度算法和框架進行評估。在設計思想上，Bricks采用了客戶機／網絡／假務器的體系結構，它由全局計算環境和調度單元組成。

Microgrid是由美國加州大學圣地亞哥分校UCSD于2000年發布的一個虛擬的網格計算環境，主要用于網格資源管理和應用程序適應性問題的研究。和其他網格仿真工具不同的是，Microgrid的一個重要的設計目標是通過對Globus Toolkit的模擬，使運行在Globus上的應用程序能夠不加修改地直接運行在Mierogrid之上。

SimGrid是由美國加州大學圣地亞哥分校UCSD于2001年發布的一個分布式異構環境中的分布式調度和并行調度仿真工具。該程序由底層SG和上層MSG組成。

GridSim最初是由澳大利亞Monash大學2001年發布的一個基于Java語言開發的網格仿真工具。用于對集群、對等計算和網格等分布式計算環境機器調度算法進行建模和仿真。GridSim由三部分組成：GridSim、GfidBroker和VisualModeler。

OptorSim是一個基于EU DataGrid體系結構的網格仿真工具，最初發布于2002年，用Java語言編寫，主要用于對大規模廣域分布式數據網格中的各種數據復制算法進行評估。

ChicSim是一個基于PARSEC的用于對數據網格的動態復制策略進行仿真的工具，與OptotSim的功能和設計目標相似。ChicSim采用了層次化分布式結構，主要包括對網格站點、用戶和傳輸網絡三種網格實體模擬，其中用戶生成待處理的作業，每個作業還需要一組數據文件才能執行。

4結束語

只有掌握資源調度的特點和方法，才能更好地研究網格的各項功能。