成本時間限制下的網格分類調度算法研究

摘要：在網格環境中，由于資源廣域分布、異構、動態且有多個管理域，調度一組具有多QoS需求如成本、時間的獨立任務是一個非常重要的問題。針對網格任務的成本和執行時間要求，提出了一種基于網格經濟模型，根據實際執行成本和預算成本進行分類的網格分類優化調度算法。模擬實際網格任務調度實驗表明，該算法能很好地滿足網格環境中不同用戶的需求。

關鍵詞：網格經濟模型；調度；優化；Makespan

中圖法分類號：TP301．6文獻標識碼：A

文章編號：1001－3695(2007)01－0031－03

網格計算是近年來得到快速發展的廣域網絡計算技術，它所要解決的問題是在動態多制度的虛擬組織之間協調資源共享與操作，這里的共享是指直接訪問計算機、軟件、數據和其他資源，而不單指文件交換。確切地說網格是一種環境，在這種環境中，各種計算資源（如超級計算機、機群系統、低端的個人計算機和工作站等）、顯示設備、存儲系統、數據庫、特殊的科學儀器（如無線望遠鏡）和計算核心程序等被邏輯地連接在一起，作為單一的整體資源提供給用戶。

由于在網格環境下，資源廣域分布、異構、動態且有多個管理域，這些資源為不同的組織擁有，各組織對資源的管理機制、策略、費用和目標都不盡相同，全局資源管理和調度富有挑戰性。傳統調度只考慮系統性能，而忽視了用戶的服務質量要求，如文獻[2～6]介紹的OLB，UDA，Fast Greedy，MinMin，MaxMin，Sufferage，GSA，Tabu，A*等，追求最小Makespan是這些算法的主要目標。文獻[3，7～9]介紹了一些優秀的基于QoS 要求的獨立任務調度算法，如某些任務的文件傳輸時間要求、安全性要求等，但這些資源管理和調度算法均不能很好地滿足實際網格環境。市場機制非常適合解決網格資源管理和調度問題，市場機制通過價格浮動反映資源供需狀況的動態變化，通過供需均衡實現資源優化，這種動態協調的資源管理機制適合網格資源的特性。為此，本文在Buyya博士提出的網格經濟資源管理模型的基礎上，提出了一種基于市場機制的成本和時間限制下的網格分類優化調度算法。

1相關工作

1．1基于經濟的網格體系結構

網格環境中，可以將資源提供者視為生產者，將應用請求者（資源用戶）視為消費者，兩者構成經濟網格模型的兩個重要因素。計算經濟模型將經濟的概念引入網格資源管理中，它應用了市場經濟中的供求原則來對資源的所有者和使用者進行調節，以保證雙方均獲取最大利益，其體系結構[9～11]如圖1所示。其關鍵的部件有網格用戶和應用、網格開發環境、用戶級中間件和工具(GRBs)、核心級中間件、網格服務提供者(GSPs)。

網格消費者提出應用請求，描述其服務要求，如服務最低完成時間和預算。

網格資源代理(GRBs)用網格中間件服務連接用戶和網格資源，負責資源發現、資源選擇和調度。它包括作業控制代理(JCA)、任務調度、網格信息瀏覽、交易管理和分配代理五大模塊。作業控制代理接收用戶的任務和要求，提交給調度模塊；網格瀏覽器通過網格市場目錄服務器和網格信息服務器查詢資源提供者的信息；交易管理模塊提供各種經濟模型和交互協議來進行資源交易；調度模塊根據資源信息及用戶要求分派最優資源給任務；任務分配代理模塊將任務調度到選定資源上運行，并隨時將任務狀態或結果返回給任務控制代理。

網格中間件提供匹配用戶請求和資源供給的服務，如遠程處理、資源協同分配、存儲控制、信息目錄、安全、授權、服務質量控制等。

網格服務提供者提供本域內資源管理和交易服務，資源管理動態監測資源，并向網格信息服務器和網格市場目錄服務器發布資源信息；交易服務負責與資源用戶進行協商，定義價格模型，管理記賬系統，記錄資源使用情況，并向用戶收費。

1．2基于經濟學理論的網格資源交易模式

經濟網格環境下，各個經濟個體有不同的目標、策略，存在多種交易模式，市場經濟驅動的資源管理與調度機制應該以實現各經濟個體利益最大化為目標來共享資源。基于經濟學理論管理分布資源有利于調節資源的供給和需求，以網格環境中所有經濟個體得到的社會總剩余最大化為目標來管理、配置和調度資源。從經濟學的觀點看，系統追求兩個基本目標：①系統要提供良好的機制鼓勵參加者共享資源；②系統資源的分配能夠實現經濟的計算。資源提供者和使用者可以使用各種經濟模型和交互協議來進行資源交易和服務存取，以達到上述目標。可以實現資源交易服務的經濟模型主要包括多商品（資源）市場模型，標記價格模型，議價模型，招標、合同網模型，拍賣模型，基于出價的按比例資源共享模型，社區/聯合/交換模型及壟斷/寡頭市場模型。無論使用何種模型，其資源管理系統需要提供機制來同時滿足資源提供者和資源使用者的目標，其實現的關鍵在于任務調度算法。

1．3經濟網格資源調度算法

文獻[9，10]在NimrodG 模型中提出基于時間和成本限制下的優化調度算法(DBC)，比較有效的算法有完成時間優先調度算法、成本優先調度算法、限定時間成本保守時間最優化算法等。以上三種算法從不同角度滿足了用戶要求，是基于應用級QoS的調度算法。完成時間優先調度算法在用戶定義的任務最低完成時間和成本的限制條件下，任務完成時間最短；成本優先調度算法在用戶定義的任務最低完成時間和成本的限制條件下，盡可能用最經濟的計算處理任務；限定時間成本保守時間最優化算法擴展了前兩種算法，在保證成本最小時兼顧任務完成時間最短。但在實際網格環境中，用戶的需求、應用是各種各樣的，需要綜合平衡時間和成本，滿足價優質優的服務原則和低成本應給劣質服務等實際市場規律。為此我們提出一種基于成本和時間限制的分類調度算法，較好地滿足了網格壞境中的復雜需求。

2分類優化調度算法基本思想

分類優化調度算法主要研究的是以計算為主且任務彼此獨立、無相互依賴關系，并且假定如主機計算速度快，則成本就高。可以簡單地描述為N個任務，M臺主機，對于每個Taski必須提交預算成本Costi和規模Sizei以及最后期限Deadlinei ，每臺主機Mj都有單位使用費率Mcostj單位/s和計算能力Performj。算法的主要思想是讓預算高出平均成本的任務優先運行，且以完成時間最優為主要目標，以實現價優質優的思想；另一類調度的主要目標則是以成本最優為主。因此，我們將任務分類，每類采取不同的調度策略，其核心是如何分類。文獻[2]描述了一種基于MinMin算法的分類思想，我們在借鑒此思想的基礎上提出以平均實際運行成本和預算成本為依據的分類方法，如果預算高于平均實際運行成本，則優先調度。這種分類原則是符合市場規律的，可以激勵用戶通過經濟手段來表達自己對服務質量（如優質快速完成任務）的需求，對于這一類優先調度的任務，以獲取時間最優為主要目的；對于另一類任務由于成本有限，則以優化成本為主要目的。分類優化調度算法中用到的相關定義如下：

3實驗結果

下面的實驗模擬了980臺計算主機，具有不同的計算能力，且各個計算資源的成本不同；實驗還模擬了3 000個任務，各個任務的預算成本、時間限制和規模均不同。表1、表2分別為部分任務的QoS需求和部分資源的性能。實驗中給定相同的計算資源和任務分別模擬了基于成本和時間限制的分類優化調度算

法、完成時間優先調度算法和成本優先調度算法。三種算法實驗結果的時間和成本對比如圖2所示。從圖2中可知，分類優化調度算法在總耗時間上優于成本優先調度算法，接近于完成時間優先調度算法，在成本上優于時間優化調度算法。另外我們還對700個預算較高任務的Makespan、總執行時間、總成本及其平均響應時間進行了比較，如表3所示。分類優化調度算法在Makespan和平均響應時間上明顯優于其他兩種算法，這是完全符合市場規律的，說明分類優化調度算法在實際網格環境中是有效的。

表1任務QoS要求

表2主機性能

表3三種算法執行700個高預算任務情況

4結論與展望

面對網格任務調度的新挑戰，在網格經濟體系基礎上，針對獨立任務給出了基于時間成本限制下分類優化調度算法，本算法可兼顧任務所耗時間、成本和用戶的QoS要求等各個因素。這種基于市場機制的任務調度算法符合實際的網格環境，可有效地實現網格資源的管理。如何進行有效的網格任務分類還有待下一步更深入的研究。

參考文獻：

［1］Foster I， Kesselman C. The Grid， Blueprint for a New Computing Infrastructure[M]. San Francisco： Morgan Kaufmann Publishers Inc.， 1998.279309.

［2］MinYou Wu， Wei Shu， Zhang H. Segmented MinMin：A Static Mapping Algorithm for Metatasks on Heterogeneous Computing Systems[C].Heterogeneous Computing Workshop，2000.

［3］Golconda K S， Ozguner F， Dogan A. A Comparison of Static QoSbased Scheduling Heuristics for a Metatask with Multiple QoS Dimensions in Heterogeneous Computing[C]. Proceedings of the 18th International Parallel and Distributed Processing Symposium，20-04.106.

［4］Shanshan Song， YuKwong Kwok， Kai Hwang.SecurityDriven Heuristics and a Fast Genetic Algorithm for Trusted Grid Job Scheduling[C]. Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium， 2005.

［5］Maheswaran M， Ali S， Siegel H J， et al. Dynamic Mapping of a Class of Independent Tasks onto Heterogeneous Computing Systems[C]. San Juan: Proc. of the 8th IEEE Heterogeneous Computing Workshop (HCW)，1999.3044.

［6］Henri Casanova， Arnaud Legrand， Dmitrii Zagorodnov，et al. Heuristics for Scheduling Parameter Sweep Applications in Grid Environments[C]. Cancun: Proc. of the 9th IEEE Heterogeneous Computing Workshop (HCW)， 2000.349363.

［7］He XS， Sun XH， von Laszewski G. QoS Guided MinMin Heuristic for Grid Task Scheduling[A]. The 1st International Workshop on Grid and Cooperative Computing (GCC)[J]. Journal of Computer Science and Technology，2003，18(4)：442451.

［8］Gan A，Ozguner F. Schdeuling Independent Tasks with QoS Requirements in Grid Computing with TimeVarying Resource Prices[C]. Grid ComputingGRID，2002.5869.

［9］Buyya R，Murshed M，Abramson D. A Deadline and Budget Constrained CostTime Optimization Algorithm for Scheduling Task Far￣ming Applications on Global Grids[C].Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications(PDPTA)，2002.

［10］Buyya R， Abramson D， Venugopal S.The Grid Economy[C].Proceedings of the IEEE， 2005.698714.

［11］Buyya R， Abramson D， Giddy J.High Nimrod/G： An Architecture for a Resource Management and Scheduling System in a Global Computational Grid[C]. Proceedings of the 4th International Conference/Exhibiti on High Performance Computing in the AsiaPacific Region，2000.283289.

［12］Foster I， Roy A，Sander V. A Quality of Service Architecture that Combines Resource Reservation and Application Adaptation[C]. Pittsburgh: Proc. of the 8th Int. Workshop on Quality of Service， 2000.181188.

［13］Braun T D， Siegel H J， Beck N， et al. A Taxonomy for Describing Matching and Scheduling Heuristics for Mixedmachine Heterogeneous Computing Systems[C]. West Lafayette:IEEE Workshop on Advances in Parallel and Distributed Systems， 1998.330335.

［14］O Ibarra， C Kim. Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors[J]. Journal of the ACM， 1977，77(2)：280289.

［15］劉麗，楊揚，郭文彩，等.基于納什均衡理論的網格資源調度機制[J].計算機工程與應用， 20-04，40（29）:106107.

［16］徐志偉，等.網格計算技術[M].北京：電子工業出版社，20-04.

作者簡介：

朱春玲(1971)，女，副教授，主要研究方向為網格調度算法；唐小勇(1973)，男，碩士研究生，主要研究方向為網格計算；李肯立(1971)，男，副教授，博士，主要研究方向為并行計算、網格計算。

注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文