基于负载均衡的网格作流调度算法的研究.doc

硕 士 学 位 论 文 基于负载均衡的网格工作流调度算法的研究 The Research of Grid Workflow Task Scheduling Based on Load Balance 摘 要 网格(Grid)计算是近年来逐渐兴起的一个研究领域，Internet技术实现了硬件的连通，Web技术实现了网页的互连，而网格技术将实现的是Internet上所有资源的全面共享。在网格技术发展的同时，网格工作流技术也随之兴起，网格工作流是建立在网格系统基础之上的。网格系统中节点负载不均衡将导致网格工作流低效执行。因此，如何设计一种负载均衡机制，用来指导工作流任务调度算法以提高其调度效率和网格系统性能，是很迫切的问题。 本文首先介绍了网格、网格工作流及负载均衡的概念、研究现状和前景，阐述了网格工作流负载均衡的重要性。在此基础上，提出了网格工作流的负载均衡机制，包括基于负载均衡的网格工作流模型和负载均衡机制的核心——节点负载权值预测算法。接着根据所提出的模型，研究网格工作流业务流程，分析如何使用DAG(有向无环图)进行建模，并对建模后生成的子任务的逻辑关系进行说明；综合比较各类任务调度算法后，将负载均衡机制与遗传算法思想相结合，设计出基于负载均衡的网格工作流任务调度算法。最后，采用GridSim工具包对基于负载均衡的网格工作流调度算法进行了仿真，验证了算法的合理性和高效性。 关键字：网格工作流；负载均衡；预测算法；任务调度 Abstract Grid technology is a hot technique developed in recent years. Before technology of Internet carry out the contact among hardware; technology of Web carry out the contact between web pages; in future, technology of grid will help the share of all grid resources in Internal to come true. As the development of Grid technology, Grid Workflow technology which depends on Grid System has become more and more useful. While Grid system running for a long time, the loads of nodes may be more obvious imbalances. Result in Grid Workflow system is inefficient. Therefore, how to design mechanism for load balance, so as to use it to guide the Workflow task scheduling algorithm and improve effectiveness and performance of system, is a very pressing issue. This paper firstly introduces the conception and status quo and the development of grid computing and workflow in recent years, summarizing the current situation and importance of load balance. Then load balance mechanism for a Grid Workflow is proposed, including Grid Workflow model based on load balance and nodes load forecasting algorithm of the load balance mechanism. In addition, we thoroughly analyze the Business Process of Grid Workflow and how to use the DAG model to generate sub-tasks; and explain the logic of the relationship between the sub-tasks. Then, a number of task scheduling algorithms