基于價(jià)格反饋機(jī)制的網(wǎng)格任務(wù)管理研究

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

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

3 網(wǎng)格任務(wù)調(diào)度模型設(shè)計(jì)
T2DSM應(yīng)用場(chǎng)景描述如下：每個(gè)站點(diǎn)包括許多節(jié)點(diǎn)，且每個(gè)節(jié)點(diǎn)都有一定量的存儲(chǔ)器。有些應(yīng)用程序需要訪問(wèn)許多數(shù)據(jù)(數(shù)據(jù)密集型)，且可能是可并行的。一定量的數(shù)據(jù)首先被輸入到計(jì)算網(wǎng)格中的節(jié)點(diǎn)，用戶任務(wù)也提交到該節(jié)點(diǎn)。計(jì)算網(wǎng)格是由各種不同類(lèi)型的被連接到局域網(wǎng)和／或廣域網(wǎng)的節(jié)點(diǎn)組成。應(yīng)用程序在本地?fù)碛斜匾臄?shù)據(jù)后才能開(kāi)始被執(zhí)行。當(dāng)用戶請(qǐng)求執(zhí)行程序時(shí)，調(diào)度器被啟用。圖1為T(mén)2DSM模型結(jié)構(gòu)圖，描述整個(gè)T2DSM以及調(diào)度器內(nèi)主要組件和調(diào)度器間的互相作用。

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

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

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

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

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