1 引言
網(wǎng)格是繼萬維網(wǎng)之后出現(xiàn)的一種新型網(wǎng)絡計算平臺，它已成為信息技術領域的熱點研究課題。開發(fā)網(wǎng)格中，任務管理是網(wǎng)格計算系統(tǒng)與應用主體交互的關鍵紐帶，是網(wǎng)格研究基礎且核心的環(huán)節(jié)。但是現(xiàn)有的網(wǎng)格任務管理方法在充分、合理利用資源，較好地滿足網(wǎng)格用戶的任務要求，確保任務的服務質量上仍存在諸多問題，無法很好解決網(wǎng)格環(huán)境中資源的異構性、動態(tài)性和自治性，以及任務的多樣性和動態(tài)性所帶來的困難。本文依據(jù)網(wǎng)格任務管理的這些特點與問題。提出三組件三隊列式的分布式任務調度模型，T2DSM(Triple-component and Triple-queue Distributed Schedule Model)，并將經濟學中的價格調控機制應用于網(wǎng)格任務的調度策略之中，實現(xiàn)任務的合理調度與資源的科學分配。

2 網(wǎng)格任務調度難點分析
目前，網(wǎng)格任務調度主要存在以下問題與難點：
(1)任何一個網(wǎng)格調度器只針對一定范圍內的網(wǎng)格資源進行管理，無法面向所有網(wǎng)格資源；
(2)網(wǎng)格資源動態(tài)變化，資源信息的采集和組織對調度影響很大。
(3)網(wǎng)格中對各種資源的約束很多，有些是非線性的，要達到調度目標也很多，比如要求時間最少、代價最小、資源利用率最高等，有些目標會存在相互矛盾之處，對于這種多目標多約束的問題找到滿足所有約束和目標的全局最優(yōu)解是很困難的。
(4)由于其他應用引起的資源競爭對性能影響很大，而且出現(xiàn)頻率較高。網(wǎng)格資源的復雜多樣。不同類型的資源展示不同性能特性，而且相同類型的資源由于共享等原因所展示的性能也隨時間變化。網(wǎng)格的調度需要建立隨時間變化的性能預測模型，充分利用網(wǎng)格的動態(tài)信息，表示網(wǎng)格性能的波動。
(5)網(wǎng)格的調度必須考慮到資源的多種管理屬性以及調用資源所設計的商業(yè)交易等因素。后者是指網(wǎng)格的調度還必須考慮到如何協(xié)調網(wǎng)格用戶和具體資源提供者之間的利益，即如何使用戶所需要支付的開銷最小且使資源提供者獲得效益更大。

3 網(wǎng)格任務調度模型設計
T2DSM應用場景描述如下：每個站點包括許多節(jié)點，且每個節(jié)點都有一定量的存儲器。有些應用程序需要訪問許多數(shù)據(jù)(數(shù)據(jù)密集型)，且可能是可并行的。一定量的數(shù)據(jù)首先被輸入到計算網(wǎng)格中的節(jié)點，用戶任務也提交到該節(jié)點。計算網(wǎng)格是由各種不同類型的被連接到局域網(wǎng)和／或廣域網(wǎng)的節(jié)點組成。應用程序在本地擁有必要的數(shù)據(jù)后才能開始被執(zhí)行。當用戶請求執(zhí)行程序時，調度器被啟用。圖1為T2DSM模型結構圖，描述整個T2DSM以及調度器內主要組件和調度器間的互相作用。

這里調度器分為兩級，頂級是全局調度器GS(Clobal Scheduler)，下級是局域調度器Ls(Local Scheduler)。與廣域網(wǎng)某段相對應的GS負責被提交的任務應被送到具體的局域調度器。相反LS負責本地局域網(wǎng)的任務調度。整個調度模型采用一種基于非直接全互連通信方式的非集中式結構一分布式結構。每個LS僅在其所在局域網(wǎng)中搜索資源信息，類似地。每個GS僅在其所負責的社區(qū)中處理資源信息。在相鄰GS節(jié)點間直接交換信息，非鄰居GS依靠鄰居GS間接通信。如果任務沒有被調度，調度器將會檢索資源、程序和用戶信息，然后激活其相應組件協(xié)同做出任務執(zhí)行調度和數(shù)據(jù)復制的決定。每個調度器都有三個組件和三個隊列，其功能和關系描述如下：
(1)任務調度組件TSC利用特定算法，任務調度組件TSC(Task Scheduling Component)在有關資源和任務信息的基礎上做出調度決策，若有必要，將一些有關數(shù)據(jù)傳輸?shù)闹噶钕魉徒o數(shù)據(jù)傳輸組件DTC(Data Fransferring Compo-nent)。TSC保持活動狀態(tài)且會對提交任務隊列ATQ(Arrived Task Queue)中的所有人物制定調度策略，然后將已被調度的任務放進已調度任務隊列STQ(Scheduled Task Queue)和指示其任務在被選擇的資源上執(zhí)行。假如局域調度器的。TSC不能給出“最好的”調度，它就會把該任務交付給相關全局調度器的ATO并采用類似方法調度此任務，只是不能完成其調度，它就會把該任務請求傳送給相鄰全局調度器的TSC，并且這些TSC會采用類似的方法繼續(xù)下去直到完成任務調度。
(2)數(shù)據(jù)傳輸組件DTC能夠追蹤每一個數(shù)據(jù)集的本地有效分布情況，如果條件滿足，它就會為任務復制或者移動相應的數(shù)據(jù)集。
(3)價格反饋組件PFC根據(jù)完成任務的執(zhí)行信息調整完成該任務所對應的各個資源節(jié)點價格參數(shù)信息。同時，對于在任務過程中沒能履行職責的資源節(jié)點進行相應懲罰，令其補償完成該任務的價格虧損。
(4)提交任務隊列 ATQ和已調度任務隊列STQ及其任務反饋隊列TFQ(Task Feedback Queue)。ATQ存儲被傳送到本地調度器的所有未調度任務。當一個任務請求到達時，該任務就會存入ATQ，而當一個任務被調度時它就會從ATQ取出，一旦調度成功將從此隊列中移走。STQ存儲那些被本調度器所成功調度的任務，而當這些任務執(zhí)行完成時，將任務轉交到TFQ，對任務完成質量進行評價反饋，然后移出隊列。

4 基于價格反饋機制的調度策略
在提交任務隊列ATQ中，改變傳統(tǒng)的先來先服務(FCFS)和短作業(yè)優(yōu)先(SJFS)的調度思想，在任務進入提交隊列時，對任務的執(zhí)行時間進行估算，具體實現(xiàn)為：

式中，k為任務需求資源的數(shù)量；mi為該資源的任務需求量；fi為需求資源量級權重，是由資源的需求量的范圍等級決定；vi為該資源的平均執(zhí)行速率。
在得到任務的預算時間后，根據(jù)任務描述的時間要求，進行差值運算，所得到的剩余時間作為調度任務的依據(jù)。每次選取提交隊列中剩余時間最少的任務進行調度。
在TSC的調度策略中引入經濟學的價格凋控機制，在任務調度時，選擇可滿足任務的價格最低資源進行調度。在任務的調度過程中，主要有兩個關鍵因素：一個是有效資源，其定義為：對于各個資源節(jié)點，根據(jù)任務描述，過濾該節(jié)點的所有空閑資源，凡是符合任務需求的資源稱為有效資源；二是價格制定。價格的形成取決于諸多因素，對于一個任務來說，其定價公式：

式中，A是資源的價格因子；M是資源的基本因子；η1、η2、η3、η4分別是任務完成好、中、差及未完成的質量因子；n、m、k、l是與質量因子對應的次數(shù)：α是資源的服務等級；P是當前資源的調度價格；ω是資源聯(lián)合工作方式系數(shù)，β是聯(lián)合工作資源節(jié)點的數(shù)量；t為該資源節(jié)點的網(wǎng)絡傳輸狀態(tài)權重。
根據(jù)這兩個關鍵因素，TSC在每次任務調度時，首先對各個資源節(jié)點的資源進行篩選，獲取具有有效資源的資源節(jié)點信息，然后根據(jù)各個資源節(jié)點的資源價格參數(shù)、服務質量參數(shù)及其當前各節(jié)點的網(wǎng)絡狀態(tài)等參數(shù)制定任務調度價格，然后選取價格最小的資源分配方案進行任務調度。如果沒有任何一個資源節(jié)點可以滿足任務中單一資源需求，則先獲取每個資源節(jié)點該資源的單位價格，然后按照由低到高的順序，將任務發(fā)放到各個資源節(jié)點直到完全滿足需求為止。
經過TSC調度過的任務從ATQ中移出投放到STQ隊列中去。此時，DTC根據(jù)各個任務的調度安排，將相應的數(shù)據(jù)集的副本傳輸?shù)较鄳馁Y源節(jié)點。任務在各個資源節(jié)點執(zhí)行時，如果發(fā)生異常，并在規(guī)定的時間內無法繼續(xù)執(zhí)行，則中斷任務，向該任務的任務調度節(jié)點發(fā)送錯誤報告。該任務調度節(jié)點根據(jù)錯誤報告，首先重新調度STQ隊列中的中斷任務，此時該任務的調度優(yōu)先級大于ATQ中任何任務的優(yōu)先級。成功調度后，在STQ隊列中恢復該任務的執(zhí)行，同時在TFO隊列中加入中斷任務信息及其相應中斷錯誤信息。若任務成功完成，則將STQ隊列中的對應任務移出，同時將任務及其相關完成狀況信息加入到TFQ隊列中。
TFQ隊列即任務反饋隊列，主要記錄各個已完成任務的反饋信息。PFC根據(jù)這些信息，調整各個節(jié)點的價格參數(shù)，其主要功能是將完成質量好、執(zhí)行效率高的資源節(jié)點的價格參數(shù)降低，使其更容易被調度；提升完成質量低、執(zhí)行效率低的資源節(jié)點的價格參數(shù)，使其難以調度；在執(zhí)行任務時，由于自身異常發(fā)生錯誤而中斷任務執(zhí)行的資源節(jié)點。不僅大幅度提升其價格參數(shù)，還要對其在該任務執(zhí)行中造成價格虧損進行懲罰處理。價格反饋機制雖然改變資源節(jié)點的價格參數(shù)，但它對任務調度的選取沒有絕對決定作用，因為在調度過程中，資源的選取不僅與各個資源節(jié)點的一系列價格參數(shù)有關，還與網(wǎng)絡狀態(tài)、資源空閑率以及是否是有效資源等因素有關。對于由聯(lián)合參數(shù)決定的價格，它不僅反映當前時間段內各個資源節(jié)點的服務質量(QoS)，而且反映各個資源節(jié)點間的負載均衡及其網(wǎng)絡傳輸效應。這樣服務質量不好，價格參數(shù)高的資源節(jié)點也會伴隨著網(wǎng)格環(huán)境中任務的數(shù)量增加而重新被調度，從而通過任務執(zhí)行，改變自身的價格參數(shù)。因此，各個資源節(jié)點同類資源的價格參數(shù)不盡相同，也是動態(tài)變化，它總是隨著任務的執(zhí)行而不斷改變，是資源站點服務近期服務質量的標志。
在該調度模型中，資源的選取所依據(jù)的價格并不等同于網(wǎng)格服務計費中的實際價格。它只是一種服務質量與負載平衡反應的測度。通過價格的調控，使需調度的任務總是選取當前綜合性能最合理的資源節(jié)點，而不是單一的性能最好或是資源空閑率最大的節(jié)點。

5 結束語
T2DSM網(wǎng)格調度模型的設計以及基于價格反饋機制的調度策略，是將網(wǎng)格任務調度時的各個要素通過經濟學中的價格機制來反應，通過不同時刻下各個資源節(jié)點的價格的動態(tài)變化以及任務完成后資源的價格反饋調整，實現(xiàn)任務與資源的實時、科學合理匹配，符合網(wǎng)格環(huán)境下資源使用的負載平衡及用戶對任務的服務質量需求。