摘 要： 研究了現(xiàn)有的調(diào)度算法，針對(duì)以出賣(mài)計(jì)算力為目的的網(wǎng)格，提出了基于冗余分配的調(diào)度模型，通過(guò)冗余分配實(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è)施，它提供無(wú)縫的、面向主題的全面資源共享和高性能計(jì)算。它向人類(lèi)描繪了一臺(tái)虛擬的超級(jí)計(jì)算機(jī)畫(huà)面，整個(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]、開(kāi)放網(wǎng)格服務(wù)體系結(jié)構(gòu)[3](OGSA)和開(kāi)放網(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ì)算中，通過(guò)對(duì)網(wǎng)格中計(jì)算力資源的整合，充分使用網(wǎng)格中的剩余計(jì)算力是一種最常見(jiàn)的利用資源的形式。在這種以出賣(mài)計(jì)算力為主的網(wǎng)格中，一個(gè)客戶無(wú)法知道陌生的遠(yuǎn)端機(jī)計(jì)算出來(lái)的結(jié)果的正確性：有可能遠(yuǎn)端機(jī)為了獲取經(jīng)濟(jì)利益故意偽造結(jié)果；或是遠(yuǎn)端主機(jī)本身的處理能力不夠，如產(chǎn)生了錯(cuò)誤的浮點(diǎn)結(jié)果等[5]。本文針對(duì)該問(wèn)題研究了現(xiàn)有的網(wǎng)格調(diào)度算法，并對(duì)以出賣(mài)計(jì)算力為主的網(wǎng)格提出了基于冗余分配的調(diào)度模型。
1 網(wǎng)格中的調(diào)度算法
任務(wù)調(diào)度是根據(jù)任務(wù)的信息和資源的信息采用適當(dāng)?shù)牟呗园巡煌娜蝿?wù)分配到合適的資源節(jié)點(diǎn)上運(yùn)行的過(guò)程。網(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)，通過(guò)資源的歷史記錄對(duì)其現(xiàn)況進(jìn)行預(yù)測(cè)。主觀上，網(wǎng)格環(huán)境中大多數(shù)網(wǎng)格成員并不是專(zhuān)門(mén)為計(jì)算網(wǎng)格中的任務(wù)服務(wù)，只是提供部分計(jì)算力完成某些任務(wù)。資源的所有者并不希望它的資源專(zhuān)門(mén)為網(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)系過(guò)密，會(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的開(kāi)始時(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)鍵的問(wè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ù)載過(guò)重)，重新安排調(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)度算法
通過(guò)網(wǎng)格購(gòu)買(mǎi)空閑的計(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)開(kāi)始運(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)的平均值不斷地寫(xiě)入該隊(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作為分類(lèi)標(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ì)列中開(kāi)始查詢(xún)，如“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)原來(lái)的狀態(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í)查詢(xún)其性能參數(shù)值wholePerformace為50％，此時(shí)不分配該節(jié)點(diǎn)，同時(shí)將它從“very vacant”隊(duì)列刪除并插入到“median”隊(duì)列中。
(5)整個(gè)查詢(xún)結(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ù)，說(shuō)明分配的次數(shù)，初值為0；“已獲得結(jié)果”，記錄獲得的資源節(jié)點(diǎn)計(jì)算的結(jié)果，若存在相等的結(jié)果，則為該子任務(wù)打上“刪除標(biāo)記”。
分配器一開(kāi)始將子任務(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èn)題等，則分配給它的子任務(wù)V1總是無(wú)法完成。但是按照分配策略，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)度模型，適用于以出賣(mài)計(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