一種應用于網格計算環境的任務調度模式

摘要：提出了一種新的網格任務調度模式，針對網格計算資源有組織、松耦合、自治等特性，建立基于多層次虛擬組織形式的計算資源模型；根據網格環境中應用任務粗粒度、特定資源依賴等特點，建立了網格任務的描述模型；提出并實現了相應的子任務生成算法、任務初始調度算法及自動調整算法。設計實現了能夠支持仿真及實際網格計算環境可擴展網格任務調度器，通過理論分析和仿真實驗對算法的正確性、效果和效率進行了評價。

關鍵詞：網格計算；任務調度；任務調度模式；算法；調度器；仿真

中圖分類號：TP393文獻標志碼：A

文章編號：1001-3695(2008)05-1500-04

1網格計算中的任務調度問題

網格計算[1]是分布式計算的一種，目的是為用戶構建一個統一的、整合的、虛擬的計算資源，以實現跨組織的資源共享、管理與訪問。網格所要實現的功能，遠不止是數值科學計算，還包括各種形式的協同工作、業務流整合、數據信息共享與互操作等。要真正實現網格在現實生活中的應用，需要解決的技術問題還很多，如標準、安全、資源管理、任務調度、中間件設計與實現等。其中，網格計算的任務調度是一個至關重要的問題，網格環境中的管理程序需要運用合適的策略，協調多個用戶之間對網格資源的合理使用，即將一組相關的任務調度到特定的計算資源上去執行，任務調度的策略和算法將直接影響到任務執行的效率以至成敗。

在傳統的分布式計算領域，有很多比較成熟的任務調度理論與方法，如基于圖論的調度算法、0－1規劃策略、啟發式調度算法、基于遺傳算法和模擬退火算法的任務調度策略、啟發式表調度算法等[2]。不過，這些算法的理論基礎是高度抽象了的傳統分布式計算環境以及任務模型，而網格計算的任務調度問題中計算資源和任務都具有其本身的特點，如計算資源的自治性、計算資源組織的自相似性、任務對特定計算資源的依賴性等。因而需要去探究更合適的任務調度模型，并在此基礎之上設計并開發簡單實用的調度算法，以盡量貼近特定的實際應用。各研究機構也已經提出了很多任務調度模式，如基于簡單輪詢方法、微觀經濟模型、各種經典非線性優化算法等，也有綜合多種策略的模式。這些模式各有其優缺點，仍處于不斷發展與完善的過程之中，同時人們也在努力探索新的任務調度模式，以期更高效地進行網絡計算環境中的任務調度。

本文提出了一種新的任務調度模式，充分考慮了網格計算環境本身虛擬化、分層次及自治的本質特征，以及網格任務的粗粒度、資源依賴、重復執行等特性。同時設計實現了一個可擴展的網格任務調度器，以驗證并評價本文所提出的任務調度模式及相關算法。

2網格任務調度模式

網格計算環境中的任務調度，就是根據一定的規則和策略，將構成網格應用程序的一組任務映射網絡計算環境中的多個節點上去執行，以期取得較好的系統執行性能，實現系統的負載平衡。任何一個任務調度系統都是由運行環境、程序任務、調度程序構成。相應地，在網格環境的任務調度問題中，此三部分分別為網格計算任務、網格計算資源和任務調度程序。

2．1網格計算任務

由于網格計算環境本身的復雜性，小規模的應用程序并沒有必要部署到網格環境中。并不是任意的任務都適于在網格環境中運行，適于在網格計算環境中運行的應用程序具有如下基本特性：

a）任務粒度大。網格上運行的任務，一般運行時間都比較長，計算量較大，子任務間通信量小；否則，其效率可能低于在普通的計算環境中運行的效率。

b）任務可劃分。在網格之上運行的應用程序，一般可以劃分為若干個子任務，由不同的計算資源協同完成，各個子任務之間有著明確的先后約束關系。

c）對特定計算資源的依賴性。就當前的技術以及近期的技術趨勢而言，尚無法做到在任意的計算資源上運行任意的任務，尤其當某個子任務只能由特定的儀器或設備來完成時，其他資源無法替代，因而，只能是在特定的某個或某些計算資源上運行特定的任務。

對于網格任務，建立的描述模型如下所述：在提交任務時，需給出任務時限要求，即最早開始時間與最遲完成時間；任務可以劃分為預定義的網格子任務，并給出（或估算出）各個子任務計算及其他開銷所需要的時間；給定可以完成特定子任務的計算資源；任務的各個子任務構成一個 DAG（directed acyclic graph，有向無環圖）。DAG任務圖示例如圖1所示。其中：nx為任務的序號；括號內的數字為計算量參數。

2．2網格計算資源

從任務調度的角度來考慮，無論是OGSA[3]還是 WSRF[4]，或是文獻[5]提出的任務池模型，基本思想都是將網格中的各種計算資源抽象為虛擬組織[6]，各個虛擬組織通過網格服務[7]連接起來構成虛擬的網格環境；同時，各個虛擬組織所提供的網格服務也不盡相同。例如，會有專門提供某種算法的高性能計算服務的虛擬組織，也會有專用設備作為網格環境中的一個虛擬組織。這就使得網格中的資源會具有如下特點：資源間的耦合度比較松；每個資源都有特定的可用時間；資源實際上有組織，只是不為最終用戶所感覺；資源具有相當的自治能力。

基于以上分析，本文建立了如下的針對任務調度的網格資源模型。網格中的資源可以抽象為分層級的虛擬組織（virtual organization，VO）。一個 VO 中可以有一個或多個更小的VO，以完成更具體的任務。一般來說，認為最底層的VO只能完成一種特定功能。上層VO可以獲得其下層VO的參數、狀態以及未來任務計劃，包括指定的下層 VO 的可用時間。在本文所提出的調度模式中，有一個集中的資源描述服務，但具體調度分層級完成。對資源描述服務來說，網格資源分為三個邏輯上的層級：第一個層級為對它來說有調度權限的能完成某一特定功能的邏輯上的組織；第二個層級為邏輯組織中各個網格計算資源；第三個層級為計算資源中具體的物理計算設備。同一個物理資源中的各個網格資源可以屬于不同的邏輯組織，而若一個網格資源同時提供多種服務，則認為它同時表現為多個網格資源，如圖2所示。

2．3網格計算任務調度程序

網格計算環境中的任務調度程序所要完成的工作是將劃分后的子任務安排到適當的計算資源上去運行。

任務調度系統的數據來源包括：a）任務描述，即新下達的任務，以及網格環境中此調度系統可以管理的計算資源中已經在運行的任務及其參數；b)計算資源描述，即各網格計算資源能完成的工作、能力、當前負載情況以及任務隊列中的排除情況以及其他相關信息；c)統計數據，主要是計算資源以前完成任務情況的統計，為新的調度及優化策略提供參考，包括計算資源的實際利用率、宕機頻率等。

任務調度的過程：取得新下達任務的描述，按相關說明將其劃分為一組子任務，并計算得出各個子任務的最早/最遲完成時間，生成子任務對象；導入當前所管轄的計算資源的信息數據，包括計算資源本身的參數、當前正在運行的任務、任務隊列情況等；根據經過劃分和計算的子任務的需求，以及計算資源的現有條件，按一定規則將各個子任務調度到適當的計算資源。在調度的過程中，如果發生某個或某些計算資源無法完成任務而導致整個任務無法在指定時間內完成的情況，則進行調度方案的優化并重新執行調度。

3任務調度算法設計

基于上述調度模式的任務調度算法由三個部分構成，即子任務生成算法、初始調度算法和自動調整算法。其中:子任務生成算法負責算出各個子任務的最早開始時間和最遲完成時間；初始調度算法將各個子任務直接調度到計算資源；自動調整算法用于對調度結果自動進行調整。

3．1子任務生成算法

子任務生成算法需要完成的任務是生成子任務對象，并根據給出的所有任務計劃最早開始時間和最遲完成時間以及每個子任務估計需要的時間（包括通信等其他時間開銷的估計值），計算出每個子任務的最早開始時間（earliest start time，EST）和最遲完成時間（latest finish time，LFT）。用 Task 表示任務整體，SubTask[i]表示第i個子任務對象，totalLoad 表示子任務所需總時間估計值，workLoad 表示子任務工作時間的估計值，overload表示子任務的其他開銷的估計值，n表示子任務數目，則子任務生成算法如下：

SubTask[0].EST=Task.EST;

SubTask[n+1].LFT=Task.LFT;//引入兩個虛任務

Construct DAG;//構造 DAG，描述各子任務依賴關系

for i=1 to n do//計算子任務所需時間

SubTask[i].totalLoad=SubTask[i].workLoad+SubTask[i].overload;

Time findEST(SubTask[]) //計算最早開始時間

{Time est=SubTask[0].EST;

if(SubTask[j].prev=SubTask[0])

return est;

for each SubTask[j] in SubTask[]

{if(SubTask[j].EST=1)

SubTask[j].EST=findEST(SubTask[j].prev);

est=max(est，SubTask[j].EST+SubTask[j].totalLoad);}

return est;}

for i=1 to n do//計算每個子任務的最早開始時間

if SubTask[i].EST=1;

SubTask[i].EST=findEST(SubTask[i].prev);

//計算各子任務最晚完成時間的算法與計算最早開始時間算法基本相同，從略

3．2初始調度算法

首先定義描述資源的符號。Factory 表示可以完成特定功能的邏輯上的組織，Workshop 表示網格計算資源，Device 表示具體執行功能的計算設備，三者是不同級別的功能單位。MaxLoad 為功能單位最大可承受的負載，CurrentLoad 為功能單位當前負載。其余符號將在算法描述中說明。

在進行初始調度之前，需要有一張STR表（子任務—資源對應列表）。進行任務調度時，首先根據STR表將各個子任務調度到各個 Factory 的任務列表中；然后由 Factory自動調整該子任務調度給哪個 Workshop 來執行；最后由Workshop決定由哪個 Device 來具體執行此項子任務。每一項任務都有多個 Workshop（Device）可以完成。任務的初始調度原則是，根據預定義的優先級，將任務調度到優先級盡可能高的Workshop（Device）。可以看出，Factory 需要的調度與自動調整算法和Workshop 所需算法相同，這一特性實際上是由網格環境的自相性決定的。以 Factory 為例介紹初始調度算法及自動調整算法。

為方便進行判斷和調整子任務的加載方案，將每個 Workshop 按時間段劃分，用符號 WorkUnit 來表示某個時間段內的某個資源，將子任務加載到其最遲完成時間所在的 WorkUnit。任務初始調度算法如下：

Factory.addSubTask(SubTask)

{

unAdjustedSubTask.add(SubTask);//將子任務添加到未調整列表

currentLoad+=SubTask.totalLoad;

flag=flase;

for each Workshop //按優先級順序嘗試

{if(Workshop.add(SubTask))//是否能成功取決于加載后負載

量是否超出限度

flag=ture;

break;}

if(!flag)//如果最終加載失敗，則加載到優先級最高的Workshop

Workshop[0].forceAdd(SubTask);

}

for each SubTask

Factory[i].addSubTask(SubTask); 

//將子任務添加到 Factory，i由子任務—資源對應列表決定

3．3自動調整算法

在初始調度算法中，只是簡單地將任務加載到 Workshop，并沒有考慮某些 Workshop負載過載的處理，因此，在初始調度完成后，需要對方案再進行調整，以解決可能出現的負載過載的問題。從初始調度算法可以看出，只有優先級最高的 Workshop 可能會出現負載過載，它需要執行如下自動調整算法：

Boolean autoAdjust()

{from last WorkUnit to first WorkUnit //從最晚的WorkUnit開始調整

{if currentLoad<=MaxLoad //不需要調整

break;

else

{//WorkUnit 中的子任務已按EST順序排序

i=0;

do

{move SubTask[i] to previous WorkUnit;

i++;

/*將EST盡可能早的子任務移到前一個WorkUnit，前提是子任務的 EST 早于前一個WorkUnit 的結束時間*/

until

currentLoad<=MaxLoad;

//直到不再過載

if currentLoad<=MaxLoad

break;

else

return 1;}}

return true;

}

自動調整算法的思想是，由調整期間（即指定進行自動調整的時間段，默認情況下是任務的 EST與LFT之間的時間段）的最后一個 WorkUnit 起，判斷負載是否過載。如果過載，則將此 WorkUnit 中 EST 最早的可移動的子任務移動到前一個 WorkUnit，直到不再過載，然后再判斷前一個 WorkUnit 的負載情況。這樣，依次遍歷調整期間內的所有 WorkUnit 后，將使各個時間段內的負載均不過載。如果某個 WorkUnit 的所有可移動子任務都移動后仍不滿足條件，則此 Workshop 自動調整無法完成，需要將發生失敗的 WorkUnit 中 EST 最早的子任務移動到優先級次之的 Workshop 中，然后由后者執行自動調整算法。依次類推，直到無須再調整或者無法再調整。

4調度器設計及算法評價

在將本文所提出的網格任務調度模式及調度算法應用于實際網格環境之前，首先通過仿真實驗的方法對算法的正確性和性能特性進行評價。

4．1可擴展網格任務調度器

當前已有Bricks、MicroGrid、SimGrid、GridSim、EDGSim、GridNet、OptorSim等諸多網格仿真環境，但其各自的設計思路與本文提出的網格任務調度模式不盡相同，不能直接仿真實現相關的調度算法，從而本文為此設計并實現了一個可擴展到實際網格環境的調度器，其體系結構如圖3所示。調度器具有細致的模塊化劃分，將算法執行與仿真數據源分離，并通過一個數據抽象模塊進行封裝。這樣，當移植到實際應用中時，只需實現預留的接口，算法模塊便可直接集成到真正的網格任務調度系統中。

仿真數據提供模塊：只用于進行網格環境及任務的仿真，主要完成的功能包括：根據配置生成特定的網格任務描述；構造虛擬的網格環境，指定各個網格資源的屬性（能力、角色、可用時間、當前工作負載情況等）以及網格資源構成的虛擬組織；仿真執行調度的結果，給出調度后各個網格資源的情況、任務調度的情況，以及詳細的調度過程描述。

網格任務與資源管理中間件：只用于將來實際的網格計算環境，負責將網格環境中的資源和任務參數提供給數據抽象模塊。仿真實驗無須此模塊的支持。

數據抽象模塊：用統一的數據結構來描述網格任務、網格資源和調度方案，這樣，調度算法只需直接使用這個統一的數據結構，不必考慮它是在仿真環境中還是在實際的網格環境中進行調度，以使得本文所提出的算法或者將來設計開發的其他算法，在經過了仿真環境的驗證之后，無須修改就可以直接應用于實際網格環境。

算法模塊：利用數據抽象模塊所提供的數據結構，完成資源對象的初始化、子任務展開、初始調度、自動調整等各個算法，最后得到一個調度方案，給出經過格式化的結果，或者給出無法完成調度的報告。另外，算法模塊提供接口供進行測試的和將來實際應用中的其他模塊進行調用。

通用工具模塊：實現的是開發環境（Java）所沒有提供而多個模塊會同時用到的功能，如對網格資源或任務的排序、時間日期格式轉換、定制的通用數據結構等。

配置模塊：對調度器的配置，以配置文件的形式給出，調度器開始運行時，首先讀取此配置文件中的系統參數。

用戶與調度器通過用戶視圖模塊進行交互。

調度器中與本文調度算法最密切相關的類包括任務、子任務以及各級網格資源所對應的類，稱為核心類，其他類統稱為輔助類。核心類在調度器的體系結構中均屬于算法模塊。類之間的關系如圖4所示。輔助類完成數據讀入、生成數據結構、輸出結果、配置等任務。

4．2調度算法的仿真實現與評價

對任務調度模式及調試算法的仿真實現的分析與評價從以下三個角度進行：

a）正確性。只有在保證算法實現正確的前提下，方可對此任務調度模式的其他方面進行評價。算法正確性的具體表現在，子任務展開過程中根據整體任務及各個子任務的工作量計算得到的各個子任務的最早開始時間與最遲結束時間，初始調度過程中根據子任務以及網格計算資源參數調度各個子任務的行為，以及自動調整過程中判斷與調整，均與手工推演結果一致。測試用例覆蓋了可能會出現的調度結果：未調整子任務而加載成功、調整優先級最高的計算資源的子任務而加載成功、調整多個計算資源的子任務而加載成功、調整多個計算資源后加載失敗。

b)效果。任務調度算法的效果表現在兩個方面：a)調度的成功率，即調度后任務能夠成功執行的概率；b)計算資源整體上的負載平衡情況。

在完成初始調度后，對每個發生任務量超載的計算資源執行自動調整算法，去判斷是否能夠通過在計算資源所屬的 WorkUnit 之間移動部分任務而達到每個 WorkUnit 的工作負荷都不超出最大工作能力的要求，這樣，就保證了只要最終判定調度方案可行，則每個計算資源的每個 WorkUnit 的工作負荷都將不會超出最大工作能力，調度算法本身最大程度地保證了調度的成功率。任務成功執行的概率直接取決于計算資源本身正常工作的概率，在初始調度算法和自動調整算法中，都是盡量將任務調度到優先級較高的計算資源上去運行，而優先級主要由計算資源的能力和穩定性來決定，所以，這也進一步提高了任務能夠成功執行的概率。

負載平衡的目的是為了避免網格計算環境中某個計算資源任務特別繁重而成為整體上的瓶頸。在初始調度算法中，子任務最先嘗試加載到優先級最高的計算資源所包含的WorkUnit，如果超出則嘗試優先級次之的計算資源，依次類推，如果嘗試至優先級最低的計算資源仍無法加載，則直接加載到優先級最高的計算資源，這樣會造成優先級最高的計算資源中某個WorkUnit 的工作負荷超出其最大工作能力，然后再通過自動調整算法進行調整。在自動調整算法中，也是先在優先級最高的計算資源中進行，如果失敗則將部分任務移至優先級次之的計算資源，再次進行自動調整，依次類推，直到得出成功或失敗的結論。優先級最高的計算資源計算能力更強，也更穩定，因而能夠成功完成任務的概率也就越高，所以將盡可能多的任務交給這些計算資源去執行。這樣，可以充分保證以更高概率按計劃完成任務的前提下，每個計算資源上任一時刻的工作負載都不會超過其最大的工作能力，不會成為網格計算環境的瓶頸。

c）效率。對網格任務調度算法本身運行效率的評價，當前尚無成熟的模型與基準，難以進行橫向對比。本文在此分析與評價的是算法效率本身的一個重要方面：子任務數增加時計算完成調度方案所需時間變化趨勢。

仿真實驗過程中，仿真數據提供模塊預設了 50 個邏輯組織（Factory），每個邏輯組織下有不定數量的能力不同的計算資源（Workshop 和Device），并在部分計算資源上隨機設置了預調度的負載。然后，分別向調度器提交具有不同子任務數的任務，以驗證算法的正確性并分析算法的執行效率。子任務之間的關系根據文獻[8]的構造方法生成。圖5給出了各算法模塊的處理不同子任務數的網格任務運行時間統計，不考慮調度器初始化等開銷。

由圖5可知，在上述條件下，隨著展開得到的子任務數目的增加，各個算法的計算時間消耗基本呈線性增長趨勢。調度過程中可能最壞情形是在所有的計算資源上都執行一遍自動調整，其所需要的時間將主要取決于計算資源的數目和能力、各個計算資源上原有子任務的數目和任務量，以及展開得到的新子任務的數目和任務量。

5結束語

本文提出了一種新的網格任務調度模式及相應的任務調度算法，設計并實現了相應的算法以及一個網格任務調度器。網格資源模型貼近實際的網格計算環境，充分考慮了網格計算資源的自治特性，任務調度分層級、分布式自主進行；面向特定應用，適用于網格任務分解后所得到子任務粒度較大且有一定規則可循的網格應用；支持對任務調度模式具體實現的定制，相對于通用的任務調度模式，可以獲得更高的效率；在網格任務執行之前，根據計算資源的能力及當前已經加載的工作量的情況，對能否成功調度新下達的網格任務進行判定，避免在網格應用程序的運行過程中動態調度而降低整體的效率；在算法中，調度到優先級較高的資源上的任務更多且不會超出其最大工作能力，保證了任務可以更快速地完成，同時提高了任務整體的成功率；網格任務調度器體系結構設計具備良好的可擴展性，同時兼顧了任務調度仿真與具體應用的需求。

此任務調度模式中尚存在一些問題亟待深入討論：

a）子任務工作量的估計模型。在仿真實驗中，各個子任務的工作量是直接指定的。當應用于實際的網格環境時，必然要面臨估算子任務計算量的問題。可以通過兩種途徑嘗試解決:(a)根據算法的時間和空間復雜度對計算量進行估計，直接在任務描述中給出計算量的估計值；（b）更為理想的方法是使用專門估計計算量的程序來完成，通過使用數值操作、存儲器訪問操作和消息傳遞原語操作等來估計得到任務的計算量。

b)計算資源的計算能力量化模型，包括計算資源的優先級、最大工作能力等。在描述所提出的任務調度模式的模型時，已經為計算資源的描述設計了一種實現途徑，即將每個計算資源的能力劃分為若干個相同的部分，這樣性能各不相同的計算資源在任務調度系統中將各自表現為多個相同能力的計算資源的組合，似于操作系統中對處理器的時間片劃分；另外一種方法是計算各個計算資源的相對性能。對于能夠完成某一子任務的所有計算資源，設置一個基準最大工作能力C，代表在固定時間內能夠完成的計算量，以計算資源在同一固定時間內能夠完成的計算量與C的比值作為此計算資源能力系數，在生成WorkUnit對象時，通過基準最大工作能力與計算資源的能力系數求得其本身的最大工作能力。

參考文獻：

[1]MAOZHEN L，MARK B.網格計算核心技術[M].王相林， 張善卿，王景麗，譯.北京：清華大學出版社，2006.

[2]朱喜福，何炎祥.并行分布計算中的調度算法理論與設計[M].武漢：武漢大學出版社，2003.

［3］FOSTER I，KESSELMAN C，NICK J，et al.The physiology of the grid:an open grid services architecture for distributed systems integration [EB/OL].(2002-06-22)[2007].http://www.globus.org/alliance/publications/papers/ogsa.pdf.

[4]CZAJKOWSKI K，FERGUSDN D F，FOSTER I，et al.The WS－resource framework[EB/OL].(2004-03-05)[2007].http://www.globus.org/wsrf/.

[5]LIU Peng，SHI Yao，LI San－li.Computing pool:a simplified and practical computational grid model[C]//Proc of the 2nd International Workshop on Grid and Cooperative Computing.German:Springer Verlag，2004:661-668.

[6]FOSTER I，KESSELMAN C，TUECKE S.The anatomy of the grid:enabling scalable virtual organizations[J].Int’l Journal of Supercomputer Applications，2001，15(3):1－10.

[7]胡春明，懷進鵬，孫海龍.基于Web服務的網格體系結構及其支撐環境研究[J].軟件學報，2004，15(7):1064－1073.

[8]Kasahara Lab.Standard task graph set [EB/OL].[2007].http://www.kasahara.elec.waseda.ac.jp/schedule/.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”