摘 要： 研究了現(xiàn)有的調(diào)度算法，針對以出賣計算力為目的的網(wǎng)格，提出了基于冗余分配的調(diào)度模型，通過冗余分配實現(xiàn)了具有計算結(jié)果驗證功能的調(diào)度算法。對該算法中的預(yù)測器" title="預(yù)測器">預(yù)測器、資源信息服務(wù)" title="信息服務(wù)">信息服務(wù)、調(diào)度器" title="調(diào)度器">調(diào)度器" title="資源調(diào)度器" title="資源調(diào)度器">資源調(diào)度器">資源調(diào)度器及分配器進行了詳細介紹。
關(guān)鍵詞： 網(wǎng)格計算 任務(wù)調(diào)度" title="任務(wù)調(diào)度">任務(wù)調(diào)度 冗余分配 結(jié)果驗證
網(wǎng)格(Grid)是新一代的分布式計算環(huán)境與基礎(chǔ)設(shè)施，它提供無縫的、面向主題的全面資源共享和高性能計算。它向人類描繪了一臺虛擬的超級計算機畫面，整個網(wǎng)格就是一臺計算機，其資源可以取之不盡、用之不竭。目前，比較有影響的網(wǎng)格體系結(jié)構(gòu)為國內(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é)，因為用戶的請求最終會被分置到網(wǎng)格的各資源節(jié)點上執(zhí)行，從而最小化任務(wù)的執(zhí)行時間，充分利用網(wǎng)格資源。
在網(wǎng)格計算中，通過對網(wǎng)格中計算力資源的整合，充分使用網(wǎng)格中的剩余計算力是一種最常見的利用資源的形式。在這種以出賣計算力為主的網(wǎng)格中，一個客戶無法知道陌生的遠端機計算出來的結(jié)果的正確性：有可能遠端機為了獲取經(jīng)濟利益故意偽造結(jié)果；或是遠端主機本身的處理能力不夠，如產(chǎn)生了錯誤的浮點結(jié)果等[5]。本文針對該問題研究了現(xiàn)有的網(wǎng)格調(diào)度算法，并對以出賣計算力為主的網(wǎng)格提出了基于冗余分配的調(diào)度模型。
1 網(wǎng)格中的調(diào)度算法
任務(wù)調(diào)度是根據(jù)任務(wù)的信息和資源的信息采用適當?shù)牟呗园巡煌娜蝿?wù)分配到合適的資源節(jié)點上運行的過程。網(wǎng)格中任務(wù)調(diào)度的特點為：
(1)導(dǎo)致網(wǎng)格資源異構(gòu)并且狀態(tài)多變的因素主要有客觀和主觀兩方面。客觀上，網(wǎng)格是大范圍的環(huán)境，自然會有很多意外的情況發(fā)生，這要求調(diào)度中具有預(yù)測系統(tǒng)，通過資源的歷史記錄對其現(xiàn)況進行預(yù)測。主觀上，網(wǎng)格環(huán)境中大多數(shù)網(wǎng)格成員并不是專門為計算網(wǎng)格中的任務(wù)服務(wù)，只是提供部分計算力完成某些任務(wù)。資源的所有者并不希望它的資源專門為網(wǎng)格服務(wù)，因此會為自己的資源加上某些限制，如閑置周期以及用戶對資源的使用權(quán)限等。同時資源的所有者有其自身的本地任務(wù)，不可能為網(wǎng)格上的遠程任務(wù)提供完全的服務(wù)。在這種環(huán)境下的任務(wù)調(diào)度要復(fù)雜一些。
(2)由于任務(wù)對資源的需求各異，網(wǎng)格環(huán)境中的調(diào)度器必須綜合考慮應(yīng)用和服務(wù)質(zhì)量的約束，以獲得應(yīng)用與資源之間較好的匹配，因此提出了基于服務(wù)質(zhì)量的調(diào)度算法。這里服務(wù)質(zhì)量的概念對于不同的資源可能有不同意義。例如，對于網(wǎng)絡(luò)資源，QoS可為提供給應(yīng)用程序的可用帶寬；而對CPU資源，QoS意味著任務(wù)所想獲得的處理速度，如浮點運算速度[6]。
(3)現(xiàn)有的調(diào)度算法都是基于粗粒度，并且相互之間獨立或只有極少聯(lián)系的任務(wù)。因為若任務(wù)聯(lián)系過密，會導(dǎo)致通信量增加，反而使整個計算效率下降。這樣，適合于網(wǎng)格計算的通常是一些容易分割成相互獨立子任務(wù)的應(yīng)用。
任務(wù)調(diào)度的基本思路可概括如下：
任務(wù)ti在機器mj的期望執(zhí)行時間ETij(Expected Execution Time)定義為mj空載時執(zhí)行ti的總時間。ti在機器mj的期望完成時間CTij定義為最終完成的時間(應(yīng)包括完成其前面所有任務(wù)的時間)。設(shè)ai是ti的到達時間，bi是ti的開始時間，則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
算法需要不斷地計算未調(diào)度的任務(wù)的期望完成時間。(2)～(4)為計算每個任務(wù)在每個機器上的期望完成時間；(6)是按照某種評價方式f1對任務(wù)i在每臺機器上的期望完成時間得出其評價值metrici；(8)為使用某種標準f2在每個任務(wù)的評價值中找出符合標準要求的最優(yōu)的任務(wù)與機器的匹配match(m，n)；最后將任務(wù)m分配到機器n上執(zhí)行。
例如，Min-min和Max-min算法定義評價方式f1為取最小的完成時間，即某個任務(wù)i的metric值為它在所有機器上的完成時間的最小值。不同的是，Min-min的標準f2是選擇metric值中的最小值，而Max-min是選擇最大值。
從上面的分析可以看出，一個好的調(diào)度取決于兩個方面，即對資源系統(tǒng)信息的預(yù)測及對應(yīng)用程序(也可以認為是任務(wù)信息)的預(yù)測。資源系統(tǒng)的信息包括使用率、任務(wù)服務(wù)的速率、任務(wù)到達的速率等；應(yīng)用程序的信息為工作量、可分割性、可并行性、完成時間等。一個關(guān)鍵的問題是：當為某些子任務(wù)指定的資源顯示出不正常的狀態(tài)時(從它的歷史數(shù)據(jù)中預(yù)測而得)，如何保證并行應(yīng)用的性能，即調(diào)度系統(tǒng)應(yīng)在執(zhí)行期間預(yù)測出資源的不正常狀態(tài)(如負載過重)，重新安排調(diào)度。因此，一個調(diào)度算法是否成功取決于系統(tǒng)及應(yīng)用狀態(tài)預(yù)測的精確度。這種預(yù)測是從其歷史信息中獲得的。
根據(jù)預(yù)測的性質(zhì)可將調(diào)度分為兩種：一種是基于短期預(yù)測的調(diào)度，如AppLe項目使用了NWS服務(wù)提供的短期預(yù)測系統(tǒng)；另一種是基于長期預(yù)測的調(diào)度，采用這種方式的是GHS(Grid Harvest Service)。
2 基于冗余分配的調(diào)度算法
通過網(wǎng)格購買空閑的計算力有很大的發(fā)展前景，但這種方法很難保證所獲得的計算力能夠計算出正確的結(jié)果。這里提出冗余分配任務(wù)，使之在二個或多個節(jié)點上運行。其結(jié)果被多次驗證后認為是正確的。
調(diào)度模型由資源調(diào)度器、任務(wù)分配器、資源信息服務(wù)和預(yù)測器構(gòu)成。資源調(diào)度器從現(xiàn)有網(wǎng)格中的節(jié)點資源中找出合適的節(jié)點集，它和資源信息服務(wù)配合使用；任務(wù)分配器將任務(wù)分配到節(jié)點集中；資源狀態(tài)預(yù)測需要消耗計算力，所以這里只做簡單預(yù)測，同時忽略對任務(wù)信息的預(yù)測。
2.1 預(yù)測器
這里對計算資源的狀況進行簡單的短期預(yù)測。預(yù)測由計算資源節(jié)點提供，目的是減輕資源調(diào)度器的負擔。
預(yù)測器收集節(jié)點自身信息并在資源調(diào)度器需要時給出預(yù)測值，它作為一個后臺程序一直運行在節(jié)點機上。一旦節(jié)點開始運行，就主動加入網(wǎng)格，提供自身的信息。預(yù)測器獲得系統(tǒng)的基本信息和可變信息?；拘畔⒅恍枰淮涡垣@得，在資源加入節(jié)點時提供給資源調(diào)度器；可變信息隨著時間變化，主要包括CPU的使用率和內(nèi)存使用率。短期預(yù)測策略方式如下：
(1)設(shè)置一個線程，每隔1s收集一次動態(tài)信息，如CPU的使用率和內(nèi)存的使用率。
(2)設(shè)置一個循環(huán)隊列，將一分鐘內(nèi)的平均值不斷地寫入該隊列。
(3)當有預(yù)測需求時將隊列中的數(shù)值讀出再取其平均值作為預(yù)測值。例如，當隊列的大小設(shè)為5時就表示使用前五分鐘的平均值作為預(yù)測值。
2.2 資源信息服務(wù)
提供資源信息服務(wù)的是哈希表，該哈希表的信息組織形式如圖1所示。哈希表為調(diào)度器查找資源節(jié)點集提供依據(jù)。
哈希表的key以節(jié)點狀態(tài)表示。因為節(jié)點狀態(tài)是時刻變化的，所以對節(jié)點可用性的描述不需要用十分精確的定量方式得出具體的數(shù)值，可采用模糊的定性的方式表述[7]，即設(shè)置median、vacant、very vacant、busy、very busy五種狀態(tài)，以計算節(jié)點的性能參數(shù)wholePerformace作為分類標準。例如：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é)點集。其策略為當要分配某一節(jié)點時再次獲取它的信息，以該最新信息作為調(diào)度的標準。描述如下：
(1)獲得應(yīng)用的子任務(wù)數(shù)，并以其作為資源個數(shù)的最大請求數(shù)。
(2)在哈希表中從資源情況最好的隊列中開始查詢，如“very vacant”隊列。
(3)從該隊列中依次取節(jié)點，并依次與節(jié)點對應(yīng)的計算資源聯(lián)系，以獲得其現(xiàn)有狀態(tài)。
(4)若該狀態(tài)差于該節(jié)點原來的狀態(tài)，則不分配該節(jié)點，并把它從現(xiàn)有的隊列中刪除，插入到與其狀態(tài)相一致的隊列中；若優(yōu)于現(xiàn)有的狀態(tài)，則分配該節(jié)點，也把它從現(xiàn)有的隊列中刪除，插入到與其狀態(tài)相一致的隊列中；若等同于現(xiàn)有的狀態(tài)，則分配；若探測到該節(jié)點不可用(退出網(wǎng)格)，則將其從隊列中刪除。
例如，一節(jié)點位于“very vacant”隊列，但在分配時查詢其性能參數(shù)值wholePerformace為50％，此時不分配該節(jié)點，同時將它從“very vacant”隊列刪除并插入到“median”隊列中。
(5)整個查詢結(jié)束的條件是：當找到子任務(wù)數(shù)個資源或是當資源數(shù)少于子任務(wù)數(shù)時，直接把所有的資源分給應(yīng)用。
(6)當是單任務(wù)應(yīng)用時，需找出兩個或多個資源。
2.4 分配器
(1)冗余分配
當分配器獲得合適的資源節(jié)點集后，就要決定如何安排子任務(wù)到各合適的機器上，以獲得最佳的性能。這里提出一種冗余分配策略，即將一個子任務(wù)分配到多個機器上執(zhí)行。采取這種方式的原因是：
①在分配節(jié)點集的時候是一種模糊分配，因為對資源信息的描述采用定性的方式。
②在描述資源性能時并未考慮網(wǎng)絡(luò)的狀態(tài)而且未對應(yīng)用程序信息做出預(yù)測。所以，在同一個狀態(tài)隊列中，性能參數(shù)wholePerformace大的計算節(jié)點的運算結(jié)果有可能先于性能參數(shù)wholePerformace小的到達。
?、廴哂喾峙淇梢詫崿F(xiàn)冗余執(zhí)行，冗余執(zhí)行具有兩種功能。其一，如②所述，若將一個任務(wù)發(fā)送到多個節(jié)點執(zhí)行，現(xiàn)狀最好的節(jié)點會最早將結(jié)果送回。這樣可以以較快的速度獲得結(jié)果，同時避免了只發(fā)送到一個計算節(jié)點的缺點：若出現(xiàn)意外情況，需要重新調(diào)度任務(wù)到節(jié)點。其二，冗余的執(zhí)行可以實現(xiàn)結(jié)果驗證的功能。
(2)分配算法
分配器的算法描述如下：
對于每個子任務(wù)設(shè)置三個標志位：“分配狀態(tài)”，其值為整數(shù)，說明分配的次數(shù)，初值為0；“已獲得結(jié)果”，記錄獲得的資源節(jié)點計算的結(jié)果，若存在相等的結(jié)果，則為該子任務(wù)打上“刪除標記”。
分配器一開始將子任務(wù)隨機分配到調(diào)度器所找出的資源集上，分配狀態(tài)變?yōu)?；若有資源送回子任務(wù)的計算結(jié)果，則將該結(jié)果記錄到相應(yīng)的標志位；若存在相等的結(jié)果，則為該子任務(wù)打上刪除標記，并且通知其他運行該任務(wù)的計算節(jié)點停止該任務(wù)的計算，若不存在，各標住位不能做任何改變；同時再次隨機選擇一個未打上刪除標記的子任務(wù)，將其分配到剛送回結(jié)果的計算資源上，分配狀態(tài)相應(yīng)加1。整個分配結(jié)束的條件是所有的子任務(wù)都打上刪除標記。
3 算法性能評價
(1)減輕了預(yù)測的工作量。因為資源具有動態(tài)性，所以保留對資源的短期預(yù)測；因為適合網(wǎng)格計算的應(yīng)用在劃分時很容易轉(zhuǎn)化為同樣大小的子任務(wù)，所以忽略對任務(wù)的預(yù)測。
(2)分配策略可以很好地支持動態(tài)性，即節(jié)點的動態(tài)退出。若某資源節(jié)點P1不知原因地退出了網(wǎng)格，如用戶誤操作、自身系統(tǒng)出問題等，則分配給它的子任務(wù)V1總是無法完成。但是按照分配策略，V1總會被分配在節(jié)點集的其他資源上執(zhí)行，最終V1會被執(zhí)行完。這時P1上V1的運行情況已經(jīng)不重要了。
(3)調(diào)度器和分配器的協(xié)作達到了負載均衡的效果。若節(jié)點機P1負載小，則它的計算節(jié)點的性能參數(shù)小，獲得新任務(wù)的幾率大；當它的負載逐漸變大時，計算節(jié)點的性能參數(shù)也變大，獲得新任務(wù)的幾率變小，新的任務(wù)會向其他性能好的節(jié)點分配，同時在其任務(wù)隊列中的任務(wù)，也會因為任務(wù)在別處提前完成而被逐漸刪除。
(4)該算法適用于以計算為主的網(wǎng)格。以計算為主的應(yīng)用結(jié)果容易比較，但有可能出現(xiàn)各機器精度不一致的情況。這時可以對所需要的精度范圍作出規(guī)定，對結(jié)果進行簡單處理后再比較。
本文給出了基于冗余分配的調(diào)度模型，適用于以出賣計算力為目的的網(wǎng)格。希望此算法能為今后的網(wǎng)格研究提供一定的思路。
參考文獻
1 徐志偉，李 偉.織女星網(wǎng)格的體系結(jié)構(gòu)研究.計算機研究與發(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并行計算環(huán)境中的負載監(jiān)測與預(yù)報系統(tǒng).上海交通大學碩士論文集，2002