基于資源主動(dòng)適應(yīng)的網(wǎng)格依賴任務(wù)調(diào)度研究.pdf

1、網(wǎng)格計(jì)算的出現(xiàn)，使得人們可以利用分布在各地的閑散計(jì)算資源處理較為復(fù)雜的計(jì)算密集型的并行分布式應(yīng)用。然而，如何將應(yīng)用程序的任務(wù)調(diào)度到可用的資源上，是實(shí)現(xiàn)高性能的關(guān)鍵因素之一。任務(wù)調(diào)度直接影響網(wǎng)格應(yīng)用的性能，網(wǎng)格自身的自治性、異構(gòu)性、動(dòng)態(tài)性、分布性等特性則對(duì)傳統(tǒng)的任務(wù)調(diào)度方式及方法提出了新的挑戰(zhàn)。 網(wǎng)格計(jì)算中一個(gè)大型的應(yīng)用程序往往被分解為多個(gè)任務(wù)，由于應(yīng)用程序分解的任務(wù)之間往往存在依賴關(guān)系，因此對(duì)依賴任務(wù)調(diào)度問題的研究具有很高的實(shí)用

2、價(jià)值。對(duì)于由一組依賴任務(wù)構(gòu)成的網(wǎng)格應(yīng)用調(diào)度的首要目標(biāo)是使得該應(yīng)用程序在最短時(shí)間內(nèi)完成，應(yīng)用的執(zhí)行時(shí)間是由為每一個(gè)任務(wù)選取的資源以及任務(wù)的執(zhí)行次序決定的，在異構(gòu)、動(dòng)態(tài)的網(wǎng)格環(huán)境下，不僅資源的處理能力是不同的，資源間的網(wǎng)絡(luò)帶寬也是不同的，因而不同的資源分配使得任務(wù)的執(zhí)行時(shí)間以及任務(wù)間的數(shù)據(jù)傳輸時(shí)間或通信時(shí)間都將是不同的，所以為了獲得應(yīng)用最短執(zhí)行時(shí)間就需要針對(duì)整個(gè)依賴任務(wù)集合進(jìn)行全局優(yōu)化調(diào)度。 可見，為了使得應(yīng)用的執(zhí)行時(shí)間最短，首先需

3、要解決的一個(gè)關(guān)鍵問題是針對(duì)整個(gè)任務(wù)集合生成一個(gè)全局的優(yōu)化調(diào)度方案，然而，網(wǎng)格自身的自治性、動(dòng)態(tài)性使得資源的性能是動(dòng)態(tài)變化的，并且隨時(shí)都可能有新的資源加入或已有的資源退出網(wǎng)格環(huán)境，針對(duì)整個(gè)任務(wù)集合的全局優(yōu)化調(diào)度方案是在確定的網(wǎng)格資源環(huán)境下生成的，在這樣的情況下，如何保證全局優(yōu)化調(diào)度方案的可行性，即如何使得全局優(yōu)化調(diào)度方案有效地適應(yīng)網(wǎng)格資源的動(dòng)態(tài)變化就成為依賴任務(wù)調(diào)度的另外一個(gè)關(guān)鍵問題。顯然，一個(gè)既能進(jìn)行全局優(yōu)化調(diào)度又能夠適應(yīng)網(wǎng)格資源動(dòng)態(tài)變

4、化的調(diào)度方法是解決依賴任務(wù)調(diào)度問題的關(guān)鍵，針對(duì)該問題，本文提出了一個(gè)新的任務(wù)調(diào)度機(jī)制一基于資源主動(dòng)適應(yīng)的網(wǎng)格依賴任務(wù)調(diào)度機(jī)制，該機(jī)制可以描述為：首先根據(jù)任務(wù)的資源需求及任務(wù)間的依賴關(guān)系在當(dāng)前可用資源上進(jìn)行全局優(yōu)化調(diào)度，生成一個(gè)全局優(yōu)化調(diào)度方案；然后，資源狀態(tài)發(fā)生變化后主動(dòng)觸發(fā)對(duì)其所影響的應(yīng)用的調(diào)度計(jì)劃的修正過程，從而使得已經(jīng)生成的調(diào)度方案能夠反映資源的動(dòng)態(tài)變化，達(dá)到適應(yīng)資源動(dòng)態(tài)變化的目的。 本文的主要貢獻(xiàn)在于： 1)提出

5、了一個(gè)新的依賴任務(wù)調(diào)度機(jī)制一基于資源主動(dòng)適應(yīng)的網(wǎng)格依賴任務(wù)調(diào)度機(jī)制，該機(jī)制的基本思想是首先通過全局優(yōu)化方法獲得依賴任務(wù)在當(dāng)前可用資源集合上的全局優(yōu)化調(diào)度計(jì)劃，然后針對(duì)資源的狀態(tài)變化調(diào)整已有的調(diào)度計(jì)劃。該調(diào)度機(jī)制能夠?qū)崿F(xiàn)針對(duì)應(yīng)用進(jìn)行全局優(yōu)化調(diào)度的同時(shí)，還能適應(yīng)網(wǎng)格資源的動(dòng)態(tài)變化，同時(shí)由于對(duì)已有調(diào)度計(jì)劃的調(diào)整過程是由資源狀態(tài)變化主動(dòng)觸發(fā)的，可作為后臺(tái)程序執(zhí)行，因此對(duì)調(diào)度計(jì)劃的調(diào)整過程不會(huì)增加整個(gè)應(yīng)用的執(zhí)行時(shí)間。 2)針對(duì)上述調(diào)度機(jī)制

6、中全局優(yōu)化調(diào)度計(jì)劃生成問題，本文提出了一個(gè)表示任務(wù)與網(wǎng)格資源映射關(guān)系的方法：任務(wù)-資源分配圖(Task-Resource Assignment Graph，T-RAG)，該圖將描述應(yīng)用靜態(tài)信息的任務(wù)圖與動(dòng)態(tài)的網(wǎng)格資源相結(jié)合，在T-RAG的基礎(chǔ)上將全局優(yōu)化調(diào)度計(jì)劃生成問題轉(zhuǎn)化為T-RAG的優(yōu)化選取問題?；谌蝿?wù)-資源分配圖優(yōu)化選取的全局優(yōu)化調(diào)度模型兼顧了任務(wù)間的依賴關(guān)系、資源間的依賴關(guān)系及資源的異構(gòu)性，因而更適合網(wǎng)格中的依賴任務(wù)調(diào)度問題。

7、基于該優(yōu)化調(diào)度模型實(shí)現(xiàn)的算法與其它算法的對(duì)比分析表明，該模型對(duì)于依賴任務(wù)的全局優(yōu)化調(diào)度問題是有效的。 3)為實(shí)現(xiàn)對(duì)全局優(yōu)化調(diào)度計(jì)劃的主動(dòng)調(diào)整，將網(wǎng)格資源的變化抽象為有限的狀態(tài)，本文定義了資源狀態(tài)變遷事件，構(gòu)建了針對(duì)網(wǎng)格資源的有限狀態(tài)機(jī)。資源狀態(tài)發(fā)生變化時(shí)，觸發(fā)有限狀態(tài)機(jī)根據(jù)預(yù)先制定的規(guī)則和算法對(duì)調(diào)度計(jì)劃進(jìn)行調(diào)整，從而使得在資源狀態(tài)變化時(shí)，調(diào)度計(jì)劃依然能夠反映資源的動(dòng)態(tài)變化，從而達(dá)到適應(yīng)資源動(dòng)態(tài)變化的目的。 4)為了提高基

8、于資源主動(dòng)適應(yīng)的網(wǎng)格依賴任務(wù)調(diào)度機(jī)制的效率，提出了面向應(yīng)用的網(wǎng)格資源表示及管理模型，面向應(yīng)用需求的網(wǎng)格資源表示可以獲得針對(duì)某個(gè)應(yīng)用的資源，提高了全局優(yōu)化調(diào)度的效率；面向應(yīng)用執(zhí)行的網(wǎng)格資源表示對(duì)任務(wù)可用資源根據(jù)性能建立了索引，可以提高調(diào)度計(jì)劃的調(diào)整效率。 5)應(yīng)用本文提出的基于資源主動(dòng)適應(yīng)的網(wǎng)格依賴任務(wù)調(diào)度機(jī)制，設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)面向依賴任務(wù)的調(diào)度系統(tǒng)-DTOSS(Dependent Task Oriented Scheduling