一種考慮網格任務重要性和時間緊迫性的網格任務調度方法
2023-09-22 17:35:55 1
專利名稱：一種考慮網格任務重要性和時間緊迫性的網格任務調度方法
技術領域：
本發明屬於計算機網格任務調度方法，特別是一種考慮網格任務重要 性和時間緊迫性的網^"任務調度方法。
背景技術：
網格計算是繼Internet、 Web技術之後的第三次的技術革命，也是伴 隨著Internet技術一起發展起來的。隨著科技的發展，科學、工程和商業 領域中大規模性的計算問題的出現，使得單一的環境(P2P)，單一的技術(集 群計算)無能為力，它必須尋求一種價格低廉，處理能力超強的高性能計算 環境，網格就是這樣應運而生。網格計算的核心思想是尋求一種超級計算 能力的虛擬計算機，它利用目前十分流行的Internet技術將地理位置上的 分布式的異構資源，如伺服器，工作站，區域網，集群，文件系統，處理器，存 儲器等等全面共享，這種共享不是如今的Internet只是實現信息的上載與 下載，它利用各種代理，實現資源透明的訪問，使得Internet構成一臺超級 的，高性能計算能力的虛擬處理機。在結構上，網格計算實際上是利用網際網路將分散在不同地域上的計算 資源組織起來，形成一個虛擬的"超級計算機"，每個參與的計算機就是一 個"節點"，成千上萬的節點組合起來，成為一個網格。網格計算有兩個優 勢 一是超強的計算能力；另一個是能充分利用網絡中的閒置的計算能力。 從而使得Internet上的計算資源，存儲資源，數據資源、信息資源、知識 資源、專家資源等全面共享並得到充分的利用。網格中資源是異構的，主要表現在資源的結構、配置和容量上的不同， 它包括共享時間的處理器資源和共享空間的存儲器資源以及其他形勢的各種資源；網格中資源是屬於多管理領域的，並且每個領域都有自己的管理 策略，這就使得網格中的資源不可能像集群(Cluster)中資源一樣實行集中 管理，而必須實行分布式管理策略；網格的資源是動態變化的，因為在這 樣一個大規^莫環境中，隨時有資源加入其中，也隨時有資源退出其中，也 有資源可用數量減少等等動態變化的因素，所以網格必須有能夠實時監控 網格中資源變化的能力。像這樣一個規模遍及全球、資源異構並且動態變 化的網格結構，對資源的管理和調度勢必異常複雜。由上可見， 一方面由於網格環境價格低廉、計算能力超強，使得網格 成為解決科學、工程和商業領域中大規模性問題的最佳環境；另一方面由 於網格環境中的資源地理位置上的分布性、管理策略的多樣性、資源配置 的異構性和動態性等特點使得網格計算十分具有挑戰性。平衡這兩種矛盾 的最好辦法只能取長補短，克服缺點。因此，網格中的資源管理和調度成 為網格計算的核心問題。發明內容本發明的目的是提供一種合理調度網格資源，優化網格任務處理的考 慮網格任務重要性和時間緊迫性的網格任務調度方法。 為了實現上述目的，本發明所釆用的方法是 建立一種基於代理的網格資源管理模型，其模型中包括 網格用戶網格環境下，提交網格任務到網格環境中執行的人； 網格請求Agent:每個網格用戶對應一個網格請求Agent,其職責如下① 接收網格用戶的資源請求；② 根據資源請求尋找符合要求的資源；③ 將用戶的請求分解為多個子任務，每個子任務與一個網格任務 Agent相對應；④根據網格請求Agent的資源請求所映射的各個子任務的特性及資源 市場的價格，制訂出各個任務的費用預算及任務完成時限； 按照任務之間的依賴關係和時間順序，由每個任務對應的網格任務 Agent進行投標獲取資源；⑥將各個網才各任務Agent的計算結果匯總，最後將結果返回網格用戶。網格任務Agent:每個任務在計算網格中都有網格任務Agent與之對 應，網格任務Agent通過竟標向一個或多個網格資源Agent購買資源，完 成計算任務，其功能包括① 根據任務的特性及任務的預算情況，參與某資源的投標並獲得一定 比例資源的使用權；② 網格任務Agent的竟標策略明確地定義了它如何竟標以優化其效 用函數；③ 網格任務Agent的主要目標是在一定資金預算限制下儘可能快地 完成任務。網格資源Agent:網才各資源Agent的主要任務是① 申請將資源描述發布到網格資源路由器；② 以一定的價格向網格請求代理出售資源，其中每個網格任務Agent 都將獲得一定時間段的一定份額的資源，資源的價格由拍賣與竟標決定；③ 向網格請求Agent提供使用該資源的調用接口。 網格資源路由器網格資源路由器完成以下功能①資源註冊/註銷資源路由器是網格計算資源的接入設備，計算資 源在資源路由器上註冊之後，相當於在網格中分配了 一個唯一的身份標示> 可以被全網才各系統共享；② 資源路由信息收集/更新資源路由信息是有關資源所在位置的信 息，作為對資源請求進行路由和轉發的依據，由於資源的動態變化，資源 路由器之間，路由器和資源之間需要周期性地進行路由信息的更新；③ 資源請求的路由/轉發當資源路由器收到一個資源請求後，它需 要根據資源路由信息為該請求選擇一條路經並將其轉發給相應的資源路由 器。本發明充分考慮到網格資源的距離，及網格任務調度過程中充分考慮 網格任務的傳輸時間和傳輸費用。並且根據子任務的重要性和時間緊迫性特點，提出一種資源調度模型這種模型模擬市場經濟下的商品的價值規 律，網格任務Agent根據子任務的重要性因子和時間緊迫性因子有針對性 的投標網格資源，使得得到的資源的處理費用和執行速度處在任務的平均 費用和速度預算上下浮動，從而既能兼顧子任務的特性(重要性和時間緊 迫性)，又能大致保證最終的總的費用和時間仍然在預期的費用和時間之 內。本發明與傳統網格資源調度相比，其優點表現如下1、本發明提出了 一種基於代理的網格資源管理模型(AGRM),並且筒要的介紹了每個模塊的 功能；2、充分考慮了網格體系中資源的距離，及考慮了網格任務分派中的 傳輸時間和傳輸費用，對於實際的基於市場經濟模型的網格系統，這是很 合理也是很有必要的，而在目前網格資源管理中很少考慮的；3、任務調度 過程中考慮了每個子任務的重要性和時間緊迫性，並且作了定量定義，這 是目前網格任務調度很少考慮的；而這種考慮很有現實意義，因為每個子 任務之間不是等同的，而是有時間緊迫性和重要性區別的；4、提出了一種 模擬市場經濟下的價值規律的模型，這種模型能夠指導網格任務投標選擇 資源，並最終能大致保證任務在預期內完成。
圖1為本發明基於代理的網格資源管理模型圖。圖2為本發明費用和時間曲線。 圖3為本發明投標方法流程圖。
具體實施方式
下面結合附圖對本發明作進一步的詳細描述。本發明提出的的調度方法是建立在市場經濟模型下，首先描述網格環 境中的任務、資源的屬性，充分考慮任務的重要性和時間緊迫性以及的資 源與任務之間的距離等因素；然後模擬市場經濟下商品的價值規律，提出 一種任務Agent投標選擇網格資源的模型，這種模型能夠保證選擇的網格 資源價格和速度浮動於任務的平均費用和速度上下，從而保證任務能夠在 預期內完成。其具體方法是1、網格用戶提交給任務代理的一組任務T = 0\ T2,……，TJ，每個 子任務都有一定的長度ML (i =1， 2…m)，整個任務有預算(Budget)和截止 期限(DeadLine)兩個QoS約束(B, D)，也就是說該組子任務必須在費用B內， D時間之內完成，否則無效。其中，任務的長度用MI (Million Instruct, 百萬指令)表示，預算B用CU(Cost Unit,費用單位)表示；截止期限D用 S (Second,秒)表示。並且由於每個子任務的重要性和時間緊迫性不一樣， 子任務定義如下子任務Ti (MIi，Qi*B, Zi*D) 其中MIi是子任務的長度，Qi表示子任務重要性因子，Zi是任務時間緊 迫性因子，滿足下面要求t@ = i,o<g/<i , tz/ = i,o<zz<i對子任務重要性定義如下QiB / ML 〉 B / M...................................................(1)及子任務的單位指令的費用比總任務的平均費用越高，表明子任務越重要，否則越不重要；對子任務的時間緊迫性定義如下Mli/ZiD〉MI/D............................................................(2)及子任務期望完成速度比總任務的平均速度越快，表明子任務越緊迫， 否則越不緊迫；並且一般認為，對於重要的性比較高的子任務，應當儘量讓其執行完； 對於時間比較緊迫的任務可以選擇資源費用比較高，同時速度比較快的資 源執行。2、 網格中的一組資源集(RLR2,…,IU,每個資源都有(距離，處理速度, 使用價格)(Di，MIPSi,CUPMIi)屬性，分別表示從網格任務代理到網格資源之 間距離，資源的執行速度和執行費用，其單位分別用距離單位 DU,MI/S,CU/MI表示。並且假設網格中單位距離上的平均資源路由器個數 為m (個/DU)，每個路由器的單位(百萬)指令的轉發時間為n (S)，單位(百萬) 指令的轉發費用為k(CU)。3、 網格任務調度方法網格任務Agent衝殳標選擇資源方法網格任務Agent根據自己分配的子任務特點(重要性，時間緊迫性)進 行投標選擇網格資源，並與其討價還價。假設i任務Agent對應的任務 Ti (MIi， QiB， ZiD)選擇j資源Rj (Di, MIPSi.C醒Ii)那麼，執行費用MIi * D產k / m + MIi * CUPMIj執行時間formula see original document page 10 如果子任務時間緊迫度高(Z, D / MIi很小的)，那麼允許該任務Agent 投標那些執行速度快的資源，即使其執行費用很高，及本任務超出了其費 用預算；否則就投標那些執行速度低的資源，平衡整體任務的時間預算； 如果子任務重要性高他* B / MI很大的)，那麼允許該任務Agent投標那 些執行費用高的(一般認為，執行費用高的資源可能更穩定，質量更好)， 即使執行速度慢些，及本任務超出了其時間預算；否則就投標執行費用低些 的資源，平衡整體任務的費用預算。不管上述那種情況，整個任務的費用 曲線和時間曲線應該滿足圖2所示曲線也就是說所有的任務Agent的資 源費用和資源速度應該在平均費用和速度預算上下波動，從而保證最後整 體費用和時間在預期之內，及對於時間緊迫性高的任務，其執行費用可以 高出自己的費用預算，否則應該低於自己的預算；對於重要性高的任務， 其執行時間可以長於自己的時間預算，否則應該短於自己的時間預算，整 體任務應當滿足formula see original document page 10任務Agent投標選擇網格資源方法① 對每個子任務Agent,根據自己分派的任務分析其重要性和時間緊 迫性特點，具體參照式1和式2;② 任務Agent投標選擇網格資源，對於重要性高的任務，可以投標選 擇執行費用高的資源，即使其執行速度慢，讓其費用和時間在平均速度/ 費用預算線之上，反之，在平均速度/費用預算線之下。對於時間緊迫性高 的任務，可以投標選擇執行速度快的資源，即使其執行費用高出自己的費 用預算，反之，投標那些執行速度低的、費用也低的資源；③重複①②直至所有的任務Agent投標選擇完成。 任務Agent投標結果評判上述所有任務Agent投標選擇的資源是否合理，就是看所有的資源費 用和速度分布情況越是分布在平均速度/費用預算兩邊，曲線越是對稱對 稱就越好，表明本次投標選擇的資源既能滿足任務本身的特徵(時間緊迫性 和重要性)要求，又能使整體任務能在預期的約束內完成；反之，就越不合理。本說明書中未作詳細描述的內容屬於本領域專業技術人員公知的現有 技術。
權利要求
1、一種考慮網格任務重要性和時間緊迫性的網格任務調度方法，所採用的方法是建立一種基於代理的網格資源管理模型，其模型中包括網格用戶網格環境下，提交網格任務到網格環境中執行的人；網格請求Agent每個網格用戶對應一個網格請求Agent；網格任務Agent每個任務在計算網格中都有網格任務Agent與之對應，網格任務Agent通過競標向一個或多個網格資源Agent購買資源，完成計算任務；網格資源Agent；網格資源路由器。
2、 如權利要求1所述的考慮網格任務重要性和時間緊迫性的網格任務 調度方法，其特徵在於網格請求Agent的具體方法是① 接收網格用戶的資源請求；② 根據資源請求尋找符合要求的資源；③ 將用戶的請求分解為多個子任務，每個子任務與一個網格任務 Agent相對應；④根據網才各請求Agent的資源請求所映射的各個子任務的特性及資源 市場的價格，制訂出各個任務的費用預算及任務完成時限； 按照任務之間的依賴關係和時間順序，由每個任務對應的網格任務 Agent進行投標獲取資源； 將各個網格任務Agent的計算結果匯總，最後將結果返回網格用戶。
3、如權利要求1所述的考慮網格任務重要性和時間緊迫性的網格任 務調度方法，其特徵在於網格任務Agent的具體方法是① 根據任務的特性及任務的預算情況，參與某資源的投標並獲得一定比例資源的使用權；② 網格任務Agent的竟標策略明確地定義了它如何竟標以優化其效 用函數；③ 網格任務Agent的主要目標是在一定資金預算限制下儘可能快地 完成任務。
4、如權利要求1或3所述的考慮網格任務重要性和時間緊迫性的網格 任務調度方法，其特徵在於網格任務Agent竟標的具體步驟是第一步驟每個任務Agent依據下述公式分析自己的分配的任務，確定任務的時間緊迫性和重要性特點，QiB / ML > B / M......................................................(1)MI,./ZiD〉MI/D............................................................(2)其中ML是子任務的長度，Qi表示子任務重要性因子，Zi是任務時間緊迫性因子，B是預算，D是時間；第二步驟任務Agent投標選擇網格資源，對於重要性高的任務，投 標選擇執行費用高的資源，即使其執行速度慢，讓其費用和時間在平均速 度/費用預算線之上，反之，在平均速度/費用預算線之下；對於時間緊迫 性高的任務，投標選擇執行速度快的資源，即使其執行費用高出自己的費 用預算，反之，投標那些執行速度低的、費用也低的資源；第三步驟重複上述過程直至所有的任務Agent投標選擇資源完成。
全文摘要
本發明涉及一種考慮網格任務重要性和時間緊迫性的網格任務調度方法，所採用的方法是建立一種基於代理的網格資源管理模型，其模型中包括網格用戶；網格請求；網格任務；網格資源和網格資源路由器，其網格任務Agent的具體方法是1.根據任務的特性及任務的預算情況，參與某資源的投標並獲得一定比例資源的使用權；2.網格任務的競標策略明確地定義了它如何競標以優化其效用函數；3.網格任務的主要目標是在一定資金預算限制下儘可能快地完成任務。本發明考慮了任務調度過程中每個子任務的重要性和時間緊迫性，並且作了定量定義，提出了一種模擬市場經濟下的價值規律的模型，這種模型能夠指導網格任務投標選擇資源，並最終能大致保證任務在預期內完成。
文檔編號H04L29/08GK101222522SQ20081004670
公開日2008年7月16日 申請日期2008年1月17日 優先權日2008年1月17日
發明者帆 吳, 李春林, 鄭四海, 林 郭, 高慶鋒 申請人:武漢理工大學