网格多集群环境和计算市场环境中的作业调度和资源分配研究

摘要

网格是建立在Internet上的一种新型的信息技术基础殴施，目的是无缝地集成广域资源来合作解决问题，实现计算资源、存储资源、通信资源、软件资源、信息资源、知识资源的全面共享。如何有效管理广域的、异构的、动态的、自治的网格资源是网格技术研究的重点和难点．传统的作业调度方法难以奏效。 本文首先介绍网格的概念、演变和分类，分析了网格凋度面临的问题。随后第二章在回顾传统调度理论的基础上。结合网格环境，归纳了调度问题住网格环境中的新特征：资源大规模异构性、环境动态不可靠性以及面向用户需求的特性。从两种典型环境入手，通过分析网格社区多集群环境和网格计算市场的特点，针对多集群环境提出基于“全局-局部”模式的层次调度方法，针对计算市场提出基于双向选择的分布式调度方法。 本文第二章提出了多集群一致监控的解决方案，设计了一种自描述方法以解决异构资源信息的公共表示问题，基于Ganglia，GridView，PBS等监控工具设计实现了一个通用的资源监控系统。殴计了一种自适应的RTT感知的最小生成树策略以改善系统的可扩展性。 论文第四章针对多集群提出了“全局-本地”的二阶段超级凋度算法。针对计算密集型应用，在传统的批调度算法中加入对任务完成时限用户QoS的考虑,提出了多集群环境下OoS感知的批调度算法，并应用于多集群的全局队列调度中，与传统批调度算法相比，任务按时完成比率有明显提高。同时，该算法对任务执行时间的预测误差也具有良好的适应性。 论文第五章致力于研究经济市场和信任评估相结合的激励机制，把信任机制融入Buyya的网格计算市场模型,提出了网格中信任感知的资源交易模型(Grid Trust Aware ResourceTransaction Model，简写G-Tart模型)，详细研究G-Tart模型中的实体、模块、交易流程。在G-Tart模型中，把信任度作为衡量节点交易诚信度的重要指标，激励节点履行已达成的资源交易合约。引出了G-Tart中两个关键问题，即任务代理的资源选择问题和资源代理的任务接受问题。 论文第六章从用户代理角度出发，提出了一种基于信任过滤的资源选择方法。该方法首先根据用户信任需求过滤低可信资源，然后对剩余高可信资源综合考虑其价格和风险因素，最后给出了最小机会成本启发式算法。实验表明，该方法能对供求双方产生激励：对资源方保证可靠资源提供者的整体利润：对用户方能显著降低作业失效率、减少成本8％-10％。 论文第七章从资源代理角度出发，提出基于收益和成本计算的任务接受策略，根据用户提交任务的相关信息，计算接受任务的沉没成本和机会成本以决定是否接受任务，使得资源捉供者和资源请求者都实现自身的经济目标，提高了服务方的收益。 论文第八章基于G-Tart模型，利用供求规律，设计了一种分布式调度系统，实现了Oppsim模拟器以模拟该系统。该系统采用用户与资源进行双向选择的模式，通过启发式的策略，动态调节资源价格，引导用户和资源的行为。模拟结果表明该系统能有效解决网格环境中资源负载平衡问题，具有良好的灵活性和可扩展性，能有效提高服务质量，任务完成率方面比Nimrod/G提高了22.5％。 本文从网格大规模、动态性和以用户为中心等特点出发，对两种典型网格环境的调度问题进行了深入分析和有益实践。针对多集群环境提出基于“全局一局部”模式的层次调度方法和实现方案，具有较强的现实意义；针对计算市场提山G-Tart模型，基于激励驱动的分布式调度方法，为未来经济可行的网格展示了全新的视角和美好的前景。

目录

文摘

英文文摘

论文说明:图表目录

声明

第1章绪论

1.1研究背景

1.1.1网格的内涵

1.1.2网格的演变

1.1.3网格的分类

1.2问题的提出

1.3研究现状和主要的网格项目

1.3.1国外的一些网格研究及项目

1.3.2国内的主要网格研究及项目

1.4论文主要工作

1.4.1论文研究内容

1.4.2论文的组织结构

1.5本章小结

第2章调度原理概述利网格调度新特征

2.1引言

2.2调度原理：基本调度框架和符号

2.2.1调度框架基本模块

2.2.2符号术语

2.3调度问题典型实例

2.4调度问题在网格环境下的新特征

2.4.1资源特点

2.4.2环境约束

2.4.3目标函数

2.5两类典型的网格环境

2.5.1网格社区多机群环境

2.5.2网格计算市场

2.6本章小结

第3章多集群调度的基础：网格多集群监控

3.1引言

3.2相关工作简介

3.3通用资源监控框架UGMF的设计

3.3.1基本架构

3.3.2关键模块设计

3.3.3可扩展性设计

3.4原型系统

3.4.1原型系统实现

3.4.2测试和分析

3.5本章小结

第4章基于超级调度者的多集群全局调度方法

4.1引言

4.2基于“全局—本地”的调度流程

4.3服务质量感知的全局批调度算法

4.3.1问题描述和相关工作

4.3.2服务质量感知的批调度算法

4.4试验模拟利结果分析

4.4.1调度算法性能比较

4.4.2预测误差对调度算法性能影响分析

4.5本章小结

第5章网格市场信任感知的资源交易模型G-Tart

5.1引言

5.2基于市场机制的网格资源管理的优点

5.2.1基于市场机制的网格资源管理的相关工作

5.2.2相关工作中存在的不足

5.3信任感知的资源交易模型G-Tart

5.3.1信任的定义及主要特征

5.3.2 G-Tart实体和功能模块

5.3.3 G-Tart交易流程

5.4 G-Tart资源交易模型中的关键问题

5.4.1任务代理资源选择策略

5.4.2资源代理的任务接受策略

5.5本章小结

第6章G-Tart中基于信任过滤的资源选择算法

6.1引言

6.2相关工作

6.3基于信任过滤的资源选择方法

6.2.1信任和计算市场

6.2.2影响资源选择的主要因素

6.2.3基于信任过滤的最小机会成本选择算法

6.3模拟试验和性能分析

6.3.1试验场景设定

6.3.2模拟内容

6.4本章小结

第7章基于收益-成本计算的作业接收算法

7.1引言

7.2任务调度模型和主要参数

7.3基于成本计算的在线调度任务接收策略

7.3.1首个任务的接收策略

7.3.2 非首个任务的接收策略

7.4实验和结果分析

7.4.1收益与机会成本的关系

7.4.2平衡因子α和β参数调优过程

7.4.3不同α和β下收益的比较

7.5本章小结

第8章基于动态定价的调度系统和Oppsim模拟器

8.1引言

8.2系统建模

8.3系统设计与实现

8.3.1逻辑设计

8.3.2网格资源运行步骤

8.3.3用户代理运行步骤

8.3.4 GridInfoServer运行步骤

8.4模拟实验和分析

8.4.1试验设定

8.4.2模拟试验

8.5本章小结

第9章结束语

9.1主要工作总结

9.2主要贡献和创新点

9.3进一步的工作

参考文献

攻读博士学位期间发表的论文

攻读博士学位期间参加的项目

致谢