（計(jì)算機(jī)應(yīng)用技術(shù)專業(yè)論文）基于蟻群算法的網(wǎng)格多qos任務(wù)調(diào)度研究.pdf

大連理工大學(xué)碩士學(xué)位論又 摘要 任務(wù)調(diào)度是網(wǎng)格研究的一個(gè)熱點(diǎn)問(wèn)題，任務(wù)調(diào)度本身是個(gè)n p 難解問(wèn)題，又加之網(wǎng) 格的動(dòng)態(tài)性、分布性、異構(gòu)性和自治性，使得網(wǎng)格下的任務(wù)調(diào)度更加復(fù)雜。蟻群算法固 有的并發(fā)性和可擴(kuò)充性等特性，使它適合用于解決網(wǎng)格計(jì)算的任務(wù)調(diào)度問(wèn)題。服務(wù)質(zhì)量 也是衡量網(wǎng)格性能的一個(gè)重要指標(biāo)，在網(wǎng)格的任務(wù)調(diào)度過(guò)程中應(yīng)該在調(diào)度目標(biāo)函數(shù)中綜 合考慮用戶的q o s 需求。 本文給出了一個(gè)網(wǎng)格多q o s 約束任務(wù)調(diào)度模型，以帶有q o s 約束的任務(wù)為研究對(duì) 象，結(jié)合蟻群算法，提出了2 個(gè)基于蟻群算法的網(wǎng)格任務(wù)調(diào)度算法( q a c o 和q i a c o ) 。 q a c o 是將螞蟻系統(tǒng)應(yīng)用到網(wǎng)格多q o s 任務(wù)調(diào)度中。由于對(duì)于更大一些規(guī)模的計(jì)算， 螞蟻系統(tǒng)的求解能力有限，算法的性能會(huì)下降。很多學(xué)者又提出了一些改進(jìn)的蟻群算法， 其中蟻群系統(tǒng)是效果比較好的一種算法。本文結(jié)合隨機(jī)交換局部搜索來(lái)改進(jìn)蟻群系統(tǒng)， 再將其應(yīng)用到網(wǎng)格任務(wù)調(diào)度中，再提出了一個(gè)基于改進(jìn)蟻群系統(tǒng)的網(wǎng)格多q o s 任務(wù)調(diào)度 算法( q i a c o ) 。本文重點(diǎn)考慮了5 種q o s 約束：時(shí)間、可靠性、版本、安全性、優(yōu) 先級(jí)，并將q o s 約束轉(zhuǎn)換成效用，調(diào)度目標(biāo)是最大化總效用即用戶滿意度。 本文進(jìn)行了仿真模擬實(shí)驗(yàn)，將本文提出的2 個(gè)基于蟻群算法的網(wǎng)格多q o s 任務(wù)調(diào)度 算法( q a c 0 與q i a c o ) 與改進(jìn)的m i n m i n 算法、q o s m a n m i n 進(jìn)行比較。仿真實(shí)驗(yàn) 表明q i a c 0 比q a c o 有了很大的改進(jìn)，q i a c o 無(wú)論是m a k e s p a n 還是總效用相比同類 算法都有很大的優(yōu)勢(shì)。本文還詳細(xì)說(shuō)明了q i a c o 如何在網(wǎng)格中應(yīng)用實(shí)現(xiàn)，由于時(shí)間有 限，還沒(méi)有實(shí)現(xiàn)，還有一些問(wèn)題有待解決，下一步會(huì)將q i a c 0 實(shí)現(xiàn)，應(yīng)用到真實(shí)的網(wǎng) 格環(huán)境來(lái)檢測(cè)其可行性及性能。 關(guān)鍵詞：網(wǎng)格任務(wù)調(diào)度；蟻群算法；多q o s 約束；效用 基于蟻群算法的網(wǎng)格多q o s 任務(wù)調(diào)度研究 r e s e a r c ho ng r i dm u l t i p l eq o sc o n s t r a i n e ds c h e d u l i n gb a s e do na n t c o l o n yo p t i m i z a t i o n a b s t r a c t t h es c h e d u l i n gp r o b l e mi ng d dp r o v e dt ob en p - h a r di sah o tt o p i c f u r t h e r m o r e ，t h eg r i d h a st h ec h a r a c t e r so fd y n a m i c i t y ，d i s t r i b u t i v e n e s s ，h e t e r o g e n e i t y ，a n da u t o n o m y ，w h i c hm a k e t h eg r i ds c h e d u l i n gm o r ec o m p l e x b e c a u s ea n tc o l o n yo p t i m i z a t i o nh a st h ec h a r a c t e r so f c o n c u r r e n c y ，e x p a n s i b i l i t ya n ds oo n , i ti ss u i tt os o l v et h eg r i ds c h e d u l i n g t h eq u a l i t yo f s e r v i c e ( q o s ) i sa l s oa ni m p o r t a n tm e a s u r eo f t h eg r i d ，t h u s ，w es h o u l dc o n s i d e rt h eu s e r s r e q u i r e m e n to fq o s i ns c h e d u l i n g i nt h i st h e s i s ，w ep r e s e n tam o d e lo fm u l t i p l eq o sc o n s t r a i ni ng r i d f o c u s i n go nt h e m e t a - t a s k 、加mm u l t i p l eq o sd i m e n s i o n sa n dc o m b i n i n gt h ea n tc o l o n yo p t i m i z a t i o n , t w o a n tc o l o n yo p t i m i z a t i o nf o rg r i dt a s ks c h e d u l i n go f m u l t i p l eq o s c o n s t r a i ni sp r o p o s e d ( q a c o a n dq i a c o ) q a c oa p p l yt h ea n ts y s t e mt ot h e 鰣do fm u l t i p l eq o sc o n s t m i n e d s c h e d u l i n g b e c a u s et h ea b i l i t yo f a n ts y s t e mi sl i m i t e da n d t h ep e r f o r m a n c ew i i id e c l i n ea s t os o m el a r g e rs c a l ec o m p u t a t i o n , m a n yi m p r o v e da n tc o l o n yo p t i m i z a t i o nw e r ep r o v e d a n t c o l o n ys y s t e m si so n eo ft h ei m p r o v e da n tc o l o n yo p t i m i z a t i o nw h i c hh a sg o o d p e r f o r m a n c e c o m b i n i n gr a n d o mc h a n g el o c a ls e a r c ht oi m p r o v e a n tc o l o n ys y s t e m s ，ag r i d m u l t i p l eq o sc o n s t r a i n e ds c h e d u l i n gb a s e do ni m p r o v e da n tc o l o m ys y s t e m s ( q t a c o ) h a s b e e np r o p o s e d t h ep r o p o s e dc o n s i d e r i n gf i v ek i n d so fq o sd i m e n s i o n s ：t i m e ，r e l i a b i l i t y , v e r s i o n ，s e c u r i t ya n dp r i o r i t yw h i c ha r et r a n s f o r m e dt ou t i l i t ya st h eh e u r i s t i ci n f o r m a t i o no f t h ea l g o r i t h m w eh a v ed o n et h es i m u l a t i o ne x p e r i m e n t sa n dc o m p a r e dq a c o ，q i a c 0 ，i m p r o v e d m i n m i l la n dq o s m i l l - m i n t h er e s u l t sh a v es h o w nt h a tq i a c op e r f o r m sb e t t e rt h a no t h e r s i i lb o n lm a k e s p a na n dt o t a lu t i l i t y w eh a v ed e s c r i b e dt h ed e t a i l so fh o w p u tt h ea l g o r i t h m q i a c o i n t og r i de n v i r o n m e n t b e c a u s eo ft h el i m i to ft i m et h e r ea r es t i l ls o m ep r o b l e m sm u s t b es o l v e d w ew i l li m p l e m e n tq i a c oa n da p p l yi ti n t ot h er e a lg d de n v i r o n m e n tt op r o v ei t s v a l i d i t yi nt h ef u t u r e k e yw o r d s ：g r i ds c h e d u l i n g ；a n tc o l o n yo p t i m i z a t i o n ；m u l t i p l eq o sc o n s t r a i n ； u t i l i t y i i 大連理工大學(xué)學(xué)位論文獨(dú)創(chuàng)性聲明 作者鄭重聲明：所呈交的學(xué)位論文，是本人在導(dǎo)師的指導(dǎo)下進(jìn)行研究 工作所取得的成果。盡我所知，除文中已經(jīng)注明引用內(nèi)容和致謝的地方外， 本論文不包含其他個(gè)人或集體已經(jīng)發(fā)表的研究成果，也不包含其他已申請(qǐng) 學(xué)位或其他用途使用過(guò)的成果。與我一同工作的同志對(duì)本研究所做的貢獻(xiàn) 均已在論文中做了明確的說(shuō)明并表示了謝意。 若有不實(shí)之處，本人愿意承擔(dān)相關(guān)法律責(zé)任。 學(xué)位論文題目： 基王數(shù)疊箕洼鮑圓整壘q q 曼堡盔調(diào)度玨究一 作者簽名：立亂晶一日期：j 壁牛年乒月二冱日 大連理工大學(xué)專業(yè)學(xué)位碩士學(xué)位論文 大連理工大學(xué)學(xué)位論文版權(quán)使用授權(quán)書(shū) 本人完全了解學(xué)校有關(guān)學(xué)位論文知識(shí)產(chǎn)權(quán)的規(guī)定，在校攻讀學(xué)位期間 論文工作的知識(shí)產(chǎn)權(quán)屬于大連理工大學(xué)，允許論文被查閱和借閱。學(xué)校有 權(quán)保留論文并向國(guó)家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，可以將 本學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫(kù)進(jìn)行檢索，可以采用影印、 縮印、或掃描等復(fù)制手段保存和匯編本學(xué)位論文。 學(xué)位論文題目： 作者簽名： 導(dǎo)師簽名： 日期：型旦年芝月j 魚(yú)日 日期：函年! 三月生日 大連理工大學(xué)碩士學(xué)位論文 1 緒論 1 。1選題背景 i n t e m e t 的出現(xiàn)使得人們能夠大范圍地共享各種信息，也使得人們比以往任何時(shí)候 都更加渴望能夠更廣泛地共享各種資源。使用i n t e m e t 作為底層，研究人員可以將很大 范圍上地理分布的異構(gòu)計(jì)算機(jī)系統(tǒng)集合在一起形成一個(gè)大規(guī)模的計(jì)算平臺(tái)。該領(lǐng)域的研 究產(chǎn)生了個(gè)新的軟件體系結(jié)構(gòu)，我們稱之為網(wǎng)格?；诰W(wǎng)格的問(wèn)題求解就是網(wǎng)格計(jì)算。 近年來(lái)世界各地開(kāi)展了許多相關(guān)的研究項(xiàng)目，研究結(jié)果表明網(wǎng)格計(jì)算確實(shí)是一個(gè)可行的 高性能廣域分布式計(jì)算模型。而網(wǎng)格計(jì)算就是將分布的計(jì)算機(jī)組織起來(lái)協(xié)同解決復(fù)雜的 科學(xué)與工程計(jì)算問(wèn)題。狹義的網(wǎng)格一般被稱為計(jì)算網(wǎng)格( c o m p u t a t i o n a lg r i d ) ，即主要 用于解決科學(xué)和工程計(jì)算問(wèn)題的網(wǎng)格。 網(wǎng)格資源管理系統(tǒng)是網(wǎng)格計(jì)算的核心中間件與用戶級(jí)中間件的重要組成部分，是連 接各類遠(yuǎn)程資源和進(jìn)行任務(wù)協(xié)同調(diào)度的核心基礎(chǔ)設(shè)施。在網(wǎng)格資源管理系統(tǒng)的設(shè)計(jì)與實(shí) 現(xiàn)中，對(duì)任務(wù)調(diào)度策略的研究是其核心內(nèi)容。高效的調(diào)度策略可以充分利用網(wǎng)格系統(tǒng)的 處理能力，從而提高應(yīng)用程序的性能。人們對(duì)網(wǎng)格任務(wù)調(diào)度的研究從未間斷過(guò)，大量的 研究成果對(duì)網(wǎng)格的進(jìn)一步發(fā)展做出了十分巨大的貢獻(xiàn)。從網(wǎng)格的定義可知，“提供非凡 的服務(wù)質(zhì)量”是判斷網(wǎng)格的三個(gè)準(zhǔn)則之一，服務(wù)質(zhì)量q o s 成為網(wǎng)格系統(tǒng)的一個(gè)重要的性 能指標(biāo)l l 】，所以網(wǎng)格的資源調(diào)度策略應(yīng)該考慮用戶的q o s 需求。將網(wǎng)格的這兩個(gè)問(wèn)題綜 合起來(lái)就是要求網(wǎng)格系統(tǒng)要在擁有最好最合理的資源分配方式和資源調(diào)度策略的同時(shí) 還要保證服務(wù)質(zhì)量。因此，如何提高網(wǎng)格系統(tǒng)中的調(diào)度算法的性能，如何保證網(wǎng)格任務(wù) 調(diào)度過(guò)程中的服務(wù)質(zhì)量都是網(wǎng)格發(fā)展道路上需要解決的關(guān)鍵問(wèn)題。本文就是將這兩個(gè)問(wèn) 題結(jié)合起來(lái)，研究網(wǎng)格環(huán)境下帶有多個(gè)q o s 約束的任務(wù)調(diào)度算法。 1 2 課題研究的目的及意義 在網(wǎng)格系統(tǒng)中，它的一塊核心部分就是網(wǎng)格任務(wù)調(diào)度，調(diào)度本身是個(gè)n p 難問(wèn)題， 又加之網(wǎng)格的動(dòng)態(tài)性、分布性、異構(gòu)性和自治性，使得網(wǎng)格下的任務(wù)調(diào)度更加復(fù)雜。人 們對(duì)網(wǎng)格任務(wù)調(diào)度的研究從未間斷過(guò)，關(guān)于這個(gè)問(wèn)題的大量的研究成果對(duì)網(wǎng)格的進(jìn)一步 發(fā)展做出了十分臣大的貢獻(xiàn)。網(wǎng)格系統(tǒng)一般具有動(dòng)態(tài)、分布、跨域、異構(gòu)、虛擬化和智 能型等特點(diǎn)，網(wǎng)格在提供服務(wù)時(shí)涉及到的因素非常多，因此網(wǎng)格應(yīng)用中的服務(wù)質(zhì)量( 即 q o s ) 的協(xié)商和保證變成一項(xiàng)非常復(fù)雜和具有挑戰(zhàn)性的工作。服務(wù)質(zhì)量的好壞、效率的 高低直接關(guān)系到網(wǎng)格系統(tǒng)的性能，因此基于網(wǎng)格應(yīng)用的需求，必須具有非凡的服務(wù)質(zhì)量， 即網(wǎng)格應(yīng)用系統(tǒng)和用戶希望、也迫切需要有q o s 的協(xié)商和保證。非凡的服務(wù)質(zhì)量已經(jīng)成 基于蟻群算法的網(wǎng)格多q o s 任務(wù)調(diào)度研究 為檢驗(yàn)網(wǎng)格性能好壞的標(biāo)準(zhǔn)之一，因?yàn)椴煌挠脩?，甚至同一用戶?duì)服務(wù)的功能、性能、 成本等都有不同考慮。事實(shí)上目前的網(wǎng)格系統(tǒng)大多只能提供部分q o s 功能。 因此，如何提高網(wǎng)格系統(tǒng)中的調(diào)度算法的性能，如何保證網(wǎng)格任務(wù)調(diào)度過(guò)程中的服 務(wù)質(zhì)量都是網(wǎng)格發(fā)展道路上需要解決的關(guān)鍵問(wèn)題。本文的目的在于從網(wǎng)格q o s 特性、網(wǎng) 格q o s 保證機(jī)制等方面研究基于q o s 的任務(wù)調(diào)度算法來(lái)滿足用戶的需求。本文對(duì)網(wǎng)格 環(huán)境下的多q o s 任務(wù)調(diào)度的研究，文中所得出仿真結(jié)果、實(shí)驗(yàn)分析及引入的數(shù)學(xué)理論知 識(shí)，都可作為以后網(wǎng)格的繼續(xù)研究的參考依據(jù)和理論基礎(chǔ)，具有十分重要的意義。 1 3 本文主要內(nèi)容和工作 本文的章節(jié)組織如下： 第一章：緒論，介紹了課題的選擇背景，研究目的和意義，以及論文的主要內(nèi)容與 組織結(jié)構(gòu)。 第二章：對(duì)本文的相關(guān)背景進(jìn)行了介紹，包括網(wǎng)格的概念，網(wǎng)格中間件g l o b u s ，網(wǎng) 格任務(wù)調(diào)度及國(guó)內(nèi)外網(wǎng)格任務(wù)調(diào)度算法研究現(xiàn)狀。 第三章：介紹了網(wǎng)格下的q o s 相關(guān)概念，定義了一個(gè)多。q o s 網(wǎng)格任務(wù)調(diào)度模型， 并且詳細(xì)介紹了本文使用的算法評(píng)價(jià)模型和性能預(yù)測(cè)機(jī)制。 第四章：首先介紹了基本蟻群算法的原理，詳細(xì)闡述了基于螞蟻系統(tǒng)的網(wǎng)格多q o s 任務(wù)調(diào)度( q a c o ) 的基本思想、算法結(jié)構(gòu)等。介紹了螞蟻系統(tǒng)的缺陷及其他改進(jìn)的蟻 群算法，然后詳細(xì)闡述了基于改進(jìn)蟻群系統(tǒng)的網(wǎng)格多q o s 任務(wù)調(diào)度( q i a c o ) 的基本 思想、算法結(jié)構(gòu)等。 第五章：對(duì)本文提出的算法進(jìn)行了仿真模擬，并詳細(xì)分析了仿真結(jié)果。 第六章：主要講解了q i a c o 如何在真實(shí)網(wǎng)格下實(shí)現(xiàn)。 結(jié)論：對(duì)本文的工作進(jìn)行了總結(jié)，并指出了下一步的工作。 1 4 本章小結(jié) 本章首先介紹了本文的選題背景，然后說(shuō)明了課題研究的目的和意義。最后說(shuō)明了 本文的主要內(nèi)容和工作。 大連理工大學(xué)碩士學(xué)位論文 2 相關(guān)背景介紹 2 1 網(wǎng)格概念 網(wǎng)格的概念源于電力網(wǎng)格 2 ( e l e c t r i cp o w e r ：g d d ) 的思想，電力網(wǎng)格是我們比較熟悉 的一種“網(wǎng)絡(luò) ，用戶只需將用電器連上電網(wǎng)，就能使用到電網(wǎng)提供的電，根本就不用 管這個(gè)電是水力發(fā)的電，火力發(fā)的電，還是核能發(fā)的電，也不用管這些電站位于何處。 網(wǎng)格技術(shù)的最終目標(biāo)是讓網(wǎng)格用戶在使用網(wǎng)絡(luò)資源的時(shí)候就如同現(xiàn)在使用電力一樣方 便，希望給最終的使用者提供的是與地理位置無(wú)關(guān)、與具體計(jì)算設(shè)施無(wú)關(guān)的通用計(jì)算能 力。網(wǎng)格詞在2 0 世紀(jì)9 0 年代中期首次被使用，用來(lái)描述用于科學(xué)和工程分布式計(jì)算 的基礎(chǔ)設(shè)施，這種基礎(chǔ)設(shè)施把計(jì)算資源、數(shù)據(jù)存儲(chǔ)設(shè)施、廣域網(wǎng)絡(luò)、儀器設(shè)備等連成有 機(jī)的整體，方便用戶使用這個(gè)基礎(chǔ)設(shè)施中的任何資源。在此之后，網(wǎng)格的概念逐漸被發(fā) 展和擴(kuò)大，最終作為一個(gè)專門的領(lǐng)域來(lái)研究。 網(wǎng)格整合網(wǎng)絡(luò)中的異構(gòu)資源，在動(dòng)態(tài)、多制度的虛擬組織中協(xié)調(diào)資源共享，解決大 規(guī)模挑戰(zhàn)性問(wèn)題【3 j 。它的目標(biāo)是實(shí)現(xiàn)網(wǎng)絡(luò)虛擬環(huán)境下的高性能資源共享和協(xié)同工作，消 除信息孤島和資源孤島。網(wǎng)格的作用是將分散在網(wǎng)絡(luò)上的信息及信息存儲(chǔ)、處理能力以 合理的方式“粘合”起來(lái)，形成有機(jī)的整體，以提供比任何單臺(tái)高性能計(jì)算機(jī)都強(qiáng)大得 多的處理能力，實(shí)現(xiàn)信息的高度融合和共享。傳統(tǒng)的因特網(wǎng)技術(shù)實(shí)現(xiàn)了計(jì)算機(jī)硬件之間 的連通，w e b 技術(shù)實(shí)現(xiàn)了網(wǎng)頁(yè)之間連通，而網(wǎng)格技術(shù)則試圖實(shí)現(xiàn)互聯(lián)網(wǎng)上所有資源的全 面連通，包括計(jì)算資源、存儲(chǔ)資源、通信資源、軟件資源、信息資源、知識(shí)資源等。 與其它的分布式系統(tǒng)相比較，網(wǎng)格計(jì)算有如下的重要特點(diǎn)1 2 】： ( 1 ) 分布與共享：分布性是網(wǎng)格計(jì)算的一個(gè)最主要的特點(diǎn)。網(wǎng)格計(jì)算的分布性， 首先是指網(wǎng)格的資源是分布的，即不同計(jì)算能力的計(jì)算資源、各種類型的數(shù)據(jù)庫(kù)、各種 儀器設(shè)備等分散在地理位置不同的地方。網(wǎng)格資源雖然是分布的，但是它們卻是可以充 分共享的，即網(wǎng)格上的任何資源都可以提供給網(wǎng)格上的任何使用者，共享是網(wǎng)格的目的。 分布是網(wǎng)格硬件在物理上的特征，而共享是在網(wǎng)格軟件支持下實(shí)現(xiàn)的邏輯上的特征，這 兩者對(duì)于網(wǎng)格來(lái)說(shuō)都是十分重要的。 ( 2 ) 自相似性：網(wǎng)格的局部和整體之間存在著一定的相似性，局部往往在許多地 方具有全局的某些特征，而全局的特征在局部也有一定的體現(xiàn)。網(wǎng)格的自相似性在網(wǎng)格 的建造和研究過(guò)程中有重要的意義。 ( 3 ) 動(dòng)態(tài)性與多樣性：對(duì)于網(wǎng)格系統(tǒng)來(lái)說(shuō)，它所擁有的資源和服務(wù)不是一成不變 的。例如原來(lái)?yè)碛械馁Y源，在下一時(shí)刻可能就會(huì)出現(xiàn)故障或者不可用；而原來(lái)沒(méi)有的資 基于蟻群算法的網(wǎng)格多q o s 任務(wù)調(diào)度研究 源，可能會(huì)不斷地加入系統(tǒng)。網(wǎng)格資源的這種動(dòng)態(tài)變化特點(diǎn)要求網(wǎng)格管理必須充分考慮 并解決好這一問(wèn)題。網(wǎng)格資源是異構(gòu)和多樣的。在網(wǎng)格環(huán)境中可以有不同體系結(jié)構(gòu)的計(jì) 算機(jī)系統(tǒng)和類別不同的資源，因此網(wǎng)格系統(tǒng)必須能夠解決這些不同結(jié)構(gòu)、不同類別資源 之間的通信和互操作問(wèn)題。 ( 4 ) 自治性與管理的多重性：網(wǎng)格上的資源，首先是屬于某一個(gè)組織或者個(gè)人的， 資源擁有者有對(duì)他的資源自主的管理能力，這就是網(wǎng)格的自治性。但是網(wǎng)格資源也必須 接受網(wǎng)格的統(tǒng)一管理，這樣才能實(shí)現(xiàn)網(wǎng)格資源的共享和共操作。因此網(wǎng)格的管理具有多 重性，一方面它允許網(wǎng)格資源的擁有者對(duì)網(wǎng)格資源具有自主性的管理，另一方面又要求 網(wǎng)格資源必須接受網(wǎng)格的統(tǒng)一管理。 網(wǎng)格之父i a n f o s t e r 限定網(wǎng)格必須同時(shí)滿足三個(gè)條件f l j ： ( 1 ) 在非集中控制的環(huán)境中協(xié)同使用資源。網(wǎng)格整合各種資源，協(xié)調(diào)各種使用者， 這些資源和使用者在不同控制域中，比如，個(gè)人電腦和中心計(jì)算機(jī)，相同或不同公司的 不同管理單元。網(wǎng)格還解決在這種分布式環(huán)境中出現(xiàn)的安全、策略、使用費(fèi)用、成員權(quán) 限等問(wèn)題。 ( 2 ) 使用標(biāo)準(zhǔn)的、開(kāi)放的和通用的協(xié)議與接口。這些協(xié)議與接口解決認(rèn)證、授權(quán)、 資源發(fā)現(xiàn)和資源存取等基本問(wèn)題。 ( 3 ) 提供非平凡的服務(wù)質(zhì)量。網(wǎng)格允許它的資源被協(xié)調(diào)使用，以得到多種服務(wù)質(zhì) 量，滿足不同使用者的需求。 2 2 網(wǎng)格中間件g io b u s g l o b u s 項(xiàng)目是目前國(guó)際上最有影響的網(wǎng)格計(jì)算項(xiàng)目之一。它發(fā)起于九十年代中期， 其前身是i - w a y 試驗(yàn)環(huán)境項(xiàng)目，它的最初目的是希望把美國(guó)境內(nèi)的各個(gè)高性能計(jì)算中 心通過(guò)高性能網(wǎng)絡(luò)連接起來(lái)，方便美國(guó)的大學(xué)和研究機(jī)構(gòu)使用，提高高性能計(jì)算機(jī)的使 用效率。隨著對(duì)g l o b u s 項(xiàng)目的深入研究，針對(duì)它的目標(biāo)也進(jìn)一步擴(kuò)展，希望通過(guò)g l o b u s 項(xiàng)目可方便對(duì)地理上分布的研究人員建立虛擬組織，進(jìn)行跨學(xué)科的虛擬合作。目前， g l o b u s 項(xiàng)目把在商業(yè)計(jì)算領(lǐng)域中w e bs e r v i c e 技術(shù)融合在一起，希望不僅僅局限于科學(xué) 計(jì)算領(lǐng)域，而且能夠?qū)Ω鞣N商業(yè)應(yīng)用進(jìn)行廣泛的、基礎(chǔ)性的網(wǎng)格環(huán)境支持，實(shí)現(xiàn)更方便 的信息共享和互操作，從而對(duì)商業(yè)模式、工作方式和生活方式產(chǎn)生深遠(yuǎn)的影響。一些重 要的公司，包括m m 和微軟等都曾公開(kāi)宣布支持g l o b u st o o l k i t 。目前大多數(shù)網(wǎng)格項(xiàng)目 都是采用基于g l o b u st o o l k i t 所提供的協(xié)議及服務(wù)建設(shè)的，已經(jīng)被應(yīng)用于全球數(shù)百個(gè)站 點(diǎn)和幾十個(gè)主要的網(wǎng)格汁算項(xiàng)目：n a s a 網(wǎng)格( n a s ai p g ) 、歐洲數(shù)據(jù)網(wǎng)格( d a t a 嘶d ) 和 大連理工大學(xué)碩士學(xué)位論文 美國(guó)國(guó)家技術(shù)網(wǎng)格f n t g ) 等。 g l o b u s 對(duì)信息安全、資源管理、信息服務(wù)、數(shù)據(jù)管理以及應(yīng)用開(kāi)發(fā)環(huán)境等網(wǎng)格計(jì)算 的關(guān)鍵理論和技術(shù)進(jìn)行了廣泛的研究，開(kāi)發(fā)出能在多種平臺(tái)上運(yùn)行的網(wǎng)格計(jì)算工具包軟 件( g l o b u st o o l k i t ) ，能夠用來(lái)幫助規(guī)劃和組建大型的網(wǎng)格試驗(yàn)和應(yīng)用平臺(tái)，開(kāi)發(fā)適合 大型網(wǎng)格系統(tǒng)運(yùn)行的大型應(yīng)用程序。g l o b u si 具包是g l o b u s 最重要的實(shí)踐成果，目前 最新版本是g t 4 e 4 1 。g t 4 的架構(gòu)圖如圖2 1 。 e 習(xí)e 司亙互臣 圖2 1 g l o b u st o o l l ( i 14 架構(gòu)圖 f i g 2 1 t h ef r a m e w o r ko fg l o b u st o o l k i t 如圖2 1 所示g t 4 主要包括5 個(gè)部分：s e c u r i t y ( g s i ，安全) ，為網(wǎng)格通信提供保 密性、完整性和回放保護(hù)( 為了防止監(jiān)聽(tīng)和中間人攻擊) ，并為網(wǎng)格用戶提供單點(diǎn)登錄 和權(quán)限委托的能力；d a t am g m t ( 數(shù)據(jù)管理) ，提供網(wǎng)格下的存儲(chǔ)管理，副本管理、數(shù) 據(jù)傳輸?shù)裙δ?；e x e c u t i o nm g m t ( 任務(wù)管理) ，提供了一個(gè)可靠的執(zhí)行環(huán)境，幫助實(shí)現(xiàn) 信任證書(shū)的管理，從而提交作業(yè)，監(jiān)視作業(yè)的進(jìn)展?fàn)顩r，控制作業(yè)的執(zhí)行情況，并分階 段地處理相關(guān)的數(shù)據(jù)；i n f os e r v i c e ( 信息服務(wù)) ，提供對(duì)網(wǎng)格計(jì)算環(huán)境中信息的發(fā)現(xiàn)、 注冊(cè)、查詢、修改等功能，動(dòng)態(tài)反應(yīng)一個(gè)真實(shí)、實(shí)時(shí)的網(wǎng)格計(jì)算環(huán)境；c o m m o nr u n t i m e ( 公共運(yùn)行庫(kù)) ，支持各個(gè)組件的運(yùn)行。 基于蟻群算法的網(wǎng)格多q o s 任務(wù)調(diào)度研究 2 3 網(wǎng)格任務(wù)調(diào)度問(wèn)題 網(wǎng)格資源管理通常由三個(gè)部分組成【5 】，分別是資源發(fā)現(xiàn)、資源匹配和任務(wù)執(zhí)行。其 中資源發(fā)現(xiàn)部分是在所有可用的資源中找出滿足任務(wù)要求的資源；資源匹配部分是從發(fā) 現(xiàn)的資源中找到一個(gè)最合適的資源分配給任務(wù)，是資源和任務(wù)的匹配；任務(wù)執(zhí)行部分是 把任務(wù)傳送到資源匹配部分找到的資源上去執(zhí)行。資源如何匹配是網(wǎng)格資源管理需要解 決的核心問(wèn)題，對(duì)網(wǎng)格的性能起著決定性的作用。網(wǎng)格的主要目的就是當(dāng)用戶提交任務(wù) 時(shí)，網(wǎng)格可以綜合分析和評(píng)價(jià)所有共享資源，將任務(wù)分配到最合適的資源上執(zhí)行，由于 網(wǎng)格中的用戶數(shù)量巨大，提交任務(wù)種類和數(shù)目千差萬(wàn)別，使得網(wǎng)格的任務(wù)調(diào)度策略顯得 尤其重要。 由于網(wǎng)格系統(tǒng)具有動(dòng)態(tài)、異構(gòu)、廣域的特點(diǎn)，在網(wǎng)格計(jì)算系統(tǒng)下，任務(wù)調(diào)度需要考 慮任務(wù)特性、機(jī)器特性，為不同任務(wù)匹配不同的資源，從而提高系統(tǒng)資源的利用率和任 務(wù)的執(zhí)行效率。由于網(wǎng)格計(jì)算中任務(wù)調(diào)度是一個(gè)n p 完全問(wèn)題，它引起了眾多學(xué)者的關(guān) 注，成為目前網(wǎng)格計(jì)算研究領(lǐng)域的一個(gè)焦點(diǎn)。 網(wǎng)格調(diào)度和傳統(tǒng)分布式系統(tǒng)的調(diào)度系統(tǒng)的主要區(qū)別6 j ： ( 1 ) 有效范圍不同 網(wǎng)格調(diào)度器的有效范圍是i n t e m e t ，網(wǎng)格環(huán)境下資源全局狀態(tài)對(duì)調(diào)度系統(tǒng)而言是不 確定的，對(duì)一般分布式系統(tǒng)而言，資源調(diào)度器是可見(jiàn)的。 ( 2 ) 操作對(duì)象不同 傳統(tǒng)調(diào)度系統(tǒng)面對(duì)的是組織內(nèi)部的，執(zhí)行實(shí)際任務(wù)的計(jì)算單元、存儲(chǔ)單元。而網(wǎng)格 調(diào)度面對(duì)的是不同系統(tǒng)之間的調(diào)度實(shí)例，本身不涉及具體的資源。因此，網(wǎng)格調(diào)度器又 被稱為是元調(diào)度器，它是建立在現(xiàn)有的調(diào)度系統(tǒng)之上的一層中間層，任務(wù)是為不同系統(tǒng) 之間的調(diào)度實(shí)例的協(xié)同工作提供標(biāo)準(zhǔn)的系統(tǒng)服務(wù)和協(xié)議。 ( 3 ) 標(biāo)準(zhǔn)的開(kāi)放性不同 由于不同的系統(tǒng)需要通過(guò)網(wǎng)格調(diào)度系統(tǒng)來(lái)通信，所以勢(shì)必要求通信協(xié)議的標(biāo)準(zhǔn)性和 開(kāi)放性，如w s r f 、w e bs e r v i c e s 、x m l 等。而對(duì)于系統(tǒng)內(nèi)部的調(diào)度器，可以根據(jù)自身 的需要，綜合考慮性能等方面的因素，定制自己的通信協(xié)議。對(duì)網(wǎng)格資源的訪問(wèn)通常需 要遵循資源管理者定義的訪問(wèn)權(quán)限、記帳、優(yōu)先級(jí)和安全機(jī)制，這些機(jī)制是由資源所在 的不同系統(tǒng)來(lái)自主管理的。因此，支持自主系統(tǒng)之間交互的高層調(diào)度服務(wù)( s c h e d u l i n g s e r v i c e ) 是進(jìn)行網(wǎng)格調(diào)度的技術(shù)關(guān)鍵。同時(shí)，調(diào)度系統(tǒng)也需要根據(jù)作業(yè)的實(shí)際情況( 批 處理作業(yè)或?qū)崟r(shí)作業(yè)) 定義不同的調(diào)度策略以滿足q o s ，這些將是網(wǎng)格調(diào)度系統(tǒng)設(shè)計(jì)的 基本原則。 大連理工大學(xué)碩士學(xué)位論文 簡(jiǎn)單地說(shuō)，網(wǎng)格計(jì)算任務(wù)調(diào)度的目標(biāo)就是要對(duì)用戶提交的任務(wù)實(shí)現(xiàn)最優(yōu)調(diào)度，并設(shè) 法提高網(wǎng)格系統(tǒng)的總體吞吐率。具體的目標(biāo)包括：最優(yōu)跨度( m a k e s p a n ) 、服務(wù)質(zhì)量 q o s ( q u a l i t yo fs e r v i c e ) 、負(fù)載均衡( l o a db a l a n c i n g ) 、經(jīng)濟(jì)原則( e c o n o m i cp r i n c i p l e s ) 等。 ( 1 ) 最優(yōu)跨度( 最短完成時(shí)間) 跨度是一個(gè)最主要、最常見(jiàn)的目標(biāo)，指的是調(diào)度的長(zhǎng)度，也就是從第一個(gè)任務(wù)開(kāi)始 運(yùn)行到最后一個(gè)任務(wù)運(yùn)行完畢所經(jīng)歷的時(shí)間?？缍仍蕉陶f(shuō)明調(diào)度策略越好。當(dāng)用戶向網(wǎng) 格系統(tǒng)提交任務(wù)后，最大的愿望是網(wǎng)格系統(tǒng)盡快完成自己的任務(wù)?？梢?jiàn)，實(shí)現(xiàn)最優(yōu)跨度 是用戶和網(wǎng)格系統(tǒng)的共同目標(biāo)。 ( 2 ) 服務(wù)質(zhì)量q o s 網(wǎng)格系統(tǒng)要為用戶提供計(jì)算和存儲(chǔ)服務(wù)時(shí)，用戶對(duì)資源的要求是通過(guò)q o s 形式反映 出來(lái)的。任務(wù)管理與調(diào)度系統(tǒng)在進(jìn)行分配調(diào)度任務(wù)時(shí)，保障網(wǎng)格應(yīng)用的q o s 是完全應(yīng)當(dāng) 的。本文研究的目的是在網(wǎng)格任務(wù)調(diào)度的同時(shí)盡可能地滿足用戶的q o s 需求。 ( 3 ) 負(fù)載均衡 在開(kāi)發(fā)并行和分布計(jì)算應(yīng)用時(shí)，負(fù)載平衡是一個(gè)關(guān)鍵問(wèn)題。網(wǎng)格系統(tǒng)更進(jìn)一步擴(kuò)展 了這個(gè)問(wèn)題。網(wǎng)格任務(wù)調(diào)度是涉及交叉域和大規(guī)模應(yīng)用的調(diào)度。解決好系統(tǒng)的負(fù)載均衡 是一個(gè)非常重要的問(wèn)題。 ( 4 ) 經(jīng)濟(jì)原則 網(wǎng)格環(huán)境中的資源在地理上是廣泛分布的，而且每個(gè)資源都?xì)w屬于不同的組織，都 有各自的資源管理機(jī)制和政策。根據(jù)現(xiàn)實(shí)生活中的市場(chǎng)經(jīng)濟(jì)原則，不同資源的使用費(fèi)用 也應(yīng)是不相同的。市場(chǎng)經(jīng)濟(jì)驅(qū)動(dòng)的資源管理與任務(wù)調(diào)度必須使消費(fèi)雙方( 資源使用者和 資源提供者) 互惠互利，才能使網(wǎng)格系統(tǒng)長(zhǎng)久地發(fā)展下去。 2 4 網(wǎng)格任務(wù)調(diào)度算法研究現(xiàn)狀 目前，國(guó)內(nèi)外已經(jīng)有很多學(xué)者針對(duì)網(wǎng)格下的任務(wù)調(diào)度算法進(jìn)行研究，其中 m i n m i n l 7 1 ，m a x m i n 7 1 ，s u f f e r a g e 蜘等是比較簡(jiǎn)單有效的啟發(fā)式算法。 m i n m i n 算法計(jì)算每個(gè)任務(wù)在各個(gè)資源上的期望完成時(shí)間，獲得每個(gè)任務(wù)的最早完 成時(shí)間及其資源機(jī)器，再將具有最小最早完成時(shí)間的任務(wù)指派給獲得它的資源，指派完 成后就更新資源就緒時(shí)間，并將已分配的任務(wù)從任務(wù)集合中刪除。如此重復(fù)，直到全部 任務(wù)分配完畢。 m a x m i n 算法與m i n m i n 算法的思想基本相同，區(qū)別是m a x m i i l 算法首先考慮長(zhǎng) 任務(wù)，當(dāng)獲得每個(gè)任務(wù)的最早完成時(shí)間及其資源時(shí)，不是將具有最小最早完成時(shí)間的任 基于蟻群算法的網(wǎng)格多q o s 任務(wù)調(diào)度研究 務(wù)進(jìn)行分配，而是對(duì)具有最大最早完成時(shí)間的任務(wù)進(jìn)行分配。但是以上的算法都沒(méi)有考 慮用戶的q o s 需求，之后有學(xué)者提出了以q o s 為指導(dǎo)的任務(wù)調(diào)度算法。 h e 等人【9 】第一次將q o s 約束加入任務(wù)調(diào)度算法中，通過(guò)改進(jìn)經(jīng)典的任務(wù)調(diào)度算法 m i n m i t t 算法，提出了一個(gè)自適應(yīng)、以性能q o s 為向?qū)У膍 i n - m i n 啟發(fā)式算法。該算 法它只考慮了網(wǎng)絡(luò)帶寬約束，網(wǎng)絡(luò)帶寬會(huì)影響任務(wù)完成時(shí)間，因此在某種情況下性能較 好，但是不適合多維q o s 約束的情況。 w e n g 等人【1 0 】對(duì)s u f f e r a g e 算法進(jìn)行改進(jìn)，以平均響應(yīng)時(shí)間作為q o s 約束提出了 q o s s u t t e m g e 算法，在計(jì)算s u f f e r a g e 值時(shí)乘以響應(yīng)率的平方，將響應(yīng)時(shí)間也作為影響 任務(wù)調(diào)度的因素。該算法也只是考慮了平均響應(yīng)時(shí)間一維q o s 情況，同樣也不適用多 q o s 約束。 陳晶等人【l l 】在任務(wù)完成期限和網(wǎng)絡(luò)帶寬的雙重屬性約束下結(jié)合預(yù)測(cè)機(jī)制，提出了網(wǎng) 格資源調(diào)度算法s e n i o r 。根據(jù)網(wǎng)格任務(wù)的預(yù)測(cè)執(zhí)行時(shí)間，調(diào)整任務(wù)的發(fā)送順序和改變分 配的目標(biāo)資源，該算法有比較好的任務(wù)完成率，但是沒(méi)有提出具體的預(yù)測(cè)機(jī)制。 伍之昂等人【1 2 】提出了網(wǎng)格q o s 的層次結(jié)構(gòu)模型，并對(duì)其中承上啟下的虛擬組織層 q o s 參數(shù)進(jìn)行了新的分類和測(cè)量；然后，利用s n a p ( s e r v i c en e g o t i a t i o na n da c q u i s i t i o n p r o t o c 0 1 ) 協(xié)議對(duì)基于網(wǎng)格q o s 層次結(jié)構(gòu)模型的網(wǎng)格q o s 參數(shù)的映射轉(zhuǎn)換過(guò)程進(jìn)行了 分析，并運(yùn)用相關(guān)的網(wǎng)格q o s 的研究改進(jìn)了現(xiàn)有的m i n m i n 算法，與原始m i n m i n 等 算法進(jìn)行比較獲得較好的結(jié)果。 張偉哲等人【1 3 通過(guò)對(duì)多q o s 約束的網(wǎng)格作業(yè)調(diào)度問(wèn)題分析，提出多q o s 約束的網(wǎng) 格作業(yè)調(diào)度問(wèn)題可規(guī)約為多目標(biāo)組合最優(yōu)化問(wèn)題，在此基礎(chǔ)上，通過(guò)引入多目標(biāo)最優(yōu)化 理論及其演化算法，提出了一種解決多q o s 約束的網(wǎng)格作業(yè)調(diào)度多目標(biāo)演化( 多目標(biāo)遺 傳) 算法q o s - n s g a - i i 1 。 在異構(gòu)計(jì)算方面，也有很多學(xué)者提出了結(jié)合服務(wù)質(zhì)量q o s 的任務(wù)調(diào)度算法，并且考 慮了多維q o s 需求。 t r a e yd b r a u n 等人【1 4 】提出了異構(gòu)計(jì)算環(huán)境下關(guān)于獨(dú)立性、優(yōu)先級(jí)、時(shí)間期限和多 個(gè)版本的靜態(tài)任務(wù)調(diào)度算法，針對(duì)帶有多個(gè)q o s 約束的任務(wù)調(diào)度模型，將遺傳算法， g e n i t o r 算法，基于m i n - m i n 的兩階段貪婪算法應(yīng)用于該模型。經(jīng)過(guò)仿真實(shí)驗(yàn)結(jié)果表 明，g e n i t o r 算法相比其他算法有最好的結(jié)果，基于m i n m i n 的兩階段貪婪算法也有 較好的性能，而且運(yùn)行時(shí)間更短。 g o l c o n d ak 等人1 1 5 】采用具有安全性、優(yōu)先級(jí)、最遲完成時(shí)間等q o s 約束的任務(wù)調(diào) 度模型，對(duì)q s m t s i p 、m i n - m i n 、g e n e t i ca l g o r i t h m 、l e a s ts l a c kf i r s t 和s u f f e r a g e 5 種 大連理工大學(xué)碩士學(xué)位論文 啟發(fā)式任務(wù)調(diào)度算法進(jìn)行了比較，在這些算法里添加上q o s 屬性要求來(lái)進(jìn)行改進(jìn)，分別 以用戶滿意數(shù)，m a k e s p a n 和任務(wù)總效用作為指標(biāo)進(jìn)行比較，實(shí)驗(yàn)結(jié)果表明g a 和m i n m i n 都可以獲得比較好的結(jié)果。 因?yàn)榫W(wǎng)格環(huán)境下的任務(wù)調(diào)度是n p 難解問(wèn)題，適合用遺傳算法、粒子種群算法等智 能優(yōu)化算法來(lái)解決，蟻群算法亦是其中一種。蟻群算法的優(yōu)點(diǎn)包括：魯棒性強(qiáng)，具有正 反饋機(jī)制，避免早熟現(xiàn)象等。而且蟻群算法具有很好的擴(kuò)展性即在一個(gè)規(guī)模r l 的問(wèn)題上 求出最優(yōu)解后，再增加m 個(gè)節(jié)點(diǎn)，可在原有基礎(chǔ)上快速找到該問(wèn)題的最優(yōu)解。蟻群算法 的這個(gè)優(yōu)點(diǎn)可以很好的解決網(wǎng)格的動(dòng)態(tài)特性，因此蟻群算法很適合解決網(wǎng)格計(jì)算中的調(diào) 度問(wèn)題。一些基于蟻群算法【1 7 j 的網(wǎng)格調(diào)度算法已被提出，并且獲得了較好的結(jié)果。 z h i h o n g x 等人【l6 j 首次將蟻群算法應(yīng)用到網(wǎng)格任務(wù)調(diào)度中，提出了基于蟻群算法的 網(wǎng)格任務(wù)調(diào)度算法，使用的是基本蟻群算法( 螞蟻系統(tǒng)) 。r u a y s h i u n g 等人1 1 7 】以負(fù)載 平衡為目標(biāo)提出了基于平衡蟻群優(yōu)化網(wǎng)格任務(wù)調(diào)度算法，并將該算法應(yīng)用于真實(shí)的網(wǎng)格 環(huán)境下，取得了較好的結(jié)果。但是它們沒(méi)有考慮q o s 因素。 綜上所述，雖然已經(jīng)有很多學(xué)者在研究網(wǎng)格任務(wù)調(diào)度問(wèn)題時(shí)考慮了q o s 約束，但是 部分算法只考慮了單一的q o s 約束，而考慮了多個(gè)q o s 約束的算法性能并沒(méi)有獲得很大 的提升，與m i n - m i n 算法相比，m i n - m i n 算法仍然占優(yōu)勢(shì)。研究表明蟻群算法可以很好 的解決網(wǎng)格調(diào)度問(wèn)題，但是還沒(méi)有學(xué)者在應(yīng)用蟻群算法時(shí)考慮q o s 約束。本文進(jìn)一步將 蟻群算法應(yīng)用多q o s 約束網(wǎng)格任務(wù)調(diào)度問(wèn)題中，從而提出了基于螞蟻系統(tǒng)的網(wǎng)格多q o s 任務(wù)調(diào)度算法( q a c 0 ) 。由于螞蟻系統(tǒng)的缺陷，出現(xiàn)很多改進(jìn)的蟻群算法，其中蟻群系 統(tǒng)對(duì)調(diào)度問(wèn)題具有很好的效果。大量關(guān)于元啟發(fā)式算法的文獻(xiàn)告訴我們，把局部搜索算 法和生成初始解的機(jī)制相結(jié)合是一條獲得高質(zhì)量解的有效途徑。因此本文再結(jié)合局部搜 索改進(jìn)蟻群系統(tǒng)提出了q i a c 0 算法，并對(duì)改進(jìn)的m i n - m i n 和q o s - m i n m i n 進(jìn)行仿真實(shí)驗(yàn) 對(duì)比。 2 5 本章小結(jié) 本章首先簡(jiǎn)單介紹了網(wǎng)格的基本概念、網(wǎng)格中間件g l o b u s 。然后介紹了網(wǎng)格任務(wù)調(diào) 度問(wèn)題，說(shuō)明了任務(wù)調(diào)度問(wèn)題是網(wǎng)格研究的一個(gè)重要問(wèn)題，是現(xiàn)在研究的熱點(diǎn)。最后分 析了國(guó)內(nèi)外網(wǎng)格任務(wù)調(diào)度算法的研究狀況，并分析了他們的缺陷和不足之處，從而提出 了將蟻群算法和多q o s 約束應(yīng)用到網(wǎng)格任務(wù)調(diào)度問(wèn)題。 基于蟻群算法的網(wǎng)格多o o s 任務(wù)調(diào)度研究 3網(wǎng)格多q o s 任務(wù)調(diào)度模型 服務(wù)質(zhì)量q o s ( q u a l i t yo f s e r v i c e ) 是網(wǎng)格系統(tǒng)的一個(gè)重要的性能指標(biāo)l l j ，所以網(wǎng)格 的資源調(diào)度策略應(yīng)該考慮用戶的q o s 需求。近年來(lái)，這個(gè)問(wèn)題已成為國(guó)內(nèi)外研究的熱點(diǎn)， 即在網(wǎng)格的任務(wù)調(diào)度過(guò)程中為了更好的滿足用戶需求而在調(diào)度目標(biāo)函數(shù)中綜合考慮用 戶q o s 需求的參數(shù)。然而，現(xiàn)在已有的一些任務(wù)調(diào)度算法過(guò)于簡(jiǎn)單，不能滿足對(duì)q o s 的多樣化需求，有些調(diào)度算法中只支持一維的q o s 需求，對(duì)于真正的網(wǎng)格應(yīng)用，用戶與 系統(tǒng)之間的交互應(yīng)該加強(qiáng)，用戶應(yīng)能對(duì)提交的工作提出更多樣的q o s 需求。 本文針對(duì)網(wǎng)格環(huán)境下的任務(wù)調(diào)度問(wèn)題進(jìn)行研究，網(wǎng)格環(huán)境下的任務(wù)調(diào)度模式分為即 時(shí)模式和批模式。即時(shí)模式是每當(dāng)有任務(wù)到來(lái)時(shí)就立刻對(duì)該任務(wù)進(jìn)行調(diào)度，而批模式采 用了周期性和任務(wù)數(shù)量限制相結(jié)合的方式，即在調(diào)度周期到達(dá)或者本次調(diào)度任務(wù)量達(dá)到 規(guī)定數(shù)量時(shí)進(jìn)行調(diào)度算法的執(zhí)行，大部分網(wǎng)格系統(tǒng)都采用批調(diào)度模式進(jìn)行調(diào)度。本文也 采用批模式的調(diào)度方式，批模式調(diào)度中的任務(wù)也稱為元任務(wù)，。元任務(wù)之間是相互獨(dú)立的 【1 8 】。本文設(shè)定每個(gè)任務(wù)都帶有多個(gè)q o s 需求。使用效用函數(shù)將q o s 約束轉(zhuǎn)換成效用， 用于表示用戶的滿意度。雖然從用戶角度來(lái)看，每個(gè)用戶都希望最大化自己的效用，作 為調(diào)度者應(yīng)該最大化所有用戶的效用而不僅僅是單個(gè)用戶的，因此本文的目標(biāo)是從整個(gè) 系統(tǒng)角度考慮，最大化所有用戶的總效用。 3 1 相關(guān)概念定義 網(wǎng)格用戶可能會(huì)對(duì)資源的有一些特殊要求，比如安全性、c p u 速度、網(wǎng)速等，他們 希望能得到盡可能好的服務(wù)。這些要求可以以o o s 的形式包含在用戶提交的任務(wù)中。在 任務(wù)調(diào)度的過(guò)程中，元調(diào)度器將根據(jù)任務(wù)中的o o s 需求，選擇合適的資源與任務(wù)映射， 以滿足用戶的需求。 在大規(guī)模計(jì)算中，q o s 分為可度量的( m e t r i c s ) 和策略性的( p o l i c i e s ) 1 9 o 可度 量的q o s 包括服務(wù)期限等與時(shí)間相關(guān)的參數(shù)和精度等與準(zhǔn)確性相關(guān)的參數(shù)，主要用來(lái)定 義性能參數(shù)，安全需求和任務(wù)之間的相關(guān)性等。策略性的o o s 規(guī)定了一些應(yīng)用的行為來(lái) 控制資源管理器如何處理應(yīng)用。本文主要考慮了可度量的o o s ，定義了網(wǎng)格下的o o s 模 型，參考n 蚰n 5 3 提出的q o s 模型，使之應(yīng)用于網(wǎng)格環(huán)境下，重點(diǎn)考慮以下5 種o o s 約束： 時(shí)間( t i m e l i n e s s ) ：定義了某個(gè)任務(wù)相關(guān)的時(shí)間，可以是任務(wù)的完成時(shí)間、開(kāi)始 時(shí)間、時(shí)間期限、執(zhí)行時(shí)間。本文只考慮時(shí)間期限( d e a d l i n e ) ，每個(gè)任務(wù)都有一個(gè)可 以接受的執(zhí)行時(shí)間期限。 大連理工大學(xué)碩士學(xué)位論文 可靠性( r e l i a b i l i t y ) ：網(wǎng)格中的機(jī)器如果長(zhǎng)時(shí)間運(yùn)行，可能會(huì)失效( 比如死機(jī)、 重啟等) 。當(dāng)機(jī)器失效時(shí)，在該機(jī)器上運(yùn)行的任務(wù)就要重啟，由此可能導(dǎo)致資源的浪費(fèi) 或降低網(wǎng)格的性能。因此給每臺(tái)機(jī)器設(shè)定一個(gè)失敗率，來(lái)考察任務(wù)成功的概率。 版本( v e r s i o n s ) ：網(wǎng)格中可用的資源因?yàn)椴皇菍Ｓ糜诰W(wǎng)格，他們的屬性經(jīng)常改變， 因此將資源的屬性分為多個(gè)版本，任務(wù)可以在不同版本下運(yùn)行。本文主要考慮不同的版 本會(huì)影響任務(wù)的執(zhí)行時(shí)間和用戶的偏好，用戶的偏好是指用戶可能會(huì)更樂(lè)意在某個(gè)版本 下運(yùn)行，因此每個(gè)任務(wù)針對(duì)每個(gè)機(jī)器的不同版本設(shè)定一個(gè)偏好度。 安全性( s e c u r i t y ) ：每個(gè)用戶可能對(duì)他們的任務(wù)和數(shù)據(jù)都有一個(gè)安全等級(jí)要求。 安全要求包括機(jī)密性、一致性、真實(shí)性等。比如對(duì)于數(shù)據(jù)來(lái)說(shuō)，一致性和真實(shí)性很重要。 為了符合用戶的不同需求，給機(jī)器設(shè)定安全等級(jí)來(lái)表示任務(wù)在該機(jī)器上可以獲得的安全 性的高低。 優(yōu)先級(jí)( p r i o r i t y ) ：網(wǎng)格中的資源有限，當(dāng)多個(gè)任務(wù)競(jìng)爭(zhēng)稀有資源時(shí)，調(diào)度者應(yīng) 該優(yōu)先滿足更重要的任務(wù)的o o s 需求。為了評(píng)價(jià)任務(wù)之間的重要性，給每個(gè)任務(wù)設(shè)定優(yōu) 先級(jí)，來(lái)表示任務(wù)的重要性。在實(shí)際應(yīng)用中，用戶可以和調(diào)度者協(xié)商設(shè)定優(yōu)先級(jí)。 雖然本文只提供了這幾種典型的q o s 指標(biāo)，但是本文的參數(shù)定義和解決方案可以應(yīng) 用于更多的q o s 類型。 本文給出了如下的一些參數(shù)定義，方便描述算法并對(duì)算法進(jìn)行仿真模擬： 定義1 ：集合r - ，l ，廠2 ，朋) 表示網(wǎng)格環(huán)境下的m 個(gè)異構(gòu)的計(jì)算資源( 可以是一般 的p c 機(jī)或者集群等) 。 定義2 ：集合t = “，t ：，f 。) 表示一個(gè)任務(wù)集中的n 個(gè)元任務(wù)集合。本文假設(shè)元任 務(wù)之間是相互獨(dú)立的，在執(zhí)行過(guò)程中不會(huì)被打斷。 f e t l l e t l h l 定義3 ：矩陣e t = ji；l 表示任務(wù)預(yù)期執(zhí)行時(shí)間。本文假設(shè)每個(gè)任務(wù)的執(zhí) 【酣。，甜。j 行時(shí)間已經(jīng)預(yù)測(cè)得出，其中，甜，表示任務(wù)t ，在資源，上的預(yù)期執(zhí)行時(shí)間。 定義4 ：m ( z ) ，1 i 刀，表示任務(wù)f ，被分配的資源。 定義5 ：s j = s ) l1 f 玎，1 m ) ，用戶記錄每個(gè)資源上的任務(wù)調(diào)度順序，s ， 為一個(gè)調(diào)度函數(shù)，表示f ，在廠，上的執(zhí)行順序。 定義6 ：y 表示為一個(gè)版本函數(shù)，礦( f ) ，1 f ，7 是任務(wù)t ，執(zhí)行時(shí)的版本。 定義7 ：每個(gè)任務(wù)t ，有巧個(gè)q o s 約束。q 。是r ，的第j 個(gè)q o s 約束的有限或無(wú)限集， 其中1 d r 。q ，為q 7 中f ，的j 維q o s 約束的具體值。q = q f l ，q 2 ，q ，4 ) 為任務(wù)， 基于蟻群算法的網(wǎng)格多q o s 任務(wù)調(diào)度研究 的q o s 的z 維空間，q j = q ，1 ，q ，2 ，q ，西) 為空間上的一點(diǎn)。在本文中d i = 5 ，分別代表 時(shí)間、可靠性、版本、安全性、優(yōu)先級(jí)。 任務(wù)調(diào)度的目標(biāo)是將，z 個(gè)任務(wù)分配到m 個(gè)資源上，并能達(dá)到最大的效益。 3 2 評(píng)價(jià)模型 國(guó)內(nèi)外已經(jīng)提出的許多網(wǎng)格任務(wù)調(diào)度算法中使用了多種性能指標(biāo)。這些性能指標(biāo)大 致可以分為兩類：基于系統(tǒng)的目標(biāo)和基于用戶的目標(biāo)。由于單個(gè)性能指標(biāo)往往不能滿足 實(shí)際應(yīng)用的需要，因此人們提出多q o s t 2 眥1 1 的性能模型。 主要有以下幾種指標(biāo)類型： ( 1 ) 基于系統(tǒng)的指標(biāo) 基于系統(tǒng)的性能模型關(guān)注整個(gè)系統(tǒng)資源的有效利用，通常的指標(biāo)包括系統(tǒng)吞吐量、 資源利用率、效率和公平性等。 系統(tǒng)資源的利用率表明資源的忙閑程度。因?yàn)榫W(wǎng)格的目標(biāo)就在于資源的有效共享和 最大利用，多數(shù)實(shí)際的調(diào)度器以此作為最主要的性能目標(biāo)。然而，系統(tǒng)利用率與應(yīng)用本 身和調(diào)度算法密切相關(guān)：對(duì)于計(jì)算密集型的任務(wù)，系統(tǒng)( c p u ) 利用率自然比存在上下文 切換的幾個(gè)任務(wù)資源利用率高。 系統(tǒng)吞吐量定義為單位時(shí)間內(nèi)完成的任務(wù)個(gè)數(shù)。系統(tǒng)執(zhí)行的任務(wù)數(shù)越多，吞吐量就 越大。然而，系統(tǒng)吞吐量很多時(shí)候需要讓位于其它指標(biāo)。例如，簡(jiǎn)單的最短任務(wù)優(yōu)先算 法具有最大的吞吐量，然而它對(duì)大任務(wù)是不公平的。 效率定義為最佳完成任務(wù)的程度。該指標(biāo)和資源的類型異構(gòu)關(guān)系密切，例如，向量 計(jì)算機(jī)用于計(jì)算關(guān)于向量的問(wèn)題，具有浮點(diǎn)計(jì)算能力的處理機(jī)執(zhí)行浮點(diǎn)運(yùn)算被認(rèn)為是有 效的。效率指標(biāo)通常和提前預(yù)留( a d v a n c er e s e r v a t i o n s ) 機(jī)制相結(jié)合，主要用于資源類型 異構(gòu)的計(jì)算平臺(tái)。 公平性是很難度量的，然而公平性是很多調(diào)度系統(tǒng)追求的目標(biāo)之一，例如操作系統(tǒng) 的多優(yōu)先級(jí)隊(duì)列觀點(diǎn)常用于調(diào)度器的實(shí)現(xiàn)。公平性指標(biāo)和任務(wù)分布情況及用戶期望相 關(guān)，在具體實(shí)現(xiàn)時(shí)需要和某種基于市場(chǎng)經(jīng)濟(jì)的策略相結(jié)合。 ( 2 ) 基于用戶的指標(biāo) 基于用戶的性能指標(biāo)包括應(yīng)用的最短完成時(shí)間( m a k e s p a n ) 、周轉(zhuǎn)時(shí)間、平均延遲和 有限降級(jí)( b o u n d e ds l o w d o w n ) 、帶權(quán)完成時(shí)間和( t o t a lw e i g h t e dc o m p l e t i o nt i m e ) 等。 最短完成時(shí)間是絕大多數(shù)任務(wù)調(diào)度算法所追求的唯一目標(biāo)，最短完成時(shí)間定義為一 個(gè)給定應(yīng)用或應(yīng)用集合中最后一個(gè)任務(wù)的結(jié)束時(shí)間。