一个市场驱动的QOS网格工作流任务调度算法.pdfVIP

第25卷第4期 计算机应用与软件 Vo1．25 No．4 2008年4月 Computer Applications and Software Apr．2008 一 个市场驱动的QoS网格工作流任务调度算法 张 艳 李 楠 (上海交通大学软件学院 上海200030) 摘 要 网格调度关系到整个网格任务运行的效率，因此在网格的研究过程中，已经提出了很多调度算法。但这些算法大部分是 对元任务(Meta．task)进行调度，很少是针对关联任务的。在考虑用户QoS(Quality of Service)需求的情况下，提出了一个市场驱动的 QoS网格工作流任务调度算法。仿真实验结果表明了该算法的合理性和有效性。 关键词 市场驱动 QoS 任务调度算法 网格工作流 A MARKET．DRIVEN QoS TASK SCHEDULING ALGORITHM FOR GRID WORKFLOW Zhang Yan Li Nan (School 0，Software，Shanghai Jiaotong University，Shanghai 200030，China) Abstract Grid scheduling has an effect on the efficiency on grid task execution，SO in the research on grid，many scheduling algorithms have been proposed．But these algorithms mainly focus on Meta—task scheduling，seldom on associated task scheduling．Considering the users’ QoS requirements，a market．driven QoS task scheduling algorithm for grid workflow is proposed．The experimental results show that the algo- Keywords Market—driven QoS Task scheduling algorithm Grid workflow 0 引 言 在网格环境中调度工作流应用是一个NP完全问题，目前 已经提出了许多启发式的调度算法对其进行调度。这些算法所 采用的调度策略可分为三类：性能驱动、市场驱动和信任驱动。 性能驱动策略的目标是调度系统有效的分配工作流任务到合适 图1 工作流 QoS的分类 的网格资源，使完成整个应用所花费的时间最少。目前，大多数 个时间期限内能够用最低的成本来完成某个应用。所以，我们 网格工作流调度系统都采用这种策略(如GRADS，Prodan)。市 提出的任务调度算法的目标就是在满足用户的时间需求的情况 场驱动策略则是在满足用户QoS需求的情况下，使完成整个应 下，使完成应用所花费的成本最低。 用所花费的成本最低。也有一些网格系统采用这个策略(如 Nimrod—G)…。而信任驱动的策略才提出不久，应用较少。 2 工作流任务调度算法 本文旨在讨论一个市场驱动的网格工作流任务调度算法， 即要在用户指定的时间约束范围内，使完成整个工作量所花费 为了实现上述目标，可以采用分治法来解决任务调度，实现 的成本最低。 的步骤分为三步： (1)资源发现和需求识别 对工作流图中的每个任 1 问题描述 务，使用网格信息服务分别识别所有可用的资源，列出可用资源