成本時間限制下的網(wǎng)格分類調(diào)度算法研究

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

關(guān)鍵詞：網(wǎng)格經(jīng)濟模型；調(diào)度；優(yōu)化；Makespan

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

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

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

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

1相關(guān)工作

1．1基于經(jīng)濟的網(wǎng)格體系結(jié)構(gòu)

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

網(wǎng)格消費者提出應(yīng)用請求，描述其服務(wù)要求，如服務(wù)最低完成時間和預(yù)算。

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

網(wǎng)格中間件提供匹配用戶請求和資源供給的服務(wù)，如遠程處理、資源協(xié)同分配、存儲控制、信息目錄、安全、授權(quán)、服務(wù)質(zhì)量控制等。

網(wǎng)格服務(wù)提供者提供本域內(nèi)資源管理和交易服務(wù)，資源管理動態(tài)監(jiān)測資源，并向網(wǎng)格信息服務(wù)器和網(wǎng)格市場目錄服務(wù)器發(fā)布資源信息；交易服務(wù)負責與資源用戶進行協(xié)商，定義價格模型，管理記賬系統(tǒng)，記錄資源使用情況，并向用戶收費。

1．2基于經(jīng)濟學理論的網(wǎng)格資源交易模式

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

1．3經(jīng)濟網(wǎng)格資源調(diào)度算法

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

2分類優(yōu)化調(diào)度算法基本思想

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

3實驗結(jié)果

下面的實驗?zāi)M了980臺計算主機，具有不同的計算能力，且各個計算資源的成本不同；實驗還模擬了3 000個任務(wù)，各個任務(wù)的預(yù)算成本、時間限制和規(guī)模均不同。表1、表2分別為部分任務(wù)的QoS需求和部分資源的性能。實驗中給定相同的計算資源和任務(wù)分別模擬了基于成本和時間限制的分類優(yōu)化調(diào)度算

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

表1任務(wù)QoS要求

表2主機性能

表3三種算法執(zhí)行700個高預(yù)算任務(wù)情況

4結(jié)論與展望

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

參考文獻：

［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］劉麗，楊揚，郭文彩，等.基于納什均衡理論的網(wǎng)格資源調(diào)度機制[J].計算機工程與應(yīng)用， 20-04，40（29）:106107.

［16］徐志偉，等.網(wǎng)格計算技術(shù)[M].北京：電子工業(yè)出版社，20-04.

作者簡介：

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

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