收 稿日期 : 2006-10-11; 修 回日期 : 2006-12-26 基 金项 目: 国 家自 然科学 基金 资助项 目( 60173026)
作 者简介 : 姜 黎立 ( 1982-) , 男, 硕士 , 主 要研究 方向 为网格 计算 ( janglily210@ gmail. com) ; 蒋昌 俊( 1962- ) , 男 , 教 授, 博导, 博 士, 主要研 究方 向
为 Petri 网 理论 及应用 、并 发理 论与并 行处 理、网格技 术; 袁禄 来( 1981- ) , 男 , 博 士研究 生, 主要 研究方 向为 网格计 算、Web 服务 、可信计 算.
网 格 环 境 下 基 于 QoS 需 求 的 关 联 任 务 调 度 算 法
*
姜黎立, 蒋昌俊, 袁禄来
( 同济 大学 计 算机 科学 与工程 系, 上海 201804)
摘 要: 首 先描 述 QoS调 度问 题, 建立 QoS需求 模型 ; 然后 通过 分 析 任务 的 依 赖性 , 提 出时 间 花 费、资 源 价 格 和
可靠 性三 种 QoS 参 数的 映射机 制; 最 后针 对网格 环境 的新 特征 , 提 出一 种以 优化 用户 效用 为目 标, 基于 QoS的关
联任 务调 度 算法 ( QBDTS_UO) 。仿 真 实验 结 果 表明 , 该算法 能 以 较小 的 时 间花 费 为 代价 , 有效满 足 用 户 的 QoS
需求 , 并 能大 大提 高网 格资 源的 使用率 。
关键 词: 网 格计 算; 任务 调度 ; 服务 质量 ; 关 联任 务
中图 分类 号: TP338; TP301.6 文献 标志 码: A 文章 编号 : 1001-3695( 2008) 02-0350-05
QoS-based scheduling heuristics for dependent tasks in grid computing
JIANG Li-li, JIANG Chang-jun, YUAN Lu-lai
( Dept. of Computer Science & Technology, Tongji University, Shanghai 201804, China)
Abstract: This paper firstly described QoS scheduling problem and established a QoS demand model. Then proposed a QoS
mapping mechanismfor three QoSparameters which included completion time, execution cost and reliability in basis of analy-
zing the relationship among tasks. Finally, proposed a computationally efficient static scheduling heuristics which was called
QoS-based dependant task scheduling for utility optimization( QBDTS_UO) . Simulation results show that QBDTS_UO is capa-
ble of meeting diverse QoSrequirements for users, while can greatly increase the usage of grid resources.
Key words: grid computing; task scheduling; quality of service( QoS) ; dependent task
网格计算是一种专门针对复杂科学计算的新型计算模式。
该计算模式是利用互联网将分 散在不 同地理 位置的 各种计 算
机和设备组成一个具有超级计算能力的虚拟计算机系统, 从而
实现对计算资源、存储资源、数据资源、信息资源、知识资源、专
家资源的全面共享
[ 1, 2]
。然而, 网 格资源 的动态 性、异 构性、地
理分布 性、开放 性、可 扩展性、不确定性, 以及网 格资源在不 同
所有者之间形成的利益分配等问题, 使得设计一种高效经济的
资源管理和任务调度模型面临挑战。
在传统的分布式和集群计算环境下, 许多有关静态、动态、
静态与动态相结 合的 调度 算 法已 经被 研 究
[ 3,4]
。同 时也 正 在
探索一些有关分布调度、中 心调度、自主调度、智能 调度、agent
协商调度等算法
[ 5]
。静态调度 算法研 究的核 心内容 是通过 减
少分布处理器节点间的通信开销、提高任务并行执行程度等手
段来缩短调度时间; 动态 调度算 法在静 态调度 算法的 基础上,
更强调任务分配时的负载平衡和负载共享, 以提高整个系统的
吞吐率和使用率。但所有这些 算法都 未考虑 用户对 任务提 出
的 QoS需求。
在网 格计 算环 境下, 由 于资 源的 内在 特性 使得 QoS 成 为
任务调度需要考虑的新因素。这样, 调度算法研究的目标将与
用户的 QoS需求紧 密结 合 起来。 目前, 对 任务 调 度 QoS 参 数
的定义和基于 QoS的独立任务 调度算 法的设 计是两 个重要 的
研究课题。文献[ 6] 对任务调度的 QoS参数进行 了分类研究;
文献[ 7 ~10] 分别介绍 了五 个基 于 QoS 需求 的独 立任 务调 度
算法, 分 别为 min-min
[ 7]
、sufferage
[ 8]
、least slack first
[ 9]
、genetic
algorithm
[ 7]
和 QSMTS-IP
[ 10]
。无论在传统分布式环境还是网格
计算环境下, 上述 算法 已 经能 够较 好 地解 决基 于 QoS 的独 立
任务调度问题, 并在一些任务依赖较 弱的科 学计算 ( 如大规 模
矩阵计算、蒙特卡罗模拟、生物上 的 DNA 测 序) 中得 到了很 好
的应用。对于更多复杂的应用, 任务间的依赖将是一个不可忽
略的因 素。 对 于 这 类 应 用, 传 统 算 法 只 能 将 其 视 为 元 任 务
( meta-task) 来考虑, 限制 了对任 务粒度 的进一 步划 分, 从而 大
大降低了任 务调 度的 性 能。因此, 如 何 设计 一种 高 效的 基 于
QoS需求的关联任务调度算法, 对提高任务执行 效率和资源 的
利用率具有重要意义。
本文 在 对 复 杂 任 务 进 行 任 务 划 分, 并 用 有 向 无 环 图
( DAG) 描述任务间 关联 的基础 上, 定义 了用 户 最关 心的 三 种
QoS参数和相关 QoS的效用函 数, 建立了 QoS需求 模型; 然 后
通过关联任务的 QoS 参数 分 配方 法 ( QoS 映 射机 制 ) , 将 用 户
对网格应用程序提 出的 QoS 需求 分 配给 它的 子 任务, 建立 了
对各个子任务调度的目标函数; 最后给出了基于服务质量的关
联任务调度算法( QBDTS_UO) 。
1 QoS 模型的建立
1. 1 基于 QoS 调度的问题描述
在当前网格计算平台下, 有 m个计算资源( 处理器设备 ) ,
记做 P = { p
1
, p
2
, …, p
m
} 。这 些 计 算资 源 可 以来 自 超 级 计 算
机、计算机集群或个人 PC, 它们有 着不同 的运 算速 度、出现 故
障频率和使用费用。本 文用 λ= { λ
1
, λ
2
, …, λ
m
} 表 示处 理 器
资源的故障率参数。现有用户 向当前 计算平 台提交 了一组 带
第 25 卷第 2 期
2008 年 2 月
计 算 机 应 用 研 究
Application Research of Computers
Vol. 25 No. 2
Feb. 2008