APP下载

基于QoS约束的网格任务调度算法

2013-11-04王浩,李飞

关键词:定义资源

王 浩,李 飞

(成都信息工程学院网络工程学院,成都 610225)

引言

网格[1]环境下的任务调度问题是网格技术中的一个基本问题。由于网格环境中的资源所具有的异构性、动态性和分布性等特点,使得如何对任务进行调度以期满足各方面(系统用户、资源提供者、系统管理者等)的需求成为一个极具挑战性的问题。网格任务调度[2]的实质是将其环境中的m个需要调度的任务合理的分配到n个系统可用资源主机上去执行。由于现实环境中的网格系统规模一般都比较大,这样就决定了m和n都比较大,因此问题则转变成为一个NP难问题,即需要在有限时间内,在2n个资源集合中寻找出最优任务-资源匹配方案,然而这又是不可能实现的,因此,一般都采用启发式任务调度算法获取近似最优配对。

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

1 相关工作

本文主要研究的是批处理模式下的启发式任务调度算法,并且已假定各任务之间相互独立,各任务在不同的资源上运行的预测执行时间可知。目前,经典的批处理模式下的调度算法有:Max-min[3]算法、Minmin[3-6]算 法、GA[7-8]算 法、Sufferage[9-10]算 法 和SA[11](Simulated Annealing)等。Max-min算法是基于MCT(Minimum Completion Time,最小完成时间)的改进算法,算法选取最早完成时间最大的任务进行优先调度。GA算法与SA算法,其复杂度一般认为都比较高。……

登录APP查看全文

猜你喜欢

定义资源
让有限的“资源”更有效
基础教育资源展示
永远不要用“起点”定义自己
定义“风格”
资源回收
资源再生 欢迎订阅
成功的定义
修辞学的重大定义
山的定义
对你有用的“钱”在资源