基于協商模型的網格資源調度算法

摘 要：本文介紹基于協商模型的網格資源調度算法，利用GridSim進行模擬試驗，并將該調度算法與Nimrod/G的DBC-CT算法的性能進行比較分析。

關鍵詞：網格；調度流程；調度算法

中圖分類號：TP393.01 文獻標識碼：A 文章編號：1674-7712 （2014） 10-0000-01

一、基于協商模型的網格資源調度算法的基本思想

調度算法通常需要在各種條件約束下將作業進行調度，如作業的時間限制、花費等。在Nimrod/G調度系統中，Buyya給出了商品市場模型下的DBC（Deadline and Budget Constrained scheduling）算法，DBC算法包括：DBC條件下的時間最優算法（DBC-Time-opt）、DBC條件下的費用最優算法（DBC-Cost-opt）、DBC條件下的時間/費用最優算法（DBC-CT）。上述算法是基于經濟的網格資源調度算法中的經典算法，自Buyya提出DBC算法至今，許多提出的基于經濟的網格資源調度算法都是在DBC算法的基礎上加以改進，例如在時間與花費兩個因素的基礎上增加資源可用性等其它約束因素。

本文提出基于協商模型的網格資源調度算法，該算法改變了DBC算法中通過確定的花費與時間約束表達用戶意愿的方式，使花費與時間約束兩個因素在用戶指定的區間范圍內通過協商的方式進行動態調整。

二、基于協商模型的網格資源調度流程

在基于協商模型的網格資源調度方法中，資源使用者的作業主要通過作業調度器、協調程序、協商進程三個模塊進行調度。基于協商模型的網格資源調度算法的執行過程為：（1）作業調度器獲取任務的預算區間、任務完成時間區間、協商時間；（2）作業調度器查詢注冊服務，獲得可用服務列表brokerResourceList；（3）作業調度器為每一個任務創建一個協調程序；（4）協調程序創建與brokerResourceList中服務數目相同的協商進程，并將任務的預算區間、任務完成時間區間、協商時間發送給各個協商進程；（5）協商進程與相應的資源代理就任務的完成時間以及花費進行協商；（6）協調程序負責為資源代理選擇下一輪的協商策略并確定本輪的最優提議；（7）在協商時間到來后，協調程序將目標資源提交給作業調度器，由作業調度器將作業調度到目標資源上執行。

三、基于協商模型的網格資源調度算法模擬實驗

（一）網格仿真工具GridSim概述。GridSim是一種網格建模與仿真工具，它能夠模擬異構和分布的網格資源、不同需求的應用模型，并能夠測試不同的調度算法性能。使用GridSim模擬網格調度的步驟如下：（1）創建不同的網格資源實體及網格用戶及用戶的作業列表，并對GridSim進行初始化；（2）使用SimJava創建協商對象，包括協調程序、協商進程等；（3）模擬基于協商模型的網格資源調度算法，并使用此算法將作業提交到資源節點上執行。

（二）實驗方法。首先，建立GridSim資源和應用模型。針對不同用戶數、不同時間限制以及不同預算限制的應用，在不同的網格計算資源環境下，給出基于協商模型的網格資源調度算法的執行結果。為進一步說明基于協商模型的網格資源調度算法的性能，我們在同樣的環境下，對Nimrod/G中采用的DBC條件下的花費時間優先算法（DBC-CT）進行模擬，對比分析兩種算法的性能。DBC-CT算法按照任務執行費用排序，優先選擇費用最小的資源完成任務，當存在兩個以上具有相同費用的服務節點時，選擇任務完成時間最短的資源節點。（1）資源模型。GridSim工具能夠創建具有不同處理速度的處理單元（Processing Elements，PE），一臺處理機由一個或若干個PE構成，而一個或若干個處理機構成一個網格資源節點。每個處理單元的處理能力用每秒鐘幾百萬條指令（Million Instructions Per Second，MIPS）描述。在GridSim中資源可以分為兩種類型：Time-shared類型的資源和Space-shared類型的資源。對于Time-shared類型的資源，作業一旦到達資源便立即執行，并在所有作業之間分配資源，最早完成時間的作業先執行，常用輪轉法（Round-Robin）策略； Space-shared類型的資源，作業到達后，如果有空閑的資源就執行作業，否則就排隊等待資源空閑，常用先來先服務（FCFS）策略。用GridSim模擬器可以建立大量不同類型和不同處理能力的網格資源；（2）應用模型。對單用戶應用模型和多用戶應用模型進行模擬，其中，單用戶模型由50個任務組成，多用戶模型由5個用戶組成，其中，每個用戶都由10個任務組成，在GridSim中這些任務被封裝為Gridlet，Gridlet包中包括作業長度、作業輸入和輸出數據大小以及其它和任務執行有關的參數，不同Gridlet能夠模擬不同類型的任務。實驗過程中，我們對用戶設定了不同的時間限制值（Deadline）和預算限制值（Budget）。

四、模擬結果和性能分析

為了對單用戶多任務條件下算法性能進行測試，我們假設用戶有50個相同的作業，用戶的預算為500，時間約束為3000，在單用戶多任務條件下基于協商模型的網格調度算法與DBC-CT算法性能比較結果如表1所示。

從比較結果可以看出，兩個算法都調度完了所有的任務，基于協商模型的網格資源調度算法的平均花費比DBC-CT算法的花費要低87.5%，平均任務完成時間比DBC-CT算法多38.2%，基于協商模型的網格資源調度算法的總效用要高于DBC-CT算法。

基于協商模型的網格資源調度算法的花費較低的原因是：一方面，由于只有一個用戶，所以在作業調度的過程中不存在用戶間的競爭；另一方面，用戶的作業逐個進行調度，因此，資源的負載一直維持在一個較低水平。缺乏競爭以及較低的負載兩個因素使得資源的使用價格低于DBC-CT算法中商品市場模型下的定價。綜合以上的分析，基于協商模型的網格資源調度算法能夠有效地提高用戶任務的完成率，并且能夠使整個網格系統形成一個用戶之間與資源提供者之間相互競爭使用資源與銷售資源的局面，從而提高整個網格系統的工作效率。

五、結束語

本文提出了基于協商模型的網格資源調度算法，通過GridSim進行模擬實驗，分析的結果表明：基于協商模型的網格資源調度算法能夠有效地提高用戶作業的完成率，并能均衡網格中各資源的負載，從而提高整個網格的工作效率和吞吐率，更符合網格的實際需求。

[作者簡介]杜麗（1983-），女，碩士研究生，教師，助教，研究方向：網格計算。