基于冗余分配的網(wǎng)格任務調(diào)度模型

1、    基于冗余分配的網(wǎng)格任務調(diào)度模型        宋 瑋 時間:2008年07月15日     字 體: 大 中 小        關鍵詞:<"cblue" " target='_blank'>任務調(diào)度<"cblue" " target='_blank&

2、#39;>資源調(diào)度器<"cblue" " target='_blank'>調(diào)度器<"cblue" " target='_blank'>信息服務<"cblue" " target='_blank'>預測器            摘要： 研究了現(xiàn)有的調(diào)度算法，針對以出賣計算力為目的的網(wǎng)格，提出了基于冗余

3、分配的調(diào)度模型，通過冗余分配實現(xiàn)了具有計算結果驗證功能的調(diào)度算法。對該算法中的<"cblue" " title="預測器">預測器、資源<"cblue" " title="信息服務">信息服務、<"cblue" " title="調(diào)度器">調(diào)度器" title="<"cblue" " title="資源調(diào)度器">資源調(diào)度器&quo

4、t;>資源調(diào)度器及分配器進行了詳細介紹。關鍵詞： 網(wǎng)格計算 <"cblue" " title="任務調(diào)度">任務調(diào)度 冗余分配 結果驗證網(wǎng)格(Grid)是新一代的分布式計算環(huán)境與基礎設施，它提供無縫的、面向主題的全面資源共享和高性能計算。它向人類描繪了一臺虛擬的超級計算機畫面，整個網(wǎng)格就是一臺計算機，其資源可以取之不盡、用之不竭。目前，比較有影響的網(wǎng)格體系結構為國內(nèi)的織女星網(wǎng)格體系結構1、五層沙漏結構2、開放網(wǎng)格服務體系結構3(OGSA)和開放網(wǎng)格服務基礎結構4(OGSI)。任務調(diào)度是這些體系結構中必不可少的環(huán)節(jié)，因為用戶的請

5、求最終會被分置到網(wǎng)格的各資源節(jié)點上執(zhí)行，從而最小化任務的執(zhí)行時間，充分利用網(wǎng)格資源。在網(wǎng)格計算中，通過對網(wǎng)格中計算力資源的整合，充分使用網(wǎng)格中的剩余計算力是一種最常見的利用資源的形式。在這種以出賣計算力為主的網(wǎng)格中，一個客戶無法知道陌生的遠端機計算出來的結果的正確性：有可能遠端機為了獲取經(jīng)濟利益故意偽造結果；或是遠端主機本身的處理能力不夠，如產(chǎn)生了錯誤的浮點結果等5。本文針對該問題研究了現(xiàn)有的網(wǎng)格調(diào)度算法，并對以出賣計算力為主的網(wǎng)格提出了基于冗余分配的調(diào)度模型。1 網(wǎng)格中的調(diào)度算法任務調(diào)度是根據(jù)任務的信息和資源的信息采用適當?shù)牟呗园巡煌娜蝿辗峙涞胶线m的資源節(jié)點上運行的過程。網(wǎng)格中任務調(diào)度的特

6、點為：(1)導致網(wǎng)格資源異構并且狀態(tài)多變的因素主要有客觀和主觀兩方面?？陀^上，網(wǎng)格是大范圍的環(huán)境，自然會有很多意外的情況發(fā)生，這要求調(diào)度中具有預測系統(tǒng)，通過資源的歷史記錄對其現(xiàn)況進行預測。主觀上，網(wǎng)格環(huán)境中大多數(shù)網(wǎng)格成員并不是專門為計算網(wǎng)格中的任務服務，只是提供部分計算力完成某些任務。資源的所有者并不希望它的資源專門為網(wǎng)格服務，因此會為自己的資源加上某些限制，如閑置周期以及用戶對資源的使用權限等。同時資源的所有者有其自身的本地任務，不可能為網(wǎng)格上的遠程任務提供完全的服務。在這種環(huán)境下的任務調(diào)度要復雜一些。(2)由于任務對資源的需求各異，網(wǎng)格環(huán)境中的調(diào)度器必須綜合考慮應用和服務質(zhì)量的約束，以獲得

7、應用與資源之間較好的匹配，因此提出了基于服務質(zhì)量的調(diào)度算法。這里服務質(zhì)量的概念對于不同的資源可能有不同意義。例如，對于網(wǎng)絡資源，QoS可為提供給應用程序的可用帶寬；而對CPU資源，QoS意味著任務所想獲得的處理速度，如浮點運算速度6。(3)現(xiàn)有的調(diào)度算法都是基于粗粒度，并且相互之間獨立或只有極少聯(lián)系的任務。因為若任務聯(lián)系過密，會導致通信量增加，反而使整個計算效率下降。這樣，適合于網(wǎng)格計算的通常是一些容易分割成相互獨立子任務的應用。任務調(diào)度的基本思路可概括如下：任務ti在機器mj的期望執(zhí)行時間ETij(Expected Execution Time)定義為mj空載時執(zhí)行ti的總時間。ti在機器m

8、j的期望完成時間CTij定義為最終完成的時間(應包括完成其前面所有任務的時間)。設ai是ti的到達時間，bi是ti的開始時間，則CTijbiETij。常用的調(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

9、(metric1，metric2)(9) compute minimum CTm，n(10) schedule task m on n(11) end while算法需要不斷地計算未調(diào)度的任務的期望完成時間。(2)(4)為計算每個任務在每個機器上的期望完成時間；(6)是按照某種評價方式f1對任務i在每臺機器上的期望完成時間得出其評價值metrici；(8)為使用某種標準f2在每個任務的評價值中找出符合標準要求的最優(yōu)的任務與機器的匹配match(m，n)；最后將任務m分配到機器n上執(zhí)行。例如，Min-min和Max-min算法定義評價方式f1為取最小的完成時間，即某個任務i的metric值為它在

10、所有機器上的完成時間的最小值。不同的是，Min-min的標準f2是選擇metric值中的最小值，而Max-min是選擇最大值。從上面的分析可以看出，一個好的調(diào)度取決于兩個方面，即對資源系統(tǒng)信息的預測及對應用程序(也可以認為是任務信息)的預測。資源系統(tǒng)的信息包括使用率、任務服務的速率、任務到達的速率等；應用程序的信息為工作量、可分割性、可并行性、完成時間等。一個關鍵的問題是：當為某些子任務指定的資源顯示出不正常的狀態(tài)時(從它的歷史數(shù)據(jù)中預測而得)，如何保證并行應用的性能，即調(diào)度系統(tǒng)應在執(zhí)行期間預測出資源的不正常狀態(tài)(如負載過重)，重新安排調(diào)度。因此，一個調(diào)度算法是否成功取決于系統(tǒng)及應用狀態(tài)預測的

11、精確度。這種預測是從其歷史信息中獲得的。根據(jù)預測的性質(zhì)可將調(diào)度分為兩種：一種是基于短期預測的調(diào)度，如AppLe項目使用了NWS服務提供的短期預測系統(tǒng)；另一種是基于長期預測的調(diào)度，采用這種方式的是GHS(Grid Harvest Service)。2 基于冗余分配的調(diào)度算法通過網(wǎng)格購買空閑的計算力有很大的發(fā)展前景，但這種方法很難保證所獲得的計算力能夠計算出正確的結果。這里提出冗余分配任務，使之在二個或多個節(jié)點上運行。其結果被多次驗證后認為是正確的。調(diào)度模型由資源調(diào)度器、任務分配器、資源信息服務和預測器構成。資源調(diào)度器從現(xiàn)有網(wǎng)格中的節(jié)點資源中找出合適的節(jié)點集，它和資源信息服務配合使用；任務分配器將

12、任務分配到節(jié)點集中；資源狀態(tài)預測需要消耗計算力，所以這里只做簡單預測，同時忽略對任務信息的預測。2.1 預測器這里對計算資源的狀況進行簡單的短期預測。預測由計算資源節(jié)點提供，目的是減輕資源調(diào)度器的負擔。預測器收集節(jié)點自身信息并在資源調(diào)度器需要時給出預測值，它作為一個后臺程序一直運行在節(jié)點機上。一旦節(jié)點開始運行，就主動加入網(wǎng)格，提供自身的信息。預測器獲得系統(tǒng)的基本信息和可變信息。基本信息只需一次性獲得，在資源加入節(jié)點時提供給資源調(diào)度器；可變信息隨著時間變化，主要包括CPU的使用率和內(nèi)存使用率。短期預測策略方式如下：(1)設置一個線程，每隔1s收集一次動態(tài)信息，如CPU的使用率和內(nèi)存的使用率。(2

13、)設置一個循環(huán)隊列，將一分鐘內(nèi)的平均值不斷地寫入該隊列。(3)當有預測需求時將隊列中的數(shù)值讀出再取其平均值作為預測值。例如，當隊列的大小設為5時就表示使用前五分鐘的平均值作為預測值。2.2 資源信息服務提供資源信息服務的是哈希表，該哈希表的信息組織形式如圖1所示。哈希表為調(diào)度器查找資源節(jié)點集提供依據(jù)。哈希表的key以節(jié)點狀態(tài)表示。因為節(jié)點狀態(tài)是時刻變化的，所以對節(jié)點可用性的描述不需要用十分精確的定量方式得出具體的數(shù)值，可采用模糊的定性的方式表述7，即設置median、vacant、very vacant、busy、very busy五種狀態(tài)，以計算節(jié)點的性能參數(shù)wholePerformace作

14、為分類標準。例如：wholePerformace>=85，其狀態(tài)為very busy；wholePerformace(60，85)，為busy；wholePerformace40，60，為median；wholePerformace(20，40)，為vacant；whole-Performace0，20，為very vacant。2.3 資源調(diào)度器調(diào)度器為某一應用找到合適的資源節(jié)點集。其策略為當要分配某一節(jié)點時再次獲取它的信息，以該最新信息作為調(diào)度的標準。描述如下：(1)獲得應用的子任務數(shù)，并以其作為資源個數(shù)的最大請求數(shù)。(2)在哈希表中從資源情況最好的隊列中開始查詢，如“very va

15、cant”隊列。(3)從該隊列中依次取節(jié)點，并依次與節(jié)點對應的計算資源聯(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)整個查詢結束的條

16、件是：當找到子任務數(shù)個資源或是當資源數(shù)少于子任務數(shù)時，直接把所有的資源分給應用。(6)當是單任務應用時，需找出兩個或多個資源。2.4 分配器(1)冗余分配當分配器獲得合適的資源節(jié)點集后，就要決定如何安排子任務到各合適的機器上，以獲得最佳的性能。這里提出一種冗余分配策略，即將一個子任務分配到多個機器上執(zhí)行。采取這種方式的原因是：在分配節(jié)點集的時候是一種模糊分配，因為對資源信息的描述采用定性的方式。在描述資源性能時并未考慮網(wǎng)絡的狀態(tài)而且未對應用程序信息做出預測。所以，在同一個狀態(tài)隊列中，性能參數(shù)wholePerformace大的計算節(jié)點的運算結果有可能先于性能參數(shù)wholePerformace小的

17、到達。冗余分配可以實現(xiàn)冗余執(zhí)行，冗余執(zhí)行具有兩種功能。其一，如所述，若將一個任務發(fā)送到多個節(jié)點執(zhí)行，現(xiàn)狀最好的節(jié)點會最早將結果送回。這樣可以以較快的速度獲得結果，同時避免了只發(fā)送到一個計算節(jié)點的缺點：若出現(xiàn)意外情況，需要重新調(diào)度任務到節(jié)點。其二，冗余的執(zhí)行可以實現(xiàn)結果驗證的功能。(2)分配算法分配器的算法描述如下：對于每個子任務設置三個標志位：“分配狀態(tài)”，其值為整數(shù)，說明分配的次數(shù)，初值為0；“已獲得結果”，記錄獲得的資源節(jié)點計算的結果，若存在相等的結果，則為該子任務打上“刪除標記”。分配器一開始將子任務隨機分配到調(diào)度器所找出的資源集上，分配狀態(tài)變?yōu)?；若有資源送回子任務的計算結果，則將該結

18、果記錄到相應的標志位；若存在相等的結果，則為該子任務打上刪除標記，并且通知其他運行該任務的計算節(jié)點停止該任務的計算，若不存在，各標住位不能做任何改變；同時再次隨機選擇一個未打上刪除標記的子任務，將其分配到剛送回結果的計算資源上，分配狀態(tài)相應加1。整個分配結束的條件是所有的子任務都打上刪除標記。3 算法性能評價(1)減輕了預測的工作量。因為資源具有動態(tài)性，所以保留對資源的短期預測；因為適合網(wǎng)格計算的應用在劃分時很容易轉(zhuǎn)化為同樣大小的子任務，所以忽略對任務的預測。(2)分配策略可以很好地支持動態(tài)性，即節(jié)點的動態(tài)退出。若某資源節(jié)點P1不知原因地退出了網(wǎng)格，如用戶誤操作、自身系統(tǒng)出問題等，則分配給它的

19、子任務V1總是無法完成。但是按照分配策略，V1總會被分配在節(jié)點集的其他資源上執(zhí)行，最終V1會被執(zhí)行完。這時P1上V1的運行情況已經(jīng)不重要了。(3)調(diào)度器和分配器的協(xié)作達到了負載均衡的效果。若節(jié)點機P1負載小，則它的計算節(jié)點的性能參數(shù)小，獲得新任務的幾率大；當它的負載逐漸變大時，計算節(jié)點的性能參數(shù)也變大，獲得新任務的幾率變小，新的任務會向其他性能好的節(jié)點分配，同時在其任務隊列中的任務，也會因為任務在別處提前完成而被逐漸刪除。(4)該算法適用于以計算為主的網(wǎng)格。以計算為主的應用結果容易比較，但有可能出現(xiàn)各機器精度不一致的情況。這時可以對所需要的精度范圍作出規(guī)定，對結果進行簡單處理后再比較。本文給出了基于冗余分配的調(diào)度模型，適用于以出賣計算力為目的的網(wǎng)格。希望此算法能為今后的網(wǎng)格研究提供一定的思路。參考文獻1 徐志偉，李 偉.織女星網(wǎng)格的體系結構研究.計算機研究與發(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