（計算機(jī)應(yīng)用技術(shù)專業(yè)論文）計算網(wǎng)格作業(yè)調(diào)度算法的研究.pdf

計算網(wǎng)格作業(yè)調(diào)度算法的研究 摘要 網(wǎng)格計算是借鑒電力網(wǎng)的概念提出來的 利用網(wǎng)絡(luò)把分散在不同地理位鼉的 計算機(jī)組織成一個 虛擬的超級計算機(jī) 其中每一臺參與計算的計算機(jī)就是一 個 節(jié)點 而整個計算環(huán)境是由成千上萬個 節(jié)點 組成的一張 網(wǎng)格 最終 目的是希望用戶在使用網(wǎng)格資源時就像現(xiàn)在使用電力一樣方便 給用戶提供可靠 的 協(xié)調(diào)的 無處不在的和低廉的高端計算能力 計算網(wǎng)格為解決科學(xué)和工程領(lǐng) 域一些大規(guī)模計算問題提供了理想的平臺 作業(yè)調(diào)度是計算網(wǎng)格中一個關(guān)鍵性的研究課題 在網(wǎng)格環(huán)境中 作業(yè)從提交 給網(wǎng)格系統(tǒng)到作業(yè)結(jié)果處理完成 都一直處于網(wǎng)格作業(yè)管理系統(tǒng)的管理之下 由 于網(wǎng)格具有大規(guī)模 異構(gòu) 動態(tài) 分布和自治等特性 如何調(diào)度作業(yè)以滿足用戶 的需求是一個極具挑戰(zhàn)性的問題 在研究分析計算網(wǎng)格作業(yè)調(diào)度算法現(xiàn)有成果的基礎(chǔ)上 本文提出了一種基于 貪心策略的調(diào)度算法和一種自適應(yīng)調(diào)度算法 具體工作如下 1 建立了計算網(wǎng)格作業(yè)調(diào)度的數(shù)學(xué)模型 考慮了網(wǎng)絡(luò)延遲因素后 對模型進(jìn)行 了改進(jìn) 2 目前的作業(yè)調(diào)度算法有一個共同特點 一個作業(yè)只能分配給一個計算節(jié)點 而副本 r e p l i c a 利用了空間并行性 使多個性能不同的計算節(jié)點運行同一 個作業(yè) 其優(yōu)點是在付出一定的資源代價下減少作業(yè)的運行時間 在r e p l i c a 的基礎(chǔ)上 本文提出了一種貪心算法 在算法的不同階段采用不同的貪心策 略 模擬實驗結(jié)果表明該算法可以減少資源浪費 提高系統(tǒng)的資源利用率 3 針對網(wǎng)格環(huán)境的動態(tài)性和異構(gòu)性 本文提出了一種自適應(yīng)調(diào)度算法 該算法 能動態(tài)地調(diào)用合適的調(diào)度算法 提出了一種系統(tǒng)負(fù)載平衡因子的定義 并給 出了一種基于負(fù)載平衡的關(guān)鍵模塊參考設(shè)計 4 總結(jié)了計算網(wǎng)格作業(yè)調(diào)度算法的主要性能評價指標(biāo) 針對提出的算法 給出 了性能評價指標(biāo)的計算公式 關(guān)鍵詞 網(wǎng)格計算 作業(yè)調(diào)度 貪心策略 副本 自適應(yīng) 負(fù)載平衡 r e s e a r c ho fj o bs c h e d u iin ga i g o r i t h min c o m p u t a t i o n a i 3 rf d a b s t r a c t g r i dc o m p u t i n gi sb a s e do np o w e rg r i d i t o r g a n i z e sd i s t r i b u t e d c o m d u t e r sa sa v i r t u a ls u p e rc o m p u t e r b yn e t w o r k e v e r yc o m p u t e r l s c a l l e dan o d e a n da l lt h en o d e sf o r ma g r i d t h et a r g e to fg r i d i s t om a k et h eu s e r sf e e lt h eu s eo fg r i disa sc o n v e n i e n t a su s i n gp o w e r g r i d g r i dc o m p u t i n gp r o v i d e sd e p e n d a b l e c o n s i s t e n t p e r v a s i v e a n d i n e x p e n s i v ea c c e s st oh i g h e n dc o m p u t a t i o n a ic a p a b i l i t i e s i t p r o v i d e s a ni d e a lp l a t f o r mt os o l v el a r g e s c a l ec o m p u t i n g p r o b l e m si ns c i e n t i f i c a n de n g i n e e r i n ga r e a j o bs c h e d u l i n g i sak e yi s s u ei nc o m p u t a t i o n a lg r i d i n g r i d e n v i r o n m e r i t s f r o mj o bs u b m i s s i o nt or e s u ltp r o c e s s i n g a l le v e n t sa b o u t j o b sa r eu n d e rt h ec o n t r o lo fj o bm a n a g e m e n t b e c a u s eg r i de n v i r o n m e n t s a r el a r g e s c a l e h e t e r o g e n e o u s d y o a m i c d is t r i b u t e da n d a u t o n o m o s g r i dj o bm a n a g e m e n ti s c o m p l e xa n dc h a l l e n g i n g r e f e r r i n gc u r r e n tr e s e a r c hr e s u l t s o nj o bs c h e d u li n ga l g o r i t h m si n g r i de n v i r o n m e n t s t h i sp a p e rp r o p o s e saj o bs c h e d u li n ga l g o r i t h mb a s e d o ng r e e d ys t r a t e g ya n das e l f a d a p t i r ea l g o r i t h m o u r r e s e a r c hw o r k s m a i n l yi n c l u d e 1 t h i sp a p e rc o n s t r u c t sam a t h e m a t i c a lm o d e lo fj o bs c h e d u l i n g i n g r i de n v i r o n m e n t s c o n s i d e r i n gt h en e t w o r kd e l a y i m p r o v e m e n t sa r em a d e t ot h em o d e l 2 t h e r ei s n ec o m m o nc h a r a c t e r i s t i ct h a to n ej o bc a no n l yb ea s s i g n e d t oo n en o d ea m o n gt h er e p r e s e n t a t i v ej o bs c h e d u l i n ga l g o r i t h m s r e p l i c a e x p l o i t st h es p a c ep a r a l l e l i s ma n de n a b l e sv a r i o u sn o d e se x e c u t t h e 8 8 m 8 j o b t h eb e n e f i tist h a titr e d u c e st h em a k e s p a n a tt h ee x p e r t s 8o f a d d it i o n a lr e s o u r c ec o n s u m p t i o n t h i sp a p e rp r o p o s e sag r e e d ya l g o r i t h m b a s e do nr e p li c a i ta d o p t sd i f f e r e n tg r e e d ys t r a t e g ya td i f f e r e n tp h a s e o ft h ea l g o r i t h m s i m u l a t i o nr e s u l t ss h o wt h a ti tc a nr e d u c et h er e s o u r e e c o n s u m p t i o na n di m p r o v et h eu t i l i z a t i o n 3 w i t ht h eg r i de n v i r o n m e n t sa r ed y n a m i ca n dh e t e r o g e n e o u s t h i s p a p e rp r o p o s e sas e l f a d a p t i v ea l g o r i t h mw h i c hc a nd y n a m i c a l l yc a l lt h e s u i t a b l es c h e d u l i n ga l g o r i t h m t h ed e f i n i t i o no fl o a db a l a n c ef a c t o ri s a l s op r o p o s e d t h ek e ym o d u l eb a s e do nl o a db a l a n c ei sd e s i g n e d 4 t h i sp a p e rs u m m a r i z e st h ek e yp e r f o r m a n c ee v a l u a t i o nm e t r i c s t h e f o r m u l a sf o rt h ep r o p o s e da l g o r i t h m sp e r f o r m a n c ee v a l u a t i o nm e t r i c sa r e a l s op r e s e n t e d k e y w o r d s g r i dc o m p u t i n g j o bs c h e d u l i n g g r e e d ys t r a t e g y r e p l i c a s e l f a d a p t i v e l o a db a l a n c e i i 獨創(chuàng)聲明 本人聲明所呈交的學(xué)位論文是本人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研究成果 據(jù)我所知 除了文中特別加以標(biāo)注和致謝的地方外 論文中不包含其他人已經(jīng)發(fā)表或撰寫 過的研究成果 也不包含未獲得 注 地遺直基絲盂蔓掛別直盟 笪 奎攔衛(wèi)窒2 或其他教育機(jī)構(gòu)的學(xué)位或證書使用過的材料 與我一同工作的同志對本研 究所做的任何貢獻(xiàn)均已在論文中作了明確的說明并表示謝意 學(xué)位論文作者簽名 王鵬簽字日期 2 輯1 月z 擴(kuò)日 學(xué)位論文版權(quán)使用授權(quán)書 本學(xué)位論文作者完全了解學(xué)校有關(guān)保留 使用學(xué)位論文的規(guī)定 有權(quán)保留并向國家有 關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和磁盤 允許論文被查閱和借閱 本人授權(quán)學(xué)校可以將學(xué) 位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索 可以采用影印 縮印或掃描等復(fù)制手 段保存 匯編學(xué)位論文 保密的學(xué)位論文在解密后適用本授權(quán)書 學(xué)位論文作者簽名 王研馬 導(dǎo)師簽字 鄞島父 簽字日期 珈6 年r 月2 礦日簽字日期 弘彩年r 月矽日 學(xué)位論文作者畢業(yè)后去向 工作單位 通訊地址 電話 郵編 計算網(wǎng)格作業(yè)調(diào)度算法的研究 0 前言 美國阿崗國家實驗室的資深科學(xué)家 美國計算網(wǎng)格項目的領(lǐng)導(dǎo)人i a nf o s t e r 這樣定義網(wǎng)格 網(wǎng)格是構(gòu)筑在因特網(wǎng)上的一組新興技術(shù) 它將高速互聯(lián)網(wǎng) 高 性能計算機(jī) 大型數(shù)據(jù)庫 傳感器 遠(yuǎn)程設(shè)備等融為一體 為科技人員和普通老 百姓提供更多的資源 功能和交互性 因特網(wǎng)主要為人們提供電子郵件 網(wǎng)頁瀏 覽等通信功能 而網(wǎng)格功能更多更強(qiáng) 能讓人們透明地使用計算 存儲等其它資 源 網(wǎng)格計算將改變傳統(tǒng)的c l i e n t s e r v e r 和c l i e n t c l u s t e r 計算機(jī)系統(tǒng)結(jié)構(gòu) 形成新的p e r v a s i v e g r i d 體系結(jié)構(gòu) 這種體系結(jié)構(gòu)將整個網(wǎng)絡(luò)視為一個巨大的 虛擬計算機(jī) 可以提供一體化的 動態(tài)變化的 可靈活控制的 智能的 協(xié)作式 信息服務(wù) 網(wǎng)格把整個因特網(wǎng)整合成一臺巨大的超級計算機(jī) 實現(xiàn)計算資源 存儲資源 數(shù)據(jù)資源 信息資源 知識資源 專家資源的全面共享 當(dāng)然 網(wǎng)格并不一定非 要這么大 事實上 網(wǎng)格的根本特征是資源共享而不是它的規(guī)模 能透明而且高 效率地為用戶提供各種服務(wù) 由于網(wǎng)格計算環(huán)境的資源具有分布共享 資源自治統(tǒng)一管理 資源異構(gòu)和動 態(tài)性等特點 使得網(wǎng)格計算環(huán)境的作業(yè)調(diào)度是一個比較棘手的問題 研究人員面 l 艋很大的挑戰(zhàn) 本文在前人研究成果的基礎(chǔ)上 對作業(yè)調(diào)度算法進(jìn)行了深入地研 究 主要提出了一種基于貪心策略的調(diào)度算法和一種自適應(yīng)調(diào)度算法 本文各部分安排如下 第1 章緒論介紹了研究背景 研究現(xiàn)狀 研究內(nèi)容及意義 第2 章對網(wǎng)格計算技術(shù)進(jìn)行了概述 第3 章給出了計算網(wǎng)格作業(yè)調(diào)度的數(shù)學(xué)模型 在考慮了網(wǎng)絡(luò)延遲因素后 對 作業(yè)調(diào)度的數(shù)學(xué)模型進(jìn)行了一定的改進(jìn) 第4 章首先介紹了目前典型的網(wǎng)格作業(yè)調(diào)度算法 然后在r e p l i c a 的基礎(chǔ)上 提出了基于貪心策略的調(diào)度算法 稱為g r e e d yr e p i c a 算法 貪心策略的目標(biāo) 函數(shù)是作業(yè)運行時間和請求資源大小的乘積 在算法的不同階段采用了兩種截然 相反的貪心策略 目的是提高資源的利用率 最后 通過一個實例來解釋算法的 運行過程 中國海洋大學(xué)碩士畢業(yè)論文 第5 章提出了一種自適應(yīng)調(diào)度算法 由于網(wǎng)格計算環(huán)境存在很多的不確定因 素和隨機(jī)性 資源動態(tài)變化 針對這種情況 提出了一種自適應(yīng)調(diào)度算法 該算 法根據(jù)性能參數(shù)動態(tài)選擇合適的調(diào)度算法 并給出了關(guān)鍵模塊的參考設(shè)計 該模 塊只考慮系統(tǒng)的負(fù)載平衡 第6 章給出了調(diào)度算法性能評價的主要指標(biāo) 并對提出的調(diào)度算法進(jìn)行了仿 真 第7 章對本文所做的工作進(jìn)行了總結(jié) 并指出了需要進(jìn)一步研究的問題 計算網(wǎng)格作業(yè)調(diào)度算法的研究 1 緒論 1 1 研究背景 人類對計算能力的需求是無止境的 隨著人類探索自然活動的深度 廣度不 斷擴(kuò)展 迫切需要功能更強(qiáng) 速度更快的計算機(jī)系統(tǒng) 目前 微處理器的時鐘頻 率已經(jīng)到了g h z 其性能按照摩爾定律在持續(xù)增長 一方面制造技術(shù)與工藝 體 系結(jié)構(gòu)的發(fā)展在不斷地提高著單個計算機(jī)設(shè)備的能力 各種計算資源的計算能力 越來越強(qiáng)大 另一方面 i n t e r n e t 飛速發(fā)展 網(wǎng)絡(luò)速度成倍增長 主干網(wǎng)的帶 寬數(shù)量級從k b s 發(fā)展到g b s 這一切使得聚集地理上分散的計算資源成為可能 目前 一種新的網(wǎng)絡(luò)計算模式一網(wǎng)格計算 已成為產(chǎn)業(yè)界和學(xué)術(shù)界的研究重點 網(wǎng)格計算是指在動態(tài)的 異構(gòu)的 廣域的虛擬組織 v i r t u a lo r g a n i z a t i o n v o 中進(jìn)行的協(xié)同資源共享和問題求解 隨著人們求解問題領(lǐng)域的不斷拓展 所遇到 的問題也越來越復(fù)雜 而且規(guī)模越來越大 解決這些問題所需要的計算能力也在 大幅度提高 例如 天文望遠(yuǎn)鏡每年所產(chǎn)生的數(shù)據(jù)不少于1 0 p e t a b y t e s 處理如 此大的數(shù)據(jù)量 即使是計算能力強(qiáng)大的超級計算機(jī)也不能勝任 此外 隨著信息 技術(shù)的快速發(fā)展 各個地理分散的組織部署了相當(dāng)多的信息處理設(shè)備 這些資源 在大部分時間內(nèi)并沒有被充分利用 它們處于分離狀態(tài) 構(gòu)成了一個個信息孤島 如果我們從用戶角度看計算機(jī)系統(tǒng)總體結(jié)構(gòu)從1 9 6 0 年到2 0 2 0 年的演變 我們可 以總結(jié)一條歷史經(jīng)驗 姑且稱之為三國定律 天下大勢 分久必合 合久必分 每個分 合階段大約主導(dǎo)1 5 年 我們已經(jīng)經(jīng)歷了三種模式 大型機(jī) 終端是早期 的主導(dǎo)模式 其主要優(yōu)點是使用方便和易于管理 其主要缺點是開放性差 不易 擴(kuò)展以及價格昂貴 為克服這些缺點 客戶 服務(wù)器模式應(yīng)運而生 集中在大型 主機(jī)中的服務(wù)器功能被打散分布到多臺獨立的開放式服務(wù)器 通過網(wǎng)絡(luò)與各類客 戶機(jī) 工作站 p c 網(wǎng)絡(luò)終端 n c 等 相聯(lián) 服務(wù)器聚集又被稱為互聯(lián)網(wǎng)數(shù)據(jù) 中心 i d c 和服務(wù)器堆模式 它用一套物理上集中式服務(wù)器同時提供多臺獨立 服務(wù)器的功能 并將盡量多的功能從客戶端移回集中式服務(wù)器端 以提高系統(tǒng)的 可管理性 我們目前正在進(jìn)入一個新的 分 的階段 即服務(wù)器聚集物理上分散 到各地 但仍然保持虛擬的單一系統(tǒng)映像 這也可以看成是一種特殊的 合 即多個i d c 的資源被互連成為一個虛擬的網(wǎng)格計算機(jī) 各種客戶端設(shè)備通過功用 中國海洋大學(xué)碩士畢業(yè)論文 方式使用網(wǎng)格資源 在這個網(wǎng)絡(luò)計算時代 孤立的計算機(jī)系統(tǒng) 軟件和應(yīng)用將被 網(wǎng)絡(luò)化的產(chǎn)品和服務(wù)取代 世界將被互連成為一個開放的 一體化的 資源共享 的全球電腦網(wǎng)絡(luò) 也稱為 全球大網(wǎng)格 g r e a tg l o b a lg r i d 以滿足人類對 計算性能的不斷需求 網(wǎng)格計算是當(dāng)今計算機(jī)科學(xué)領(lǐng)域最新興起的一項有很高學(xué)術(shù)價值和應(yīng)用價 值的研究課題 目前 科學(xué)家們越來越多地使用超級計算機(jī)來研究復(fù)雜現(xiàn)象 例 如 可以用來預(yù)測復(fù)雜的非線性現(xiàn)象 或者是在做實驗之前 就可探索物理參數(shù) 的變化規(guī)律 甚至還可以用來模擬現(xiàn)實世界中所發(fā)生的某些事件 然而超級計算 機(jī)造價極高 通常只有一些特殊的部門 如航天 氣象和軍事等部門才有能力配 置這樣的設(shè)備 此外 某些應(yīng)用對計算能力的要求極高 即使是超級計算機(jī)也無 法勝任 這就需要將高性能計算依托i n t e r n e t 或其他高速網(wǎng)絡(luò)將遍布世界各個 角落的能力于差萬別的計算資源聯(lián)結(jié)在一起 形成大規(guī)模的幾乎可以無限擴(kuò)展的 計算能力 例如由美國n s f 國家自然科學(xué)基金 支持建設(shè)的網(wǎng)格計算系統(tǒng)d t f d i s t r i b u t e dt e r as c a l ef a c i l i t y 就是一個成功的網(wǎng)格計算項目 該系 統(tǒng)利用高速互聯(lián)網(wǎng)絡(luò)將n s c a s d s c a n l 以及加州工學(xué)院等多家高性能計算中心 連接起來 為數(shù)以萬計的科研人員提供了萬億次的計算能力和超過6 0 0 t 的存儲 能力 與傳統(tǒng)的高性能計算機(jī)不同 d t f 不是位于一個地點 而是由網(wǎng)絡(luò)連接起 來的一個計算聯(lián)盟 通過分布在不同地點的高性能計算設(shè)備的接入 d t f 可以很 容易的擴(kuò)展計算能力和存儲能力 d t f 所擁有的每秒1 3 6 萬億次的計算能力大 約是 深藍(lán) 超級計算機(jī)的i 0 0 0 倍 強(qiáng)大的計算和存儲能力使其能夠滿足如生 命科學(xué) 大氣分析 高能物理等眾多領(lǐng)域?qū)Ω咝阅苡嬎愕囊?因此 網(wǎng)格計算 的研究具有很強(qiáng)的現(xiàn)實意義 從網(wǎng)絡(luò)發(fā)展的短暫歷史來看 它對全球經(jīng)濟(jì)的發(fā)展起到了不可忽視的作用 網(wǎng)絡(luò)的第一次浪潮是因特網(wǎng) 實現(xiàn)了全球計算機(jī)的連通 第二次浪潮是萬維網(wǎng) 實現(xiàn)了網(wǎng)頁的連通 第三次浪潮是網(wǎng)格技術(shù) 將實現(xiàn)全球資源的全面連通和共享 i 2 研究現(xiàn)狀 網(wǎng)格計算的重要戰(zhàn)略意義及其廣闊應(yīng)用前景 使其成為當(dāng)今吸引眾多研究人 員和巨大資金投入的研究熱點 4 計算網(wǎng)格作業(yè)調(diào)度算法的研究 美國政府從十年前就開始投資 1 9 9 2 年 美國開始實施高性能計算方面的計 劃h p c c 并投入巨資研究解決 巨大挑戰(zhàn)問題 的環(huán)境 方法和技術(shù) 累計使 用的基礎(chǔ)研究經(jīng)費已近五億美元 美國軍方更為積極 美國國防部已在規(guī)劃實施 一個宏大的計劃 稱為 全球信息網(wǎng)格 g l o b a l i n f o r m a t i o ng r i d 預(yù)計在 2 0 2 0 年完成 英國政府己決定投資1 億英鎊 用來建設(shè) 英國國家網(wǎng)格 u k n a t i o n a lg r i d 隨著網(wǎng)格研究在學(xué)術(shù)界的加速 信息產(chǎn)業(yè)界的大公司也相繼公布了與網(wǎng)格目 標(biāo)一致的研究開發(fā)計劃 惠普 i b m 微軟 s u n 等公司展近取得共識 支持x m l s o a p u d d i 等萬維網(wǎng)標(biāo)準(zhǔn) 從而更有利于開發(fā)新一代的網(wǎng)絡(luò)應(yīng)用 即萬維網(wǎng)服 務(wù) 其目的是將因特網(wǎng)上的資源和信息匯聚在一起 組合成企業(yè)和消費者所需要 的服務(wù) 2 0 0 2 年8 月 i b m 宣布投入四十億美元 啟動一個全公司的 網(wǎng)格計算 創(chuàng)新計劃 將網(wǎng)格計算從學(xué)術(shù)界的科學(xué)計算應(yīng)用擴(kuò)展到商業(yè)應(yīng)用 其它公司也 不甘示弱 s u n 公司宣布推出新的g r i de n g i n e5 3 軟件的b e t a 測試版 該軟 件使企業(yè)內(nèi)的計算機(jī)的連接更為方便 s u n 目前也已啟動了以g r i de n g i n e 分布 式資源管理軟件為基礎(chǔ)的開放源代碼戰(zhàn)略 m i c r o s o f t 的研究部門也積極參與相 關(guān)項目 包括容錯遠(yuǎn)程文件系統(tǒng)f a r m t e 和分布式系統(tǒng)m i l l e n i u m 的建設(shè) i n t e l 大力倡導(dǎo)對等計算 p 2 p 對等計算技術(shù)的主要用途之一是充分挖掘連接在網(wǎng)絡(luò) 上的成千上萬個p c 的處理能力和存儲能力 以處理一些需要大型機(jī) 甚至超級 計算機(jī)才能承擔(dān)的任務(wù) 國外具有代表性的研究項目和成果主要有g(shù) l o b u s 2 1 l e g i o n n i m r o d g n e t s o l v e a p p l e s 和c o n d o r 等 國內(nèi)主要的網(wǎng)格研究項目是織女星 v e g a 網(wǎng) 格 4 項目 g l o b u s 網(wǎng)格項目是由美國阿崗國家實驗室等科研單位共同研發(fā) 是目前國際 上最有影響的網(wǎng)格計算項目之一 它發(fā)起于2 0 世紀(jì)9 0 年代 其最初目的是希望 把美國境內(nèi)的各個高性能計算中心通過高性能網(wǎng)絡(luò)連接起來 方便美國的大學(xué)和 研究機(jī)構(gòu)使用 提高高性能計算機(jī)的使用效率 g l o b u s 項目組認(rèn)為 大型應(yīng)用 項目應(yīng)該由許多組織協(xié)同完成 這些組織通過網(wǎng)格計算環(huán)境形成一個統(tǒng)一的 虛 擬組織 網(wǎng)格計算環(huán)境中的用戶 成員 資源可隨時加入這種虛擬組織 各個 組織擁有的各種資源都可被虛擬組織中的成員共享 并且各成員可以方便地協(xié)同 完成各種分布式應(yīng)用和工作 中國海洋大學(xué)碩士畢業(yè)論文 l e g i o n 是美國維吉尼亞大學(xué)開發(fā)的基于面向?qū)ο蟮木W(wǎng)格操作系統(tǒng) 它和 g l o b u s 類似 提供地理分布的無縫的異構(gòu)系統(tǒng)集成 它是面向?qū)ο蠹夹g(shù)在網(wǎng)格 計算領(lǐng)域應(yīng)用的重要實例 支持透明的調(diào)度 數(shù)據(jù)管理 容錯 站點自治和各種 安全選項 它將網(wǎng)格計算環(huán)境視為一個世界范圍的抽象計算機(jī) 其設(shè)計目標(biāo)是讓 用戶在l e g i o n 環(huán)境中只感覺到 一臺 大的計算機(jī) 而網(wǎng)格計算用戶在這臺大 計算機(jī)上進(jìn)行程序設(shè)計 在l e g i o n 中 一切都是對象 l e g i o n 規(guī)定了對象交互 的消息格式與高級協(xié)議 通過對象的 組方法描述其接口 但是對編程語言和具 體的通信協(xié)議沒有規(guī)定 織女星 v e g a 網(wǎng)格項目是由中國科學(xué)院計算技術(shù)研究所承擔(dān)的研究課題 織女星網(wǎng)格項目的名稱來源于其四個特性 l 通用服務(wù) v e r s a t i l es e r v i c e s 通用服務(wù)與資源 共性技術(shù) 2 輔助智能 e n a b l i n gi n t e l l i g e n c e 自動 自我 動態(tài) 交互 共性智 能支持技術(shù) 3 全局一體 g l o b a lu n i f o r m i t y 連通性 單一系統(tǒng)映像 互操作性 4 自主控制 a u t o n o m o u sc o n t r 0 1 用戶自主 公開標(biāo)準(zhǔn) 以人為中心 織女星網(wǎng)格項目組主要包括知識網(wǎng)格 k n o w l e d g eg r i d 信息網(wǎng)格 i n f o r m a t i o ng r i d 服務(wù)網(wǎng)格 s e r v i c eg r i d 基礎(chǔ)研究和網(wǎng)格操作系統(tǒng) g r i d o p e r a t i n gs y s t e m 五個部分 可以將網(wǎng)格計算的發(fā)展總結(jié)為以下三個階段 1 萌芽階段 9 0 年代早期 主要是建設(shè)千兆測試床 以及進(jìn)行一些元計算實 驗 2 早期實驗階段 在9 0 年代中期到晚期 主要為學(xué)術(shù)研究實驗 3 迅速發(fā)展階段 2 0 0 2 年以來 出現(xiàn)了大量的應(yīng)用社團(tuán)和項目 如i b m g i c r o s o f t s u n 等開展基礎(chǔ)設(shè)施建設(shè)和使用 形成了具有相當(dāng)規(guī)模的g g f g l o b a l g r i df o r u m 組織 1 3 研究內(nèi)容及意義 在網(wǎng)格系統(tǒng)中 有大量的應(yīng)用程序要運行 這些應(yīng)用程序共享網(wǎng)格的各種資 源 如何才能夠合理利用這些資源 獲得最大的網(wǎng)格性能是網(wǎng)格環(huán)境研究需要解 計算網(wǎng)格作業(yè)調(diào)度算法的研究 決的主要問題 同時 資源管理和作業(yè)調(diào)度是連接網(wǎng)格底層與高層功能的紐帶 是協(xié)調(diào)整個網(wǎng)格系統(tǒng)有效運轉(zhuǎn)的中樞 是網(wǎng)格的核心技術(shù)問題 對這部分網(wǎng)格技 術(shù)的研究具有重要的意義 在分布式網(wǎng)格環(huán)境中 由于網(wǎng)格環(huán)境具有動態(tài)性 異構(gòu)性和分布性等特點 使得作業(yè)調(diào)度比傳統(tǒng)集中式操作系統(tǒng)中的作業(yè)調(diào)度要復(fù)雜得多 高效的作業(yè)調(diào)度 算法對于滿足網(wǎng)格用戶的需求和提高系統(tǒng)的效率都是至關(guān)重要的 本文的作業(yè)調(diào) 度模型是針對相互獨立作業(yè) 即作業(yè)之間不存在相互依賴關(guān)系 它們之間沒有數(shù) 據(jù)通信 參數(shù)掃除 p a r a m e t e r s w e e p 應(yīng)用通常就屬于這種類型 參數(shù)掃除應(yīng) 用存在于很多重要的應(yīng)用領(lǐng)域 例如生物信息 數(shù)據(jù)挖掘 商業(yè)模型模擬和電子 c a d 等 它們包含了很多彼此獨立的同構(gòu)作業(yè) 例如 s e t i h o m e 利用互聯(lián)網(wǎng)閑 置計算能力尋找外星生命 每個s e t i h o m e 任務(wù)要花費3 9 萬億個浮點操作 或 者在5 0 0 m h zp e n t i u mi i 上運行大約l o 小時 而每個任務(wù)只需要下載3 5 0 k b 的 數(shù)據(jù)和上傳1 k b 的數(shù)據(jù) 5 l 中國海洋大學(xué)碩士畢業(yè)論文 2 網(wǎng)格技術(shù)概述 2 1 網(wǎng)格計算的概念 網(wǎng)格是借鑒電力網(wǎng)概念提出來的 網(wǎng)格最終目標(biāo)是希望用戶在使用網(wǎng)格時 就如同現(xiàn)在使用電力一樣方便 網(wǎng)格計算的概念最早起源于元計算 m e t a c o m p u t i n g 6 它是由s m a r r 和c a t l e t t 引入的 在i w a y 7 1 項目中提出 了網(wǎng)格計算的概念 雖然對網(wǎng)格計算的研究己經(jīng)有了很大的進(jìn)步 但是到目前為 止 學(xué)術(shù)界和產(chǎn)業(yè)界對什么是網(wǎng)格計算還沒有一個普遍接受的定義 關(guān)于網(wǎng)格概 念仍存在很大的分歧和爭議 有人把網(wǎng)格看成為了下一代互聯(lián)網(wǎng) 國外媒體常用 下一代因特網(wǎng) 國際互聯(lián)網(wǎng)2 等詞語來描述網(wǎng)格相關(guān)的技術(shù) 1 9 9 8 年 i a n f o s t e r 在 網(wǎng)格 一種未來計算基礎(chǔ)設(shè)施藍(lán)圖 8 一書中將網(wǎng)格描述為 網(wǎng)格 是構(gòu)筑在互聯(lián)網(wǎng)上的一組新興技術(shù) 它將高速互聯(lián)網(wǎng) 高性能計算機(jī) 大型數(shù)據(jù) 庫 傳感器 遠(yuǎn)程設(shè)備等融為一體 為科技人員和普通老百姓提供更多的資源 功能和交互性 互聯(lián)網(wǎng)主要為人們提供電子郵件 網(wǎng)頁瀏覽等通信功能 而網(wǎng)格 功能則更多更強(qiáng) 人們可以透明地使用計算 存儲等資源 一個計算網(wǎng)格是一個 硬件和軟件基礎(chǔ)設(shè)施 此基礎(chǔ)設(shè)施提供對高端計算能力可靠的 一致的 普遍的 和不昂貴接入 在2 0 0 0 年的一篇題為 網(wǎng)格剖析 的文章中 指出網(wǎng)格計算 關(guān)心的是 在動態(tài)的 多機(jī)構(gòu)的虛擬組織中協(xié)調(diào)資源共享和協(xié)同解決問題 其核 心概念是 在一組參與節(jié)點 資源提供者和消費者 中協(xié)商資源共享管理的能力 利用協(xié)商得到的資源池共同解決問題 此后 i a nf o s t e r 等人進(jìn)一步完善網(wǎng)格 定義 認(rèn)為網(wǎng)格實際上是滿足如下三個條件的系統(tǒng) l 協(xié)調(diào)非集中控制資源 網(wǎng)格整合各種資源 協(xié)調(diào)各種使用者 這些資源和使用者在不同控制域中 例如 個人電腦和中心計算機(jī) 相同或不同公司的不同管理單元 網(wǎng)格還要解決 在這種分布式環(huán)境中出現(xiàn)的安全 策略 使用費用 成員權(quán)限等問題 否則 只 能算本地管理系統(tǒng)而非網(wǎng)格 2 使用標(biāo)準(zhǔn) 開放 通用的協(xié)議和界面 網(wǎng)格建立在多功能的協(xié)議和界面之上 這些協(xié)議和界面解決認(rèn)證 授權(quán) 資 源發(fā)現(xiàn)和資源存取等基本問題 否則 只算一個具體應(yīng)用系統(tǒng)而非網(wǎng)格 計算網(wǎng)格作業(yè)調(diào)度算法的研究 3 得到非平凡的服務(wù)質(zhì)量 網(wǎng)格允許它的資源被協(xié)調(diào)使用 以得到多種服務(wù)質(zhì)量 滿足不同使用者的需 求 如系統(tǒng)響應(yīng)時間 流通量 有效性 安全性及資源重定位 使得聯(lián)合系統(tǒng)的 功效比其各部分的功效總和要大得多 總之 網(wǎng)格作為一種全新的 更加方便的計算模式 打破了傳統(tǒng)共享與協(xié)作 的限制 以 虛擬組織 的方法 實現(xiàn)了全社會范圍內(nèi)的資源共享與服務(wù)協(xié)作 可以有效地解決目前尚解決不了的復(fù)雜問題 它將徹底改變?nèi)藗儗?計算機(jī)應(yīng)用 的看法 網(wǎng)格可以聯(lián)合并放大全社會的計算能力 解決計算能力的限制 把 資 源 送到你的桌面 把 全社會的計算能力 送到你的桌面 甚至可以把 應(yīng)用 放到網(wǎng)格中完成 連 桌面 都可以節(jié)省 2 2 網(wǎng)格的特點 網(wǎng)格作為一種新出現(xiàn)的基礎(chǔ)性設(shè)施 和其他的系統(tǒng)相比 具有以下幾個重要 特點 1 分布與共享 分布性是網(wǎng)格最主要的特點 網(wǎng)格的分布性首先是指網(wǎng)格資源是分布的 組 成網(wǎng)格的各種物理設(shè)旋分布在不同的地理位置 而不是集中在一起 網(wǎng)格資源雖 然是分布的 但是它們卻是可以充分共享的 共享是網(wǎng)格的目的 沒有共享便沒 有網(wǎng)格 解決分布資源的共享問題是網(wǎng)格的核心任務(wù) 分布是網(wǎng)格硬件在物理上 的特征 而共享是在網(wǎng)格軟件下實現(xiàn)的邏輯上的特征 2 自相似性 自相似性指局部和整體之間存在著一定的相似性 局部往往在許多地方具有 全局的某些特征 而全局的特征在局部也有一定的體現(xiàn) 自相似性的典型例子是 分形模型 自相似性在許多自然和社會現(xiàn)象中都大量存在 一些復(fù)雜系統(tǒng)都具有 這種特征 網(wǎng)格也不例外 可以認(rèn)為國家級的網(wǎng)格是在省一級的網(wǎng)格基礎(chǔ)之上建 造起來的 國家級主干網(wǎng)要有更大的帶寬 只有這樣才可以將不同省份的子網(wǎng)格 連接起來提供滿意的通信服務(wù) 國家級和省級網(wǎng)格都會有各自的計算中心 只不 過在計算能力上有差異而己 它們也都需要管理結(jié)點 只不過國家級的管理結(jié)點 管理功能需要更多 更強(qiáng)大 除了相似性外 整體和部分之間必然有不同的地方 中國海洋大學(xué)碩士畢業(yè)論文 3 動態(tài)性與多樣性 對于網(wǎng)格來說 決不能假設(shè)它是一成不變的 原來擁有的資源或者功能 在 下一時刻可能就會出現(xiàn)故障或者不可用 而原來沒有的資源 可能會隨著時間的 推移不斷地加入進(jìn)來 網(wǎng)格的動態(tài)性包括動態(tài)增加和動態(tài)減少兩個方面的含義 當(dāng)網(wǎng)格資源的動態(tài)減少或者資源出現(xiàn)故障時 要求網(wǎng)格能夠及時采取措施 實現(xiàn) 任務(wù)的自動遷移 做到對高層用戶透明或者盡可能減少用戶的損失 在網(wǎng)格的設(shè) 計與實現(xiàn)時 必須考慮到新的資源能否很自然地加入到網(wǎng)格中來 并且可以和原 來的資源融合在一起 共同發(fā)揮作用 解決網(wǎng)格的擴(kuò)展性問題 網(wǎng)格擴(kuò)展要求體 現(xiàn)在規(guī)模 能力 兼容性等幾個方面 開始網(wǎng)格的規(guī)模往往不是特別大 不需要 也不可能一步到位 但是網(wǎng)格應(yīng)該能夠允許對它自身進(jìn)行多種形式地擴(kuò)展 網(wǎng)格 規(guī)模擴(kuò)展后 網(wǎng)格的相應(yīng)管理軟件也應(yīng)該能夠滿足擴(kuò)展性的要求 網(wǎng)格軟件的升 級要能夠向下兼容 網(wǎng)格資源是異構(gòu)和多樣的 在網(wǎng)格環(huán)境中可以有不同體系結(jié) 構(gòu)的計算機(jī)系統(tǒng)和類別不同的資源 因此網(wǎng)格系統(tǒng)必須能夠解決這些不同結(jié)構(gòu) 不同類型資源之間的通信和互操作問題 4 自治性與管理的多重性 網(wǎng)格上的資源 首先是屬于某一個組織或者個人的 因此網(wǎng)格資源的擁有者 對該資源具有最高級別的管理權(quán)限 網(wǎng)格應(yīng)該允許資源擁有者對他的資源有自主 的管理能力 這就是網(wǎng)格的自治性 但是網(wǎng)格資源也必須接受網(wǎng)格的統(tǒng)一管理 否則不同的資源就無法建立相互之間的聯(lián)系 無法實現(xiàn)共享和互操作 無法作為 一個整體為更多的用戶提供方便的服務(wù) 因此網(wǎng)格的管理具有多重性 一方面它 允許網(wǎng)格資源的擁有者對網(wǎng)格資源具有自主性的管理 另 方面又要求網(wǎng)格資源 必須接受網(wǎng)格的統(tǒng)一管理 2 3 資源的概念 網(wǎng)格資源是網(wǎng)格中所有可以被用戶請求使用的實體的總稱 是所有網(wǎng)格節(jié)點 履行網(wǎng)格協(xié)議要求向網(wǎng)格提供的資源總和 網(wǎng)格就是資源和服務(wù)的集合 服務(wù)表示用于提供訪問某種資源的能力 例如讀取文件和創(chuàng)建進(jìn)程等 服務(wù) 通常以接口的形式提供 在網(wǎng)格計算環(huán)境中通過協(xié)議進(jìn)行請求 資源的共享通過 服務(wù)實現(xiàn) 計算網(wǎng)格作業(yè)調(diào)度算法的研究 網(wǎng)格資源種類繁多 功能各異 可以從不同的角度對資源進(jìn)行劃分 9 l 根據(jù)資源的可移動性 資源可以分為可移動資源 如數(shù)據(jù) 程序 它們 可從一個位置移動到另外一個位置 和不可移動資源 如硬件 設(shè)備 2 根據(jù)資源是否可重復(fù)使用 資源可以分為可重復(fù)使用資源 如c p u 存儲 器 和不可重復(fù)使用資源 如計算周期 網(wǎng)絡(luò)帶寬 3 根據(jù)資源可復(fù)制特性 資源可以分為可復(fù)制資源 如數(shù)據(jù) 應(yīng)用程序 服務(wù) 和不可復(fù)制資源 硬件 從物理的角度看 網(wǎng)格中資源種類繁多而且多為異構(gòu)的 包括掛接在網(wǎng)格上 的各種計算機(jī)軟件 計算機(jī)硬件 存儲系統(tǒng) 分布式文件系統(tǒng) 集群系統(tǒng)以及信 道傳輸能力等 從邏輯的角度看 網(wǎng)格資源是這些具體的物理設(shè)備所能提供的計 算能力 存儲能力 信息服務(wù)等 物理資源是邏輯資源的載體 網(wǎng)格中的資源具有如下特點 9 l 異構(gòu)性 網(wǎng)格中的資源種類繁多 功能各異 訪問接口也各不相同 例如 有的機(jī)器 運行w i n d o w s 操作系統(tǒng) 有的機(jī)器運行l(wèi) i n u x 操作系統(tǒng) 即使運行同一個操作系 統(tǒng) 其運行的操作系統(tǒng)版本也不一樣 2 動態(tài)性 網(wǎng)格中的資源可以自由地隨時加入和離開網(wǎng)格系統(tǒng) 網(wǎng)格資源的可獲得性是 隨時間的變化而動態(tài)變化的 網(wǎng)格資源的負(fù)載也是動態(tài)變化的 3 自治性 網(wǎng)格資源有自己的本地管理機(jī)構(gòu)或處在本地管理機(jī)構(gòu)的管理之下 網(wǎng)格資源 或強(qiáng)或弱的有本地自治能力 4 二分特性 網(wǎng)格資源最終都是由具體的資源擁有者提供的 除了一部分專用的網(wǎng)格資源 是專門提供給網(wǎng)格用戶使用之外 大部分的資源都同時作為網(wǎng)格用戶可以使用的 網(wǎng)格資源和資源擁有者自己使用的本地資源 中國海洋大學(xué)碩士畢業(yè)論文 2 4 網(wǎng)格體系結(jié)構(gòu) 2 4 1 五層沙漏結(jié)構(gòu) 網(wǎng)格體系結(jié)構(gòu)就是關(guān)于如何建造網(wǎng)格的技術(shù) 它給出了網(wǎng)格的基本組成與功 能 描述了網(wǎng)格各組成部分的關(guān)系以及它們集成的方式或方法 刻畫了支持網(wǎng)格 有效運轉(zhuǎn)的機(jī)制 到目前為止 比較重要的體系結(jié)構(gòu)有兩個 一個是i a nf o s t e r 等人在早些時候提出來的五層沙漏結(jié)構(gòu) 另 個是在考慮了w e b 技術(shù)的發(fā)展與影 響后 i a nf o s t e r 等人結(jié)合w e bs e r v i c e s 提出的開放網(wǎng)格服務(wù)結(jié)構(gòu)o g s a o p e n c r i ds e r v i c ea r c h i t e c t u r e 本小節(jié)介紹五層沙漏結(jié)構(gòu) 下 小節(jié)介紹開放網(wǎng) 格服務(wù)結(jié)構(gòu) 五層沙漏結(jié)構(gòu)的主要思想是以 協(xié)議 為中心 每層的功能定義由內(nèi)部協(xié)議 和外部協(xié)議組成 五層沙漏結(jié)構(gòu)側(cè)重于定性的描述而不是具體的協(xié)議定義 因此 很容易從整體上進(jìn)行理解 是一種影響十分廣泛的結(jié)構(gòu) 網(wǎng)格的五層沙漏形狀結(jié) 構(gòu)如圖2 1 所示 圖2 1 五層沙漏結(jié)構(gòu) 1 構(gòu)造層包括計算設(shè)備 存儲設(shè)備 目錄 分布式文件系統(tǒng) 分布式計算 池 計算機(jī)集群 網(wǎng)絡(luò) 傳感器以及貴重儀器等 該層的功能是向上提供網(wǎng)格中 可共享使用的資源接口 網(wǎng)格通過支持設(shè)備共享的協(xié)議來訪問本地設(shè)備 2 連接層主要為下層的物理資源提供安全的數(shù)據(jù)通信能力 使孤立的單個 資源之間建立聯(lián)系 構(gòu)造層的各種資源間的數(shù)據(jù)交換都在這一層的控制下實現(xiàn) 的 計算網(wǎng)格作業(yè)調(diào)度算法的研究 3 資源層反映的是局部資源的抽象特征 資源層建立在連接層的通信與認(rèn) 證協(xié)議基礎(chǔ)之上 是對個人資源安全共享操作的談判 啟動 監(jiān)視 控制 記賬 和支付定義協(xié)議 a p i 和s d k 4 匯聚層的作用是將資源層提交的受控資源匯聚在一起 供應(yīng)用程序共享 使用 該層提供目錄服務(wù) 資源分配 負(fù)載控制 賬戶管理等功能 5 應(yīng)用層包括用戶代碼和網(wǎng)格調(diào)用兩部分 它關(guān)心的是有什么樣的資源可 以提供給網(wǎng)格用戶 解決不同網(wǎng)格用戶的具體問題 五層結(jié)構(gòu)的一個重要特點就是其沙漏形狀 這種形狀可以從兩方面來理解 首先網(wǎng)格環(huán)境中對不同層的服務(wù)需求量是不同的 應(yīng)用層是分布在各個客戶端 的 基本不會發(fā)生爭用 匯聚層只有在多個資源協(xié)調(diào)時使用 爭用的可能性較小 構(gòu)造層分布在各個物理資源 也基本不會發(fā)生爭用 而資源層和連接層是所有任 務(wù)分配和使用資源時都要調(diào)用的部分 是最核心的部分 成為此結(jié)構(gòu)中的瓶頸 同時因為資源層和連接層既要能夠?qū)崿F(xiàn)上層各種協(xié)議向自身的映射 同時又要實 現(xiàn)自身向下層其它各種協(xié)議的映射 在所有支持網(wǎng)格計算的地點都應(yīng)該得到支 持 因此核心協(xié)議與其它層次協(xié)議相比數(shù)量應(yīng)該比較少 以便于實現(xiàn)和移植 2 4 2 開放網(wǎng)格服務(wù)結(jié)構(gòu) 開放網(wǎng)格服務(wù)結(jié)構(gòu)o g s a 是g l o b a lg r i df o r u m4 的重要標(biāo)準(zhǔn)建議 是繼五 層沙漏結(jié)構(gòu)之后最重要 也是最新的一種網(wǎng)格體系結(jié)構(gòu) 目前的大多數(shù)的研究項 目和開發(fā)都已經(jīng)從五層沙漏結(jié)構(gòu)轉(zhuǎn)移到基o g s a 架構(gòu) o g s a 被稱為是下一代的網(wǎng)格體系結(jié)構(gòu) 它是在原來 五層沙漏結(jié)構(gòu) 的基礎(chǔ) 上 結(jié)合最新的w e bs e r v i c e 技術(shù)提出來的 o g s a 包括兩大關(guān)鍵技術(shù) 網(wǎng)格技 術(shù)和w e bs e r v i c e 技術(shù) 把原來按照兩條路線進(jìn)行的研究活動歸納到一條主線上 來 以服務(wù)為中心是o g s a 的基本思想 在o g s a 中一切都是服務(wù) 主要突出從 網(wǎng)格用戶的角度看上去的網(wǎng)格系統(tǒng)結(jié)構(gòu)是什么樣子 在o g s a 框架中 將一切都抽象為服務(wù) 包括計算機(jī) 程序 數(shù)據(jù) 儀器設(shè) 備等 這種觀念 有利于通過統(tǒng) 的標(biāo)準(zhǔn)接口來管理和使用網(wǎng)格 在o g s a 中 服務(wù)的概念更廣泛 包括各種計算資源 存儲資源 網(wǎng)絡(luò) 程序和數(shù)據(jù)庫等 簡 而言之 一切都是服務(wù) 將一切都抽象為服務(wù)有利于通過統(tǒng)一的標(biāo)準(zhǔn)接口來管理 中國海洋大學(xué)碩士畢業(yè)論文 和共享網(wǎng)格上功能各異的資源 服務(wù)可以實現(xiàn)資源共享與資源管理 任務(wù)調(diào)度 網(wǎng)格安全等 還可以訪問網(wǎng)格上的各種分布式資源 在o g s a 中 可以基于簡單 的基本服務(wù) 形成更復(fù)雜 更高級 更抽象的服務(wù) o g s a 架構(gòu)由四個主要的層構(gòu)成 如圖2 2 所示 從下到上依次為 資源 物 理資源和邏輯資源 w e b 服務(wù)以及定義網(wǎng)格服務(wù)的o g s 工擴(kuò)展 基于o g s a 架構(gòu) 的服務(wù) 網(wǎng)格應(yīng)用程序 朗搭應(yīng)用程序 基于o g s a 架構(gòu)的服務(wù) l o g s l w 曲服務(wù) 安全機(jī)制ii 詞典ii 數(shù)據(jù)庫ii ii 文件系統(tǒng) 一1 一i j 1 一1 一 物理與邏輯瓷獗 h q j 服務(wù)器 存赭罨 硒絡(luò)等 圖2 2o g s a 架構(gòu) l 物理和邏輯資源層 資源的概念是o g s a 以及通常意義上的網(wǎng)格計算的中心部分 物理資源通常包 括處理器 存儲器和網(wǎng)絡(luò) 物理資源之上是邏輯資源 它們通過虛擬化和聚合物 理層的資源來提供額外的功能 通用的中間件 例如文件系統(tǒng) 數(shù)據(jù)庫管理員 目錄和工作流管理人員 在物理網(wǎng)格之上提供這些抽象服務(wù) 2 w e b 服務(wù)層 這里有一條重要的o g s a 原則 所有網(wǎng)格資源 邏輯的與物理的 都被建模為 服務(wù) o g s i 規(guī)范定義了網(wǎng)格服務(wù)并建立在標(biāo)準(zhǔn)w e b 服務(wù)技術(shù)之上 o g s i 利用諸 如x m l 與w e b 服務(wù)描述語言 w e bs e r v i c e sd e s c r i p t i o nl a n g u a g e w s d l 這 樣的w e b 服務(wù)機(jī)制 為所有網(wǎng)格資源指定標(biāo)準(zhǔn)的接口 行為與交互 o g s i 進(jìn)一 步擴(kuò)展了w e b 服務(wù)的定義 提供了動態(tài)的 有狀態(tài)的和可管理的w e b 服務(wù)的能力 3 基于o g s a 架構(gòu)的網(wǎng)格服務(wù)層 w e b 服務(wù)層及其o g s i 擴(kuò)展為上一層提供了基礎(chǔ)設(shè)旋一基于架構(gòu)的網(wǎng)格服務(wù) 計算網(wǎng)格作業(yè)調(diào)度算法的研究 g g f 目前正在致力于在諸如程序執(zhí)行 數(shù)據(jù)服務(wù)和核心服務(wù)等領(lǐng)域中定義基于網(wǎng) 格架構(gòu)的服務(wù) 隨著這些新架構(gòu)的服務(wù)開始出現(xiàn) o g s a 將變成更加有用的面向 服務(wù)的架構(gòu) 4 網(wǎng)格應(yīng)用程序?qū)?隨著時間的推移 一組豐富的基于網(wǎng)格架構(gòu)的服務(wù)不斷被開發(fā)出來 使用一 個或多個基于網(wǎng)格架構(gòu)的服務(wù)的新網(wǎng)格應(yīng)用程序亦將出現(xiàn) 這些應(yīng)用程序構(gòu)成了 o g s a 架構(gòu)的第四層 中國海洋大學(xué)碩士畢業(yè)論文 3 計算網(wǎng)格作業(yè)調(diào)度的數(shù)學(xué)模型 3 1 網(wǎng)格作業(yè)調(diào)度概述 首先需要指出的是 在科技論文中存在 任務(wù)調(diào)度 和 作業(yè)調(diào)度 兩種說 法 為了消除歧義 本文統(tǒng)一用 作業(yè) 來表示 網(wǎng)格上的計算資源是一種需要用戶提供代碼使用的資源 通過執(zhí)行用戶代 碼 處理用戶數(shù)據(jù)給用戶提供計算周期 大多數(shù)情況下 用戶都是以提交作業(yè)的 方式使用資源 作業(yè)管理是負(fù)責(zé)管理網(wǎng)格作業(yè)全周期的模塊 作業(yè)是用戶代碼 數(shù)據(jù)及相應(yīng)資源描述信息的集合 9 l 網(wǎng)格中的計算資源經(jīng)過抽象之后 用戶看到 的計算資源只是邏輯資源 用戶不需要指定運行作業(yè)的物理位置 通常在提交作 業(yè)時 只需描述作業(yè)對計算資源的需求情況 例如要求幾個c p u 并行計算 內(nèi)存 不小于5 1 2 m b 計算速度不小于1 0 9 f l o p s 應(yīng)用軟件等 通常 我們一般將集群計算系統(tǒng)的作業(yè)管理系統(tǒng)稱為 局部調(diào)度器 而把 網(wǎng)格作業(yè)調(diào)度系統(tǒng)稱為 全局調(diào)度器 全局調(diào)度器與局部調(diào)度器的區(qū)別是局部 調(diào)度器僅僅管理單一的節(jié)點或集群 并通常擁有資源 而網(wǎng)格調(diào)度器負(fù)責(zé)資源發(fā) 現(xiàn) 資源調(diào)度 資源分配和作業(yè)調(diào)度 和作業(yè)的執(zhí)行管理 這通常要跨越多個自 治域 本文以下如果沒有特別說明 調(diào)度器指網(wǎng)格作業(yè)管理系統(tǒng) 目前 網(wǎng)格系統(tǒng)中的調(diào)度器可以根據(jù)表3 1 進(jìn)行分類 1 1 1 2 表3 1 調(diào)度器的分類 分類指標(biāo)具體分類 調(diào)度器的組織集中 分層 分散 調(diào)度策略 固定的 可擴(kuò)展的 狀態(tài)估計有預(yù)測 啟發(fā)式 機(jī)器學(xué)習(xí) 經(jīng)濟(jì)模型 無預(yù)測 重調(diào)度階段性 事件驅(qū)動 調(diào)度器的組織分為集中式 分層結(jié)構(gòu)和分布式的三種 集中式調(diào)度器易于實 施和管理 易于實現(xiàn)資源的協(xié)同分配 缺點是維護(hù)代價高 難于實現(xiàn)容錯 分層 調(diào)度器易于實現(xiàn)擴(kuò)展和容錯 易于資源的協(xié)同分配 但不支持資源地域自治和多 種調(diào)度策略 分布式調(diào)度器易于擴(kuò)展和容錯 支持資源自治和多種調(diào)度策略結(jié)合 使用 但不易于管理和資源協(xié)同分配 調(diào)度策略可分為固定的和可擴(kuò)展的 固定式調(diào)度又可以分為面向系統(tǒng)的和面 計算網(wǎng)格作業(yè)調(diào)度算法的研究 向應(yīng)用程序的 前者的調(diào)度目標(biāo)是最大化系統(tǒng)吞吐量 后者的調(diào)度目標(biāo)是最優(yōu)化 應(yīng)用程序完成時間 可擴(kuò)展調(diào)度策略又分為a d h o c 類型和結(jié)構(gòu)化類型 前者執(zhí) 行固定調(diào)度策略 但允許系統(tǒng)外部實體修改調(diào)度結(jié)果 而后者允許外部代理修改 系統(tǒng)作業(yè)調(diào)度策略 從系統(tǒng)狀態(tài)估計的支持上 可將網(wǎng)格作業(yè)調(diào)度分成有狀態(tài)預(yù)測和無狀態(tài)預(yù)測 兩類 預(yù)測方法包括啟發(fā)式方法 基于經(jīng)濟(jì)模型的方法和機(jī)器學(xué)習(xí)方法 無預(yù)測 的方法包括啟發(fā)式方法和概率分布方法 為了提高資源利用率 作業(yè)吞吐量 進(jìn)行負(fù)載平衡 有些調(diào)度器支持作業(yè)的 重新調(diào)度 重新調(diào)度策略分為批處理式和在線式 批處理重調(diào)度資源利用率高 在