网格计算中面向QoS的任务调度机制研究论文.doc

硕士学位论文硕士学位论文 网格计算中面向网格计算中面向 QoSQoS 的任务调度机制研究的任务调度机制研究 Research on QoS Guided Mechanism of Task Scheduling in Grid Computing 专 业 软件工程 作 者 导 师 胡志刚教授 中南大学软件学院 二 一三年三月 中图分类号 学校代码 10533 UDC 密级 公开 硕士学位论文硕士学位论文 网格计算中面向网格计算中面向 QoSQoS 的任务调度机制研究的任务调度机制研究 Research on QoS Guided Mechanism of Task Scheduling in Grid Computing 作者姓名 学科专业 软件工程 研究方向 学院 系 所 软件学院 指导教师 胡志刚 副指导教师 论文答辩日期 答辩委员会主席 中 南 大 学 小三号宋体 年 月 小三号宋体 I 原创性声明原创性声明 本人声明 所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果 尽我所知 除了论文中特别加以标注和致 谢的地方外 论文中不包含其他人已经发表或撰写过的研究成果 也不包含为获得中南大学或其他单位的学位或证书而使用过的材料 与我共同工作的同志对本研究所作的贡献均已在论文中作了明确的 说明 作者签名 日期 年 月 日 学位论文版权使用授权书学位论文版权使用授权书 本人了解中南大学有关保留 使用学位论文的规定 即 学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文 允许学位论文被查阅和借阅 学校可以公布学位论文的全部或部分 内容 可以采用复印 缩印或其它手段保存学位论文 同时授权中 国科学技术信息研究所将本学位论文收录到 中国学位论文全文数 据库 并通过网络向社会公众提供信息服务 作者签名 导师签名 日期 年 月 II 日 网格计算中面向网格计算中面向 QoSQoS 的任务调度机制研究的任务调度机制研究 摘要 论文介绍和总结了网格计算中的关键技术 资源分配和任务 调度以及网格 QoS 的国内外研究现状 指出了目前研究中存在的问 题和不足 并就这两方面的结合 即如何在资源分配和任务调度中 考虑 QoS 提出了自己的见解和看法 本研究提出了一种面向 QoS 的网格任务调度机制 用于在任务 调度过程中保障用户的 QoS 要求 具体研究内容包括 任务 资源 QoS 参数抽象 调度过程的 Petri 网建模方法 调度机制服务接口 以及动态多 QoS 任务调度算法等 该调度机制的目的是通过综合考 虑用户对任务 QoS 要求以及计算资源的多种属性 建立资源分配和 任务调度的 Petri 网模型达到资源的优化利用和任务的高效执行 并尽可能控制调度本身带来的成本 文章对调度机制的运行环境 系统结构和主要组件进行了简要说明 重点阐述了多 QoS 任务调度 算法的设计思想 调度原理和实现方法 实验和比较的结果显示了 算法的优越性和对 QoS 的保障 本调度机制符合 OGSA WSRF 标准 在 Globus 基础上构建面向网 格服务的框架 提高了服务的通用性 可移植性 有利于实际网格 调度系统的实现与开发 更好地与资源组织管理 作业管理等其它 网格服务结合 以此促进我国在网格资源应用上的基础研究工作 图 X 幅 表 X 个 参考文献 X 篇 关键词 网格计算 QoS 任务调度 调度机制 调度算法 分类号 XXXXXXXX XXXXXXXX III Research on QoS Guided Mechanism of Task Scheduling in Grid Computing ABSTRACT In this paper current research situation and problems of the key technique resources allocation QoS task scheduling scheduling mechanism scheduling algorithm Classification XXXX XXXX IV 目 录 原创性声明原创性声明 I I 摘要摘要 IIII ABSTRACTABSTRACT IIIIII 目目 录录 IVIV 第第 1 1 章章 绪论绪论 1 1 1 11 1 研究背景研究背景 1 1 1 21 2 国内外研究现状国内外研究现状 1 1 1 2 11 2 1 网格技术的发展网格技术的发展 1 1 1 2 21 2 2 网格网格 QoSQoS 研究研究 3 3 1 2 31 2 3 网格资源管理和任务调度研究网格资源管理和任务调度研究 5 5 1 31 3 研究意义研究意义 8 8 1 41 4 研究内容研究内容 9 9 1 51 5 内容组织与安排内容组织与安排 1010 第第 2 2 章章 结束语结束语 1111 2 12 1 研究工作总结研究工作总结 1111 2 22 2 下一步研究方向和目标下一步研究方向和目标 1212 参考文献参考文献 1313 致谢致谢 1414 攻读学位期间主要的研究成果攻读学位期间主要的研究成果 1515 发表论文发表论文 1515 参加科研项目参加科研项目 1515 硕士学位论文 第 1 章 绪论 1 第 1 章 绪论 1 1 研究背景 随着计算技术和网络技术的迅速发展 使用多种新型终端设备访问网络上 的计算和信息资源正变得越来越普及 并成为传统社会向信息化社会转型的一 个重要特色 信息化建设的进一步发展 表现出两个显著的趋势 一是计算资 源 设备资源以及各种信息资源都向网络化发展 二是访问这些网络资源的终 端设备朝多样化 小型化 智能化以及可移动的方向发展 这两种趋势牵引了 网格计算技术的发展 近年来 以服务为中心的新一代网格 服务网格的架 构已经提出并引起全球网格研究者的关注 这种面向用户 以封装服务形式的 新型网格技术已成为当前网格研究的热点 目前 以网格技术为核心的新一代网络计算环境的发展还处于初级阶段 仍然存在许多重大基础科学问题有待解决 其中最为核心和关键的问题就包括 网格计算环境中网格资源分配与任务调度的机制和方法 网格资源分配和任务 调度的基本功能是根据网格任务的需求 从众多的可用资源中 选择满足任务 需求并能最大化某种评价标准的资源 并将任务调度到匹配的资源上执行 传 统的计算机系统以提高系统吞吐量或缩短任务完成时间为单一目标 然而随着 网格结构的日益复杂 且不同组织采用不同的资源管理策略 致使资源使用者 和资源提供者的目标存在不一致 甚至完全相悖的情况 同时 网格应用要求 能够并发分配隶属于不同管理域的资源 进一步将网格任务调度机制复杂化 因此 描述与表示资源提供者与资源使用者的目标是进行网格任务调度的重要 依据 也是保证网格用户和其它服务 QoS 的前提 研究跨管理域的资源分配机 制和网格 QoS 保障已成为目前的重要研究方向 1 2 国内外研究现状 1 2 1 网格技术的发展 网格技术源于大型科学计算 是指在动态变化的多个虚拟机构间共享资源 和协同解决问题 1 与许多其他技术的发展一样 网格计算在学术研究领域诞 生 但迅速扩散到金融 汽车设计 生命科学和其他领域的各种商业应用中 其实质是在动态的可扩充的虚拟组织中可控且平等地使用和共享资源 而其中 最为核心的是为各种网络上的资源提供一种安全 高效的共享机制 使得各种 异构和孤立的资源能以一个整体为用户提供各种计算和信息服务 Error Reference source not found 硕士学位论文 第 1 章 绪论 2 目前国内外的政府 研究机构 IT 巨头们都在网格领域投入了大量的资金 进行理论研究和项目实践 网格基础设施的理论与技术也得到了飞速的发展 也经历了几个阶段的发展 在开放网格服务框架 OGSA Open Grid Service Architecture 出现之前 已经出现很多种用于分布式计算的技术和产品 但都 是各行其道 互不兼容 直到 90 年代末 这种混乱局面才有望结束 原因是此 时基于 XML Extensible Markup Language 可扩展标记语言 的 Web Services 技 术开始盛行 Web Services 之所以能够迅速走红是因为它在各种异构平台之上 构筑了一层通用的 与平台无关的信息和服务交换设施 从而屏蔽了互联网中 千差万别的差异 使信息和服务畅通无阻地在计算机之间流动 Web Services 得到了各大公司的支持 解决方案精彩纷呈 包括 IBM 的 WebSphere 微软 的 Net SUN 的 SunOne Oracle 的 Oracle9i 惠普的 eSpeak 等等 Globus 项目 组看到了 Web Services 的巨大潜力 在 2002 年迅速将 Globus Toolkit 的开发转 向了 Web Services 平台 2002 年 2 月 在加拿大多伦多市召开的全球网格论坛 GGF 会议上 Globus 项目组和 IBM 共同倡议了一个全新的网格标准 开放网格服务框架 OGSA Open Grid Service Architecture 它把 Globus 标准 Error Reference source not found 与以商用为主的 Web Services 的标准结合起来 网格服务统一以 Services 的方式对外界提供 OGSA 的诞生 标志着网格已经从学术界的象牙塔延伸到 了商业世界 而且从一个封闭的世界走向了开放的环境 2003 年 1 月 符合 OGSA 规范的 Globus Toolkit 3 0 Alpha 版 已经在第一届 Globusworld 会议 上发布 这标志着 OGSA 已经从一种理念 一种体系结构 走到付诸实践的阶 段了 目前 Globus Toolkit 已经发展到了 4 0 版本 2004 年 1 月 基于 OGSA 的一种新型网格服务资源框架 WSRF Web Services Resource Framework 问世 它定义了资源的状态 以及如何通过 Web Service 来发现 获取和操作资源 它促进了 OGSI Open Grid Service Infrastructure 的发展 并率先把 OGSA 的 思想付诸实施 目前网格技术的主流规范为 OGSA 和 WSRF 基于 OGSA 之后 网格的一 切对外功能都以网格服务 Grid Service 来体现 并借助一些现成的 与平台无 关的技术 如 XML Extensible Markup Language SOAP Simple Object Access Protocol 简单对象访问协议 WSDL Web Services Definition Language Web 服务描述语言 UDDI Universal Description Discovery and Integration 统一描述 发现和集成协议 WSFL Web Services Flow Language Web 服务流 语言 WSEL Web Services Endpoint Language 网络服务终端语言 等 来实现 这些服务的描述 查找 访问和信息传输等功能 这样 一切平台及所使用技 硕士学位论文 第 1 章 绪论 3 术的异构性都被屏蔽 OGSA 的模型结构如图 1 1 所示 应用 OGSA架构服务 OGSI开发式网格服务基础设施 OGSA使能的安全 工作流 数据库 消息 目录 OGSA使能的服务器 存储 网络 专 业 服 务 自 动 性 能 Web服务 图 1 1 开放网格服务框架 OGSA 的模型结构 当前大多数网格项目的实现都是基于 GT3 GT4 Globus Toolkit Version 3 4 所提供的协议及服务建设的 例如美国的物理网格 GriPhyN 欧洲的数据 网格 DataGrid 荷兰的集群计算机网格 DAS 2 美国能源部的科学网格和 DISCOM 网格 美国学术界的 TeraGrid 以及 BondError Reference source not found Nimrod GError Reference source not found Error Reference source not found LegionError Reference source not found 等等 而且网格项目也有向大型化发展的趋势 如美国国家 科学基金 NSF 支持的 TeraGrid 将连接位于五个不同地方的超级计算机 达到 每秒 20 万亿次的计算能力 并能存储和处理近 1 千万亿字节的数据 另外美 国军方正在实施的全球信息网格 GIG Global Information Grid 预计在 2020 年完成 IBM 在 2001 年 8 月宣布 将投入 40 多亿美元进行 网格计算创新计 划 Grid Computing Initiative 全面支持网格计算 IBM 因此成为 Globus 首 席合作伙伴以及 OGSA 标准的制定者之一 英国政府宣布投资 1 亿英镑 用以 研发 英国国家网格 UK National Grid 在亚洲 2003 年 6 月 26 日 日本 NTT 数据公司公布了自 2002 年 12 月 20 日开始进行的大型 PC 网格计算验证试验 Cell Computing 单元计算 的结 果 有 1 万 2206 台个人电脑参加 峰值性能超过了 3TFLOPS 2002 年 11 月 日本产业技术综合研究所网格计算研究中心宣布 在由多台个人电脑通过网络 连接组成网格计算环境下 实现了日美之间创纪录的 707Mbps 的数据传输 我 国也逐年加大对网格研究的投入和力度 仅 2002 年公布的 863 网格专项 就拨 出了上亿元的资金用于 China Grid 相关的研究 目前国内的网格项目主要有清 华大学的先进计算基础设施 ACI 和以中科院计算所为主的国家高性能计算环境 NHPCE 织女星网格项目以及上海教育网格等 硕士学位论文 第 1 章 绪论 4 1 2 2 网格 QoS 研究 由于近年来面向服务的体系架构 Service oriented architectures 作为一个基 本的问题被考虑 而面向服务的体系架构主要就是为所服务的客户提供确定的 QoS 保障 因此提供非平凡 Non trivial 的 QoS 将是网格的首要目标 不提 供此类支持的分布式资源将不可用 网络 QoS 是计算机网络中一个流行的研究领域 这个研究关注如何提供更 可靠的网络传输服务 满足应用的传输延时 延时抖动 分组丢失等质量保证 网格是运行在互联网络之上的 为满足高性能网格应用端到端 QoS 保证的要求 除了网络层次外 还需在网格系统结构上实现相应的保证 以下列举了一些已 有关于网格 QoS 的研究项目 文献 8 提出了一个基于 OGSA 的 SLA 管理实体在商业网格中支持 QoS 实体拥有一组方便管理和保证的协议 并设计了一种用于 SLA 的语言 文章通 过 SLA 来监控和保证网格的服务 设计了监控引擎 文献 9 提出了一个统一的协商模型 Service Negotiation and Acquisition Protocol SNAP 这是一种网格中的资源管理模型 SNAP 定义了三种类型的 SLA 用于描述在分布式环境中的复杂的服务请求 Task SLA TSLA Resource SLA RSLA 和 Bind SLA BSLA TSLA 用来描述任务 RSLA 描 述执行任务的资源 BSLA 描述了任务和资源之间的联系 预留模型可以封装 成一个请求在 RSLA 中执行 TSLA 类似于 QoS 请求 在用户提交期望服务的 同时附上资源的要求 文献 10 提出了一个称为 Virtual Application Service VAS 的结构 用于计 算网格中的 QoS 管理 它的主要目标就是处理实时性的服务或对截至时间有严 格要求的服务 因而该模型只支持时间的约束条件 系统有很多元数据 包括 和每个服务相联系的应用信息和应用模型信息 这样系统可以计算满足在时间 约束条件下任务执行的可行性 如通过执行时间和硬件资源信息 系统决定所 需的 CPU 资源 并可以实施资源预留 Global Grid Forum GGF GGF 的成员关注于网格 QoS 相关内容 GRAAP WG 已经提出了一份 GGF 草案支持网格中的资源预留属性 并且一份 基于 OGSI 的协议模型也正在探讨之中 这个基于协议的网格服务管理模型定 义了服务的 QoS 的行为和生命周期 GARA Globus Architecture for Reservation and Allocation 6 由 Argonne Lab Globus 项目提出 以支持端到端的 QoS 保障 是目前计算网格中最广为接 受的 QoS 框架 它的目标是为发起预留的客户端或应用程序能从资源管理者处 获得特定的 QoS 提供保障 其特点是 将预留资源与计算元素看作同样的实体 硕士学位论文 第 1 章 绪论 5 独立的进行创建 监测和管理 支持异构资源类型 GARA 分层次结构 使得 资源集的发现 预留 分配和管理可以被包装在 co reservation agents 和 Co allocation agents 中 与 GRAM 相比 GARA 多了 Co reservation agent 组件 支 持了资源的预留 缺点是不兼容 OGSA 不支持 SLA Service Level Agreement 缺少对应的 QoS 监控和调整函数 Grid QoS Manager G QoSM 有一批注重于研究 SLA 及 Agreement Protocol 的项目产生 其中包括 G QoSM Cardi University UK 这是以 G QoSM Grid QoS Manager 为代表的一类在服务网格中支持 QoS 的管理架构 它 基于 OGSA 可以管理和分辨网格服务的 QoS 属性 为软实时应用程序提供必 要的资源预留 以提供执行的开始时间保证 但不能提供结束时间的保证 G QoSM 的特点有 分辨 QoS 请求 根据资源的能力映射 QoS 请求 当请求不 能满足时 与资源所有者协商 与客户端建立服务层协议 SLAs 预留和分 配资源 在 QoS 会话期间监控相关的参数 当资源的质量特性发生变化时进行 适当调整 结束 QoS 会话 从上述项目可以看出 大部分的 QoS 是从系统管理的角度出发 主要集中 在结构和协议上 属于底层的基础设施 在本研究所关心的资源管理和调度层 目前关于 QoS 的调度研究不是很多 如 AQoS 是文献 11 提出的基于 G QoSM 和 GARA 使用 UDDIe 服务的一种调度算法 它所关心的 QoS 参数是资源的 利用率 从某种意义上 也是从系统的角度出发 还有一些网格计算中与 QoS 相关的调度研究有 QSMTS IP 是文献 12 提 出的一种异构计算环境下用于满足多用户时间 QoS 要求的算法 算法可以进行 静态调度 也可以改为动态调度 实验和 Max max 算法比较 能较好的同时满 足多用户不同 QoS 时间要求 文献 13 提出了基于策略的支持简单 QoS 的调度 机制 主要用于资源预留和提高资源的利用率 Distributed QoS Network Scheduler DQNS 是文献 14 提出的分布式网络调度器 它的目的是在分配 资源的同时考虑网络 QoS 路由 更趋向于满足一些网络相关的 QoS 要求 1 2 3 网格资源管理和任务调度研究 网格计算作为一种新型的分布计算和协同工作环境 能够提供超强的处理 能力 并有利于资源共享 因此受到广泛的关注 网格计算中包含很多关键技 术 其中资源分配和任务调度又是重中之重 因而成为研究热点 国外一些重大网格项目中的资源管理和调度研究有 LSF 由加拿大平台计算机公司研制和开发 从 Toronto 大学开发的 Utopia 系统发展而来的 LSF 是一个成熟的集群作业管理系统 资源管理采用集中式 模型 在任务调度方面的主要特点是提供抢占式调度 保证紧急任务的调度 硕士学位论文 第 1 章 绪论 6 可通过逻辑表达式创建任务依赖图 提供对依赖性任务的支持 提供了多种调 度策略 其中包括 Reservation 和 Backfill 等 Globus 由美国 Argonne 国家实验室实施的研究项目 该项目的主要研究 计划是网格技术的研究和相应软件的开发的标准的制定 目前 Globus 被认为 是计算网格技术的典型代表和事实上的规范 其资源管理体系结构采用典型的 层次模型 实现了层次模型的大部分被动组件和主动组件 资源描述与访问采 用可扩展模式模型 层次式名空间 软 QoS LDAP 网络目录存储 分布式基 于查询的发现 周期性推送分发等 在任务调度方面 提供较低级服务 支持 上层资源分配或者协同分配 提供高级工具执行调度等 BondError Reference source not found 由美国 Purdue 大学探索基于证券 市场的经济方法建立网格环境的一个项目 其资源管理体系结构采用层次模型 资源描述与访问采用可扩展对象模型 图式名空间 硬 QoS 基于语言的对象 存储与通讯 基于代理的发现 周期性推送分发 在任务调度方面采用采用分 布式调度 可预测价格模型 在线重调度方法 固定的面向应用的调度策略等 G Commerce 由美国 Tennessee 大学实施的研究项目 此项目使用市场经 济学在网格中进行动态资源分配 研究指出了资源的相对价值是根据供需变化 而变的 给出了 CPU 资源和磁盘资源的价格公式 并讨论了关于价格调整的问 题 Nimrod GError Reference source not found 由澳大利亚 Monash 大学开 发的一个专门用来模拟参数学习的网格项目 其资源管理体系结构采用典型的 经济 市场模型 资源描述与访问使用由底层 Globus 中间件服务所提供的资源 模型 依赖于计算节点的可用性 提供软 QoS 和硬 QoS 等 在任务调度中引入 经济方法 采用由计算经济和截止期限所驱动的应用级调度策略 遵循层次 分布式调度模型等 任务调度是资源管理的核心部分 它的重要性显而易见 无论是特定任务 的执行性能 如时间 费用等 还是整个系统的吞吐率 资源利用率都受到资 源调度质量的决定性影响 同时 它也是资源管理中最困难的部分 它的困难 性来自网格本身的特性 首先 网格是完全分布的动态环境 处于变化中的资 源的信息无法被实时更新 即调度中使用的资源的当前信息无法保证其正确性 其次 网格中的资源往往同时还有非网格的任务 即网格中的资源竞争包括网 格任务之间的竞争及网格任务和非网格任务之间的竞争 这种复杂的竞争使得 资源状态难以预测 而对资源在任务执行过程中的状态预测 主要是负载信息 是调度的主要依据之一 硕士学位论文 第 1 章 绪论 7 从不同的观察角度可把网格中资源调度策略按照不同的标准分类 下面根 据调度策略的目的 把调度策略分成三种 1 面向应用的调度策略 它是从特定任务的角度来衡量每个可能的调度方案 从中选择最大程度满 足特定任务要求的调度方案的调度策略 不同的任务可能有不同的要求 一般 的要求是尽量缩短任务执行时间 其他的要求包括 在使用计费资源时最小化 费用 在多个资源可用的情况下优先使用某个资源等 目前大部分调度策略都 属于这一类 如 Legion 中使用的方法 这一类策略完全不考虑调度方案对整个 系统的影响 如果网格中只采用这一类的策略 整个网格的性能可能受到一定 影响 2 面向系统的调度策略 它是从整个系统的角度来衡量每个可能的调度方案 从中选择能最大程度 提高整个系统的性能 如吞吐率 资源利用率 负载平衡等方案的调度策略 值得注意的是 在一个由许多管理域 Administration Domain 组成 有多种任务 的大规模的网格中 如果把整个网格作为一个系统 它的性能将无法衡量 所 以可以把网格在同一个管理域中的部分作为一个系统 由域中的管理者来进行 系统级的资源调度 即把整个网格划分成多个系统 在每个系统内执行资源管 理 在系统内采用面向系统的调度策略 在客户端采取面向应用的调度策略能 在一定程度上取长补短 同时兼顾应用任务和系统整体的性能 3 面向资源市场的调度策略 除了上述两类调度策略外 还有一些无法划入两种中任意一种的调度策略 最主要的是面向 资源市场 策略 这种调度策略由澳大利亚 Monash 大学的 Rajkumar Buyya 最早提出 它的主要思想如下 把网格环境和市场环境进行类 比 用户作为买方 而资源的拥有者作为卖方 资源调度的过程就是买卖双方 的交易过程 并把宏观经济学和微观经济学的各种模型应用到网格资源调度过 程中 如拍卖模型 邮件广告模型等 结合上一节网格 QoS 研究 总的来说 当前在网格计算的资源分配和任务 调度方面的研究还存在以下问题 1 目前的网格 QoS 研究和资源分配 任务调度策略大部分以系统为中心 较少考虑用户 QoS 要求的相异性和多样性 也较少考虑用户需求的多 目标性 这就导致了存在资源分配无效和不公平的情况 2 现在的任务调度技术一般不支持资源联合分配或者支持能力很弱 已 有的联合分配方法采用的都是类似于网状的结构 难以获取全局状态 信息 调度过程中通信开销大 联合分配器负担过重 硕士学位论文 第 1 章 绪论 8 3 现在的资源分配和任务调度技术较难适应资源供需的动态变化 目前 资源分配和任务调度时 在考虑负载变化的同时很少考虑资源能力的 变化 而网格环境下却经常发生资源能力变化的情况 4 目前在实现资源分配和任务调度策略中 缺乏形式化的建模和描述方 法 性能评价方法 5 任务调度是根据用户提交的任务按照任务的类型 所需资源 可用资 源等情况来安排运行日程和策略 在实际的网格资源调度上 每个管理域都在开发各自的调度系统 很少利 用已有的各个领域的研究成果 因此开发周期长 效率低 很难建立一套合理 灵活 高效的调度机制 1 3 研究意义 资源分配和任务调度在网格资源管理系统中占据重要的地位 它对系统 资源的使用状况以及任务的执行 用户的满意度等都产生直接的影响 并和 系统中其它模块如资源发现 作业管理等密切相关 本课题通过对 网格计 算中面向 QoS 的任务调度机制和算法 的研究 在 Globus 基础上建立面向 QoS 的资源管理和任务调度模型 有机地集成资源筛选 任务调度模型 算 法等功能模块 并研究各个模块之间的数据接口和服务要求 建立适应任务 的多种 QoS 要求并满足不同用户要求的网格资源分配和任务调度的服务框架 本项目研究意义如下 1 调度机制研究 它将为网格计算的相关研究和应用服务提供理论基础 和支撑环境 目前国内外在资源分配和任务调度的相关研究上已经取得了一 些成果 包括资源发现 资源筛选 调度算法等 但这些研究成果都只是基 于资源分配和任务调度中的某个或某些局部问题取得的 而且很多是理论成 果 还没有一个机制框架能够提供相应的接口模块来融合并利用已有的研究 成果 以便在实际的网格环境中建立一个高效 可移植的资源分配和任务调 度机制 当前迫切需要建立一个开放的机制来实现合理 灵活 高效的资源 分配和任务调度来和其它服务交互 因此 本项目的研究将有助于建立网格 计算环境中资源分配和任务调度的统一机制 有利于将目前已取得的一些宝 贵研究成果应用到实际的网格资源分配和任务调度中 并为今后的相关研究 和实际的网格系统实现提供理论基础 方法指导和支撑环境 2 网格中的 QoS 研究的重要性 QoS 等于一组服务集合的性能 该性 能决定用户对服务的满意程度 它是网格区别于 基础设施 或 中间件 的一 个关键要素 从网格服务的概念看 随着计算网格 数据网格直到服务网格 的发展 网格作为广泛 分布的服务 与用户和其它服务的交互决定了 QoS 硕士学位论文 第 1 章 绪论 9 是其内在需求 从多样的用户需求看 不同的用户 甚至同一用户对服务的 功能 性能 成本等都有不同考虑 因而使 QoS 变得重要 从网格资源的异 构性看 网格资源是异构的 它必须为用户提供单一系统映像 透明地满足 用户需求 因而 QoS 直接关系到网格系统的性能 3 满足不同用户对 QoS 的不同需求 本项目将研究各种异构网格资源 性能和应用需求的描述模型 并基于多 QoS 建立网格资源与应用需求之间的 映射以完成对计算资源的筛选 同时研究并设计一个以用户为中心的 融入 QoS 保证机制的动态多 QoS 网络资源分配和任务调度服务机制 达到对网格 环境进行规范化和高效管理 因此 本机制的建立将综合满足网格系统和用 户任务调度的需求 提供良好的服务质量 推动网格核心技术的向前发展和 基础理论研究 总之 网格计算环境中的资源分配和任务调度正处于研究初期 各种理 论和算法都在探索阶段 而且各项研究都处于各自为政的状态 没有一个开 放的集成机制来集成各项研究成果 缺乏一个提供统一服务接口的集成环境 影响和制约了研究的推广和应用 因而为资源分配和任务调度建立开放的集 成环境迫在眉睫 同时 网格本身的特点给研究满足系统和用户多目标的调 度机制带来了巨大的挑战 并为设计复杂而精妙的调度系统提供了动力 1 4 研究内容 为适应任务多种 QoS 要求并满足不同的用户目标的网格资源分配和任务 调度服务 本课题将在既有 OGSA WSRF 框架标准基础上 开展在网格计算 中面向 QoS 的任务调度机制和算法的研究 具体研究内容包括 1 面向 QoS 调度机制的框架结构研究 在网格调度层 结合已有的网格服务和基础设施 集中考虑任务调度过 程中的关键步骤和用户的多种 QoS 要求 设计一个合理 高效的任务调度机 制 且具备相关接口的实现满足服务网格的架构 调度机制中主要步骤为在 提取任务 资源的 QoS 属性基础上进行资源的初步筛选 接着运用一定的调 度算法进行任务调度 且在调度中保障 QoS 要求 2 调度机制中相关组件的实现原理研究 根据调度机制运行的关键步骤划分组件 主要构成和研究内容有 不同 网格任务需求和资源 QoS 参数的提取方法 基于任务需求与资源 QoS 参数之 间的映射关系 实现资源筛选的原理和方法 通过考虑任务之间的约束关系 以及资源的动态变化情况 研究基于 Petri 网的任务调度模型 调度机制的服 务接口类型和实现原理研究 3 多 QoS 的任务调度算法研究 硕士学位论文 第 1 章 绪论 10 在 Petri 网调度模型基础上 研究如何在任务调度过程中综合考虑任务的 多种 QoS 需求 如时间 价格等 和资源的动态变化 设计一个有效保证 QoS 的任务调度算法 算法要能切合网格实际情况 具备一定的优越性 1 5 内容组织与安排 本论文详细介绍了网格技术以及任务调度的研究现状和发展 并对任务 调度中的关键问题提出了作者自己的看法和观点 为了更好地诠释观点和阐 述研究内容 全文主要分为五个章节 第一章主要介绍了本论文的研究背景 国内外在网格方面的研究现状和 发展趋势 以及论文的研究意义 第二章分为两部分 重点介绍了网格计算中关于 QoS 和任务调度方面的 研究工作 同时针对一些关键性问题 如网格 QoS 的分层和要求 任务调度 的组成等进行了详细的解释 第三章和第四章是本论文的核心 也是作者的主要研究内容 第三章提 出了面向 QoS 的网格任务调度机制 包括机制的模型 环境 组成 关键技 术和实现方案等 第四章详细说明了作者设计的基于模糊贴近度 以时间和 价格为 QoS 的任务调度算法 并对算法进行了验证 第五章对所作研究做了总结并提出了未来的工作方向 硕士学位论文 第 2 章 结束语 11 第 2 章 结束语 2 1 研究工作总结 本研究旨在通过任务调度中关键问题研究建立面向 QoS 的有效 统一调度 机制并设计相应的调度算法 以保证和适应网格及其任务的多种 QoS 要求 通 过对 网格计算中面向 QoS 的任务调度机制和算法 的研究 在 OGSA WSRF 的框架下 利用神经网络以及 Petri 网强大的模糊推力和建模分析能力 建立面 向 QoS 的调度机制模型 并有机地集成任务 资源 QoS 参数抽象 资源筛选 任务调度模型 算法 调度等功能模块 实现适应任务多种 QoS 要求并满足不 同的用户目标的网格资源分配和任务调度服务 本研究主要内容包括 1 介绍和总结了当前国内外网格研究以及网格 QoS 任务调度方面的研究 现状和关键问题 文章介绍了网格技术的特点 发展过程和三大趋势 分析和总结了当前国 内外网格计算中关于 QoS 以及任务调度方面的研究现状 对网格 QoS 的结构 要求和资源管理的特点 分类进行了简要说明 重点对任务调度的技术特点 分层模型 当前的算法及其存在的问题进行了较为详细的阐述 2 提出面向 QoS 的网格任务调度框架 研究以提供网格调度服务为前提 在 OGSA WSRF 框架下 结合 Globus 服务 提出了面向 QoS 的网格任务调度机制 机制由资源 任务属性 QoS 参数 提取 资源筛选等调度预处理模块 基于 Petri 网的任务调度模块以及机制的服 务接口等组成 目的是保证用户对所需网格服务的 QoS 实现网格服务的交互 调用 同时满足高效 合算的任务调度 3 提出基于模糊贴近度的多 QoS 网格任务调度算法 在上述调度机制的环境下 设计了一种基于模糊贴近度的多 QoS 网格任务 调度算法 算法以时间和价格为目标 运用模糊数学中的贴近度来表示资源和 任务匹配程度 通过比较任务和资源的贴近度来得到每个任务的可用资源集 然后选取整体匹配度最大的一组调度方案作为最优解 算法为用户对任务的求 解所考虑的因素提供了权值选择 这在很大程度上适应了网格应用的需求和方 向 实验结果表明算法能综合考虑时间和价格的因素 文中以 FAA 和几个经典 启发式算法比较为例 可以得出当对用户关心的目标设定相应的权值后 算法 保证了 FAA 的完成价格最低 并在性能指标上有所改善 硕士学位论文 第 2 章 结束语 12 2 2 下一步研究方向和目标 由于服务网络的发展还刚刚起步 处于初级阶段 仍然存在许多重大基础 科学问题有待解决 许多研究模型和算法都还带有实验性质 非常不成熟 虽 然国内外已取得一些研究成果 但仍有大量的研究课题值得深入 特别在网格 计算领域 其中最为核心和关键的问题就网格资源分配与任务调度的机制和方 法 因此 本研究的进一步开展有着广阔的前景和应用空间 在本论文中 调度机制的结构只包含了任务调度过程中必需的功能 所提 供的服务功能也较为简单 因此接下来的工作是首先是增加机制的组成模块 如调度评测 性能预测等功能 使得机制的组成更加完整 其次是完善接口服 务 如增加创建临时服务 Factory 主键服务 PrimaryKey 以及升级管理等类型 功能 在调度算法方面 增加任务和资源的描述因素 即增加贴近度公式中的维 度 如网络要求 存储要求等 以备有更多的调度目标可供用户选择 更贴近 实际的网格环境 硕士学位论文 参考文献 13 参考文献 1 Foster I Kesselman C and Tuecke S The Anatomy of the Grid Enabling Scalable Virtual Organizations J International Journal of Supercomputer Applications 2001 15 3 200 222 2 Foster I What is the Grid A Three P