摘 要： 研究了現(xiàn)有的調(diào)度算法,，針對(duì)以出賣計(jì)算力為目的的網(wǎng)格,，提出了基于冗余分配的調(diào)度模型，通過冗余分配實(shí)現(xiàn)了具有計(jì)算結(jié)果驗(yàn)證功能的調(diào)度算法。對(duì)該算法中的預(yù)測(cè)器" title="預(yù)測(cè)器">預(yù)測(cè)器,、資源信息服務(wù)" title="信息服務(wù)">信息服務(wù),、調(diào)度器" title="調(diào)度器">調(diào)度器" title="資源調(diào)度器" title="資源調(diào)度器">資源調(diào)度器">資源調(diào)度器及分配器進(jìn)行了詳細(xì)介紹,。
關(guān)鍵詞： 網(wǎng)格計(jì)算 任務(wù)調(diào)度" title="任務(wù)調(diào)度">任務(wù)調(diào)度 冗余分配 結(jié)果驗(yàn)證
網(wǎng)格(Grid)是新一代的分布式計(jì)算環(huán)境與基礎(chǔ)設(shè)施,，它提供無縫的、面向主題的全面資源共享和高性能計(jì)算,。它向人類描繪了一臺(tái)虛擬的超級(jí)計(jì)算機(jī)畫面,，整個(gè)網(wǎng)格就是一臺(tái)計(jì)算機(jī)，其資源可以取之不盡,、用之不竭,。目前，比較有影響的網(wǎng)格體系結(jié)構(gòu)為國(guó)內(nèi)的織女星網(wǎng)格體系結(jié)構(gòu)[1],、五層沙漏結(jié)構(gòu)[2],、開放網(wǎng)格服務(wù)體系結(jié)構(gòu)[3](OGSA)和開放網(wǎng)格服務(wù)基礎(chǔ)結(jié)構(gòu)[4](OGSI)。任務(wù)調(diào)度是這些體系結(jié)構(gòu)中必不可少的環(huán)節(jié),，因?yàn)橛脩舻恼?qǐng)求最終會(huì)被分置到網(wǎng)格的各資源節(jié)點(diǎn)上執(zhí)行,，從而最小化任務(wù)的執(zhí)行時(shí)間，充分利用網(wǎng)格資源,。
在網(wǎng)格計(jì)算中,，通過對(duì)網(wǎng)格中計(jì)算力資源的整合，充分使用網(wǎng)格中的剩余計(jì)算力是一種最常見的利用資源的形式,。在這種以出賣計(jì)算力為主的網(wǎng)格中,，一個(gè)客戶無法知道陌生的遠(yuǎn)端機(jī)計(jì)算出來的結(jié)果的正確性：有可能遠(yuǎn)端機(jī)為了獲取經(jīng)濟(jì)利益故意偽造結(jié)果；或是遠(yuǎn)端主機(jī)本身的處理能力不夠,，如產(chǎn)生了錯(cuò)誤的浮點(diǎn)結(jié)果等[5],。本文針對(duì)該問題研究了現(xiàn)有的網(wǎng)格調(diào)度算法，并對(duì)以出賣計(jì)算力為主的網(wǎng)格提出了基于冗余分配的調(diào)度模型,。
1 網(wǎng)格中的調(diào)度算法
任務(wù)調(diào)度是根據(jù)任務(wù)的信息和資源的信息采用適當(dāng)?shù)牟呗园巡煌娜蝿?wù)分配到合適的資源節(jié)點(diǎn)上運(yùn)行的過程,。網(wǎng)格中任務(wù)調(diào)度的特點(diǎn)為：
(1)導(dǎo)致網(wǎng)格資源異構(gòu)并且狀態(tài)多變的因素主要有客觀和主觀兩方面?？陀^上,，網(wǎng)格是大范圍的環(huán)境，自然會(huì)有很多意外的情況發(fā)生,，這要求調(diào)度中具有預(yù)測(cè)系統(tǒng),，通過資源的歷史記錄對(duì)其現(xiàn)況進(jìn)行預(yù)測(cè),。主觀上,，網(wǎng)格環(huán)境中大多數(shù)網(wǎng)格成員并不是專門為計(jì)算網(wǎng)格中的任務(wù)服務(wù)，只是提供部分計(jì)算力完成某些任務(wù),。資源的所有者并不希望它的資源專門為網(wǎng)格服務(wù),，因此會(huì)為自己的資源加上某些限制,，如閑置周期以及用戶對(duì)資源的使用權(quán)限等。同時(shí)資源的所有者有其自身的本地任務(wù),，不可能為網(wǎng)格上的遠(yuǎn)程任務(wù)提供完全的服務(wù),。在這種環(huán)境下的任務(wù)調(diào)度要復(fù)雜一些。
(2)由于任務(wù)對(duì)資源的需求各異,，網(wǎng)格環(huán)境中的調(diào)度器必須綜合考慮應(yīng)用和服務(wù)質(zhì)量的約束,，以獲得應(yīng)用與資源之間較好的匹配，因此提出了基于服務(wù)質(zhì)量的調(diào)度算法,。這里服務(wù)質(zhì)量的概念對(duì)于不同的資源可能有不同意義,。例如，對(duì)于網(wǎng)絡(luò)資源,，QoS可為提供給應(yīng)用程序的可用帶寬,；而對(duì)CPU資源，QoS意味著任務(wù)所想獲得的處理速度,，如浮點(diǎn)運(yùn)算速度[6],。
(3)現(xiàn)有的調(diào)度算法都是基于粗粒度，并且相互之間獨(dú)立或只有極少聯(lián)系的任務(wù),。因?yàn)槿羧蝿?wù)聯(lián)系過密,，會(huì)導(dǎo)致通信量增加，反而使整個(gè)計(jì)算效率下降,。這樣,，適合于網(wǎng)格計(jì)算的通常是一些容易分割成相互獨(dú)立子任務(wù)的應(yīng)用。
任務(wù)調(diào)度的基本思路可概括如下：
任務(wù)ti在機(jī)器mj的期望執(zhí)行時(shí)間ETij(Expected Execution Time)定義為mj空載時(shí)執(zhí)行ti的總時(shí)間,。ti在機(jī)器mj的期望完成時(shí)間CTij定義為最終完成的時(shí)間(應(yīng)包括完成其前面所有任務(wù)的時(shí)間),。設(shè)ai是ti的到達(dá)時(shí)間，bi是ti的開始時(shí)間,，則CTij＝bi＋ETij,。
常用的調(diào)度算法描述為：
(1) while there are tasks to schedule
(2) for all task i to schedule
(3) for all host j
(4) compute CTi，j=CT(task i,，host j)
(5) end for
(6) compute metrici=f1(CTi,，1，CTi,，2,，……)
(7) end for
(8) select best metric match(m，n)=f2(metric1,，metric2……)
(9) compute minimum CTm,，n
(10) schedule task m on n
(11) end while
算法需要不斷地計(jì)算未調(diào)度的任務(wù)的期望完成時(shí)間。(2)～(4)為計(jì)算每個(gè)任務(wù)在每個(gè)機(jī)器上的期望完成時(shí)間,；(6)是按照某種評(píng)價(jià)方式f1對(duì)任務(wù)i在每臺(tái)機(jī)器上的期望完成時(shí)間得出其評(píng)價(jià)值metrici,；(8)為使用某種標(biāo)準(zhǔn)f2在每個(gè)任務(wù)的評(píng)價(jià)值中找出符合標(biāo)準(zhǔn)要求的最優(yōu)的任務(wù)與機(jī)器的匹配match(m,，n)；最后將任務(wù)m分配到機(jī)器n上執(zhí)行,。
例如,，Min-min和Max-min算法定義評(píng)價(jià)方式f1為取最小的完成時(shí)間，即某個(gè)任務(wù)i的metric值為它在所有機(jī)器上的完成時(shí)間的最小值,。不同的是,，Min-min的標(biāo)準(zhǔn)f2是選擇metric值中的最小值，而Max-min是選擇最大值,。
從上面的分析可以看出,，一個(gè)好的調(diào)度取決于兩個(gè)方面，即對(duì)資源系統(tǒng)信息的預(yù)測(cè)及對(duì)應(yīng)用程序(也可以認(rèn)為是任務(wù)信息)的預(yù)測(cè),。資源系統(tǒng)的信息包括使用率,、任務(wù)服務(wù)的速率、任務(wù)到達(dá)的速率等,；應(yīng)用程序的信息為工作量,、可分割性、可并行性,、完成時(shí)間等,。一個(gè)關(guān)鍵的問題是：當(dāng)為某些子任務(wù)指定的資源顯示出不正常的狀態(tài)時(shí)(從它的歷史數(shù)據(jù)中預(yù)測(cè)而得)，如何保證并行應(yīng)用的性能,，即調(diào)度系統(tǒng)應(yīng)在執(zhí)行期間預(yù)測(cè)出資源的不正常狀態(tài)(如負(fù)載過重),，重新安排調(diào)度。因此,，一個(gè)調(diào)度算法是否成功取決于系統(tǒng)及應(yīng)用狀態(tài)預(yù)測(cè)的精確度,。這種預(yù)測(cè)是從其歷史信息中獲得的。
根據(jù)預(yù)測(cè)的性質(zhì)可將調(diào)度分為兩種：一種是基于短期預(yù)測(cè)的調(diào)度,，如AppLe項(xiàng)目使用了NWS服務(wù)提供的短期預(yù)測(cè)系統(tǒng),；另一種是基于長(zhǎng)期預(yù)測(cè)的調(diào)度，采用這種方式的是GHS(Grid Harvest Service),。
2 基于冗余分配的調(diào)度算法
通過網(wǎng)格購(gòu)買空閑的計(jì)算力有很大的發(fā)展前景,，但這種方法很難保證所獲得的計(jì)算力能夠計(jì)算出正確的結(jié)果。這里提出冗余分配任務(wù),，使之在二個(gè)或多個(gè)節(jié)點(diǎn)上運(yùn)行,。其結(jié)果被多次驗(yàn)證后認(rèn)為是正確的。
調(diào)度模型由資源調(diào)度器,、任務(wù)分配器,、資源信息服務(wù)和預(yù)測(cè)器構(gòu)成。資源調(diào)度器從現(xiàn)有網(wǎng)格中的節(jié)點(diǎn)資源中找出合適的節(jié)點(diǎn)集，它和資源信息服務(wù)配合使用,；任務(wù)分配器將任務(wù)分配到節(jié)點(diǎn)集中,；資源狀態(tài)預(yù)測(cè)需要消耗計(jì)算力,，所以這里只做簡(jiǎn)單預(yù)測(cè),，同時(shí)忽略對(duì)任務(wù)信息的預(yù)測(cè)。
2.1 預(yù)測(cè)器
這里對(duì)計(jì)算資源的狀況進(jìn)行簡(jiǎn)單的短期預(yù)測(cè),。預(yù)測(cè)由計(jì)算資源節(jié)點(diǎn)提供,，目的是減輕資源調(diào)度器的負(fù)擔(dān)。
預(yù)測(cè)器收集節(jié)點(diǎn)自身信息并在資源調(diào)度器需要時(shí)給出預(yù)測(cè)值,，它作為一個(gè)后臺(tái)程序一直運(yùn)行在節(jié)點(diǎn)機(jī)上,。一旦節(jié)點(diǎn)開始運(yùn)行，就主動(dòng)加入網(wǎng)格,，提供自身的信息,。預(yù)測(cè)器獲得系統(tǒng)的基本信息和可變信息?；拘畔⒅恍枰淮涡垣@得,，在資源加入節(jié)點(diǎn)時(shí)提供給資源調(diào)度器；可變信息隨著時(shí)間變化,，主要包括CPU的使用率和內(nèi)存使用率,。短期預(yù)測(cè)策略方式如下：
(1)設(shè)置一個(gè)線程，每隔1s收集一次動(dòng)態(tài)信息,，如CPU的使用率和內(nèi)存的使用率,。
(2)設(shè)置一個(gè)循環(huán)隊(duì)列，將一分鐘內(nèi)的平均值不斷地寫入該隊(duì)列,。
(3)當(dāng)有預(yù)測(cè)需求時(shí)將隊(duì)列中的數(shù)值讀出再取其平均值作為預(yù)測(cè)值,。例如，當(dāng)隊(duì)列的大小設(shè)為5時(shí)就表示使用前五分鐘的平均值作為預(yù)測(cè)值,。
2.2 資源信息服務(wù)
提供資源信息服務(wù)的是哈希表,，該哈希表的信息組織形式如圖1所示。哈希表為調(diào)度器查找資源節(jié)點(diǎn)集提供依據(jù),。
哈希表的key以節(jié)點(diǎn)狀態(tài)表示,。因?yàn)楣?jié)點(diǎn)狀態(tài)是時(shí)刻變化的，所以對(duì)節(jié)點(diǎn)可用性的描述不需要用十分精確的定量方式得出具體的數(shù)值,，可采用模糊的定性的方式表述[7],，即設(shè)置median、vacant,、very vacant,、busy、very busy五種狀態(tài)，以計(jì)算節(jié)點(diǎn)的性能參數(shù)wholePerformace作為分類標(biāo)準(zhǔn),。例如：wholePerformace>=85,，其狀態(tài)為very busy；wholePerformace∈(60,，85),，為busy；wholePerformace∈[40,，60],，為median；wholePerformace∈(20,，40),，為vacant；whole-Performace∈[0,，20],，為very vacant。
2.3 資源調(diào)度器
調(diào)度器為某一應(yīng)用找到合適的資源節(jié)點(diǎn)集,。其策略為當(dāng)要分配某一節(jié)點(diǎn)時(shí)再次獲取它的信息,，以該最新信息作為調(diào)度的標(biāo)準(zhǔn)。描述如下：
(1)獲得應(yīng)用的子任務(wù)數(shù),，并以其作為資源個(gè)數(shù)的最大請(qǐng)求數(shù),。
(2)在哈希表中從資源情況最好的隊(duì)列中開始查詢，如“very vacant”隊(duì)列,。
(3)從該隊(duì)列中依次取節(jié)點(diǎn),，并依次與節(jié)點(diǎn)對(duì)應(yīng)的計(jì)算資源聯(lián)系，以獲得其現(xiàn)有狀態(tài),。
(4)若該狀態(tài)差于該節(jié)點(diǎn)原來的狀態(tài),，則不分配該節(jié)點(diǎn)，并把它從現(xiàn)有的隊(duì)列中刪除,，插入到與其狀態(tài)相一致的隊(duì)列中,；若優(yōu)于現(xiàn)有的狀態(tài)，則分配該節(jié)點(diǎn),，也把它從現(xiàn)有的隊(duì)列中刪除,，插入到與其狀態(tài)相一致的隊(duì)列中；若等同于現(xiàn)有的狀態(tài),，則分配,；若探測(cè)到該節(jié)點(diǎn)不可用(退出網(wǎng)格)，則將其從隊(duì)列中刪除,。
例如,，一節(jié)點(diǎn)位于“very vacant”隊(duì)列,，但在分配時(shí)查詢其性能參數(shù)值wholePerformace為50％，此時(shí)不分配該節(jié)點(diǎn),，同時(shí)將它從“very vacant”隊(duì)列刪除并插入到“median”隊(duì)列中,。
(5)整個(gè)查詢結(jié)束的條件是：當(dāng)找到子任務(wù)數(shù)個(gè)資源或是當(dāng)資源數(shù)少于子任務(wù)數(shù)時(shí)，直接把所有的資源分給應(yīng)用,。
(6)當(dāng)是單任務(wù)應(yīng)用時(shí),，需找出兩個(gè)或多個(gè)資源。
2.4 分配器
(1)冗余分配
當(dāng)分配器獲得合適的資源節(jié)點(diǎn)集后,，就要決定如何安排子任務(wù)到各合適的機(jī)器上,，以獲得最佳的性能,。這里提出一種冗余分配策略,，即將一個(gè)子任務(wù)分配到多個(gè)機(jī)器上執(zhí)行。采取這種方式的原因是：
?、僭诜峙涔?jié)點(diǎn)集的時(shí)候是一種模糊分配,，因?yàn)閷?duì)資源信息的描述采用定性的方式。
?、谠诿枋鲑Y源性能時(shí)并未考慮網(wǎng)絡(luò)的狀態(tài)而且未對(duì)應(yīng)用程序信息做出預(yù)測(cè),。所以，在同一個(gè)狀態(tài)隊(duì)列中,，性能參數(shù)wholePerformace大的計(jì)算節(jié)點(diǎn)的運(yùn)算結(jié)果有可能先于性能參數(shù)wholePerformace小的到達(dá),。
③冗余分配可以實(shí)現(xiàn)冗余執(zhí)行,，冗余執(zhí)行具有兩種功能,。其一，如②所述,，若將一個(gè)任務(wù)發(fā)送到多個(gè)節(jié)點(diǎn)執(zhí)行,，現(xiàn)狀最好的節(jié)點(diǎn)會(huì)最早將結(jié)果送回。這樣可以以較快的速度獲得結(jié)果,，同時(shí)避免了只發(fā)送到一個(gè)計(jì)算節(jié)點(diǎn)的缺點(diǎn)：若出現(xiàn)意外情況,，需要重新調(diào)度任務(wù)到節(jié)點(diǎn)。其二,，冗余的執(zhí)行可以實(shí)現(xiàn)結(jié)果驗(yàn)證的功能,。
(2)分配算法
分配器的算法描述如下：
對(duì)于每個(gè)子任務(wù)設(shè)置三個(gè)標(biāo)志位：“分配狀態(tài)”，其值為整數(shù),，說明分配的次數(shù),，初值為0；“已獲得結(jié)果”,，記錄獲得的資源節(jié)點(diǎn)計(jì)算的結(jié)果,，若存在相等的結(jié)果,，則為該子任務(wù)打上“刪除標(biāo)記”。
分配器一開始將子任務(wù)隨機(jī)分配到調(diào)度器所找出的資源集上,，分配狀態(tài)變?yōu)?,；若有資源送回子任務(wù)的計(jì)算結(jié)果，則將該結(jié)果記錄到相應(yīng)的標(biāo)志位,；若存在相等的結(jié)果,，則為該子任務(wù)打上刪除標(biāo)記，并且通知其他運(yùn)行該任務(wù)的計(jì)算節(jié)點(diǎn)停止該任務(wù)的計(jì)算,，若不存在,，各標(biāo)住位不能做任何改變；同時(shí)再次隨機(jī)選擇一個(gè)未打上刪除標(biāo)記的子任務(wù),，將其分配到剛送回結(jié)果的計(jì)算資源上,，分配狀態(tài)相應(yīng)加1。整個(gè)分配結(jié)束的條件是所有的子任務(wù)都打上刪除標(biāo)記,。
3 算法性能評(píng)價(jià)
(1)減輕了預(yù)測(cè)的工作量,。因?yàn)橘Y源具有動(dòng)態(tài)性，所以保留對(duì)資源的短期預(yù)測(cè),；因?yàn)檫m合網(wǎng)格計(jì)算的應(yīng)用在劃分時(shí)很容易轉(zhuǎn)化為同樣大小的子任務(wù),，所以忽略對(duì)任務(wù)的預(yù)測(cè)。
(2)分配策略可以很好地支持動(dòng)態(tài)性,，即節(jié)點(diǎn)的動(dòng)態(tài)退出,。若某資源節(jié)點(diǎn)P1不知原因地退出了網(wǎng)格，如用戶誤操作,、自身系統(tǒng)出問題等,，則分配給它的子任務(wù)V1總是無法完成。但是按照分配策略,，V1總會(huì)被分配在節(jié)點(diǎn)集的其他資源上執(zhí)行,，最終V1會(huì)被執(zhí)行完。這時(shí)P1上V1的運(yùn)行情況已經(jīng)不重要了,。
(3)調(diào)度器和分配器的協(xié)作達(dá)到了負(fù)載均衡的效果,。若節(jié)點(diǎn)機(jī)P1負(fù)載小，則它的計(jì)算節(jié)點(diǎn)的性能參數(shù)小,，獲得新任務(wù)的幾率大,；當(dāng)它的負(fù)載逐漸變大時(shí)，計(jì)算節(jié)點(diǎn)的性能參數(shù)也變大,，獲得新任務(wù)的幾率變小,，新的任務(wù)會(huì)向其他性能好的節(jié)點(diǎn)分配，同時(shí)在其任務(wù)隊(duì)列中的任務(wù),，也會(huì)因?yàn)槿蝿?wù)在別處提前完成而被逐漸刪除,。
(4)該算法適用于以計(jì)算為主的網(wǎng)格,。以計(jì)算為主的應(yīng)用結(jié)果容易比較，但有可能出現(xiàn)各機(jī)器精度不一致的情況,。這時(shí)可以對(duì)所需要的精度范圍作出規(guī)定,，對(duì)結(jié)果進(jìn)行簡(jiǎn)單處理后再比較。
本文給出了基于冗余分配的調(diào)度模型,，適用于以出賣計(jì)算力為目的的網(wǎng)格,。希望此算法能為今后的網(wǎng)格研究提供一定的思路。
參考文獻(xiàn)
1 徐志偉,，李 偉.織女星網(wǎng)格的體系結(jié)構(gòu)研究.計(jì)算機(jī)研究與發(fā)展,，2002；39(8)
2 Foster J,，Kesselman C,，Tuecke S.The anatomy of the grid：Enabling scalable virtual organizations.International Journal Supercomputer Applicatins，2001,；15(3)
3 Foster J,，Kesselman C,，Nick J M et al.The Physiology of the Grid：An Open Grid Services Architecture for Dist ributed Systems Integration.http：//www.globus.org/research/papers/ogsa.pdf
4 Tuecke S,，Czajkowski K，F(xiàn)oster L et al.Open Grid Services Inf rast ructure (OGSI).http：//www.ggf.org/ogsi2wg,，2003
5 Alexandrov A D,，Ibel M，Schauser K E et al.SuperWeb：Re-search Issues in Java-Based Global Computing.http：//www.citeseer.ist.psu.edu/alexandrov96superweb.html
6 HE X S,，Sun X H,，Laszewski G V.QoS Guided Min-Min Heuristic for Grid Task Scheduling.http：//www.cs.iit.edu/~scs/psfiles/jcst_XHe-5-28.pdf
7 湯勇平.Java并行計(jì)算環(huán)境中的負(fù)載監(jiān)測(cè)與預(yù)報(bào)系統(tǒng).上海交通大學(xué)碩士論文集，2002