基于多QoS约束的数据网格任务调度算法研究

李 飞，王 浩，张 琨，牛京武

（成都信息工程学院 网络工程学院，四川 成都610225）

0 引 言

网格［1］环境下的任务调度问题是网格技术中的基础性问题。由于网格环境中的资源所特有的分布性、异构性和动态性等特点，使得对任务如何进行调度安排并以期满足各方面 （资源提供者、系统用户、系统管理者等等）的需求成为一个极具挑战性的问题。

网格任务调度［2－3］的目的是在网格异构环境中，将m个待调度的任务分配到n个可用资源上去，并且使得任务完成总时间 （makespan）尽可能的小。对于实际的网格环境，其m和n一般都不会太小，因此，网格任务调度实际就是一个NP问题。对任务集合实现最优调度，成为网格任务调度的首要目标。具体的目标包括负载均衡、时间跨度、安全度、费用、稳定性、成功率等。负载均衡是影响网格中各节点之间进行协同工作最为重要的因素之一。时间跨度是指从任务等待调度开始到所有任务运行完毕所经历的时间，其值越小，该调度策略越好。当用户向网格系统提交自己的任务时，最大的愿望是：系统在满足自己任务的多QoS约束条件下，尽可能快的完成自己的任务，并且相关费用越低越好。如何提高网格系统的性能，并保证用户任务在调度过程中的服务质量，正是网格调度算法所要解决的问题。

目前国内外所研究的任务调度算法一般分为在线模式（on－line mode）和批处理 （batch mode）模式两类。在线模式在任务到达的第一时间开始执行映射。批处理模式则需要将任务收集到一定数量 （系统设定的一个参数数值），等待映射事件触发以后才开始映射所收集的任务。……