云计算环境下的自主调度技术研究

摘要

云计算是信息技术革命的产物，是一种大规模复杂计算系统。云计算系统时刻都在处理海量数据和应用任务，具有高度的动态性。由于云计算系统具有资源规模庞大且异构多样、用户群体广泛、应用任务类型各异且QoS目标约束各异等特性，系统需要频繁地对云平台中的各种资源与应用任务进行实时调度和动态管理。而云计算作为一种商业计算模式，其目的是实现资源共享与协同工作，并同时满足用户的服务请求和云服务提供商的服务收益。因此，如何对云资源进行合理的分配，对海量应用任务进行高效管理与实时调度，在确保云计算系统负载均衡和提高云资源利用率的前提下，降低用户的成本，提高云服务提供商的收益，是目前云计算环境下的研究热点之一。
　　从本质上说，云计算环境下的任务调度是需要建立一种应用任务与计算资源之间合适的映射关系的调度策略，其目的是实现计算资源的合理分配与应用任务的高效执行。早期传统的分布式计算系统、网格计算系统等，通过系统吞吐量和任务完成时间等性能指标衡量调度管理的效果。但是在云计算环境下，任务调度问题往往更加复杂。首先，云计算环境下应用任务请求往往是非集中式的，而且规模巨大，传统的集中式的资源管理系统已经不再适用，云计算系统必须以一种分布式的并行模式对任务和资源进行调度与管理；其次，云资源通常来自不同的云服务提供商，各个机构的云资源往往是异构的，如何将各种异构资源组合成完整的服务提供给用户是非常复杂的；再者，由于云计算系统具有动态可扩展的性质，相应的任务调度也必须满足可扩展性与自适应性；然后，云计算作为一种商业模式，云服务提供商首先要考虑的是如何提高自身的资源利用率，提升共享使用率从而降低成本，获得尽可能多的服务收益，这就使得任务调度必须考虑云计算系统的整体负载均衡问题。最后，从用户的角度而言，云服务提供商所提供的服务是否满足用户任务调度的QoS多目标需求是任务调度策略必须考虑的问题。
　　因此，针对上述目前云计算环境下任务调度存在的问题，本文对云环境下的任务调度技术做了详细而系统的研究，其主要内容包括四个方面：云环境下用户任务调度的QoS多目标优化问题、云资源利用率与云计算系统负载均衡问题、云计算系统任务调度策略执行效率问题、用户任务调度成本与云服务提供商服务收益问题。本文在对这些问题进行深入研究的基础上，设计了一套云计算环境下的自主调度体系架构，并对其中重要功能都给出了详细的算法与实验结果。论文的主要研究内容包括以下几个方面：
　　1）在分析和研究了云计算环境下任务调度存在的问题及目标要求的基础上，提出了一种云计算环境下的自主调度体系架构。在自主调度体系架构中，系统为每个向云计算系统请求服务的用户创建一个云代理进行智能分析和决策，并为每个云代理设计了分析、评估、博弈等功能与算法。本文通过对云代理功能进行分类，设计了一个两层的自上而下的自主调度模型。其中，针对用户与云服务提供商之间的协商问题，设计了云代理协商模型。云代理通过一系列约束规则与目标规则选择符合用户QoS目标约束的SLA协议，并对SLA协议进行评估。其次，针对多个用户对关键资源的竞争而导致的资源冲突问题，设计了云代理博弈模型。云代理将系统全局收益函数引入到用户个体的收益函数中，在满足用户QoS多目标优化需求的前提下，云代理之间通过自主竞争博弈的模式，使整个系统达成全局利益最优。云代理通过协商、自主博弈的方式实现了用户任务的自主调度，提高了任务调度策略的执行效率，并且降低了用户的调度成本，也提高了云服务提供商的服务收益。
　　2）针对在云计算环境下，用户如何判断云服务提供商在SLA中承诺的资源是否满足用户任务的QoS需求，本文提出了一种星型结构下的SLA任务调度评估算法。该算法通过云代理将云服务提供商SLA中承诺的资源抽象为标准的虚拟资源，并将用户任务与虚拟资源的映射关系抽象为星型拓扑结构的云计算系统。通过评估云计算系统的性能与可靠性，评估相应云服务提供商所承诺的资源的服务质量。用户将SLA中承诺的服务质量作为一种判断标准，判断云服务提供商提供的服务是否能够满足用户任务的QoS需求。
　　3）针对用户任务调度的QoS多目标优化问题，提出了一种基于NSGA-II的多目标优化调度算法。云计算环境下，用户如何在一组有效的SLA集合中，选出符合其QoS多目标优化需求的调度策略依然是非常困难的问题。用户请求的任务集通常包含多个任务，每个任务都可以和不同的云服务提供商签订SLA协议，整个任务集的SLA协议由单个任务的SLA协议组合而成，组合过程往往呈现出指数级的复杂度。另一方面，用户的QoS目标之间往往是冲突的，例如，服务时间和服务成本之间是冲突的，要获得快速响应的服务，就需要计算能力较高的资源，而计算能力越高其成本就越高，必然无法同时满足两个目标。本文提出的算法为用户提供了一种高效快速的选择机制，通过NSGA-II算法对多个目标进行并行搜索，与传统的将多个目标转化为单目标问题相比，本文的算法能够在满足用户QoS多目标优化需求的前提下，高效地为其选择合理的最优的SLA任务调度策略。
　　4）在已经签订了SLA协议的情况下，用户任务选择SLA中不同的云资源构成了不同的任务调度策略。针对如何判断哪些调度策略满足用户的QoS多目标优化需求，提出了一种虚拟树型结构下的调度评估算法。根据云资源的性质，将用户任务与云资源的映射关系建模为由网络连接起来的虚拟树型结构。在树型结构下，通常需要考虑共享传输通道失效引起的共因失效问题。针对此问题，本文利用最小生成树算法对云资源与传输通道进行数学建模。对于一个任务分配给多个资源节点冗余执行的情况，只要存在一个资源节点不失效，该任务就能成功完成；对于多个任务共享同一资源的情况，算法通过在云资源节点上增加新的分支和叶子节点，如果是并行任务就平均分配共享资源，如果是串行任务则独享资源。因此，在树型结构下，用户任务与云资源之间是一种动态灵活的映射模式。本文提出的算法能够对任意一个任务调度策略的服务质量进行快速且准确的评估，将其应用于云代理博弈模型的效用函数计算中，在提高每个用户的调度策略执行效率的同时，也提高了云服务提供商的资源利用率。
　　5）针对大量用户同时提交任务调度请求的问题，以及多个用户之间对关键资源的竞争问题，本文在博弈论的基础上提出了一种基于囚徒困境博弈的多代理自主调度算法。该算法假设每个用户具有自己的偏好和自私性的特性，总是倾向最大化自己的利益，每个用户都只会选择对自己最有利的资源，不管是否对其他用户产生影响。由于用户的个体理性，形成了囚徒困境，导致了资源分配冲突，比如大多数用户都选择了同一个资源，使得系统负载不均衡。算法通过云代理之间的自主博弈过程，将云计算系统的全局效用目标融入到每个用户的局部效用目标中，通过设计云代理之间的博弈规则和对应的奖励因子，在每个云代理追求各自效用目标的前提下，使得整个云计算系统获得全局最优收益。通过本文提出的自主调度算法，不仅使竞争性环境下的每个用户都能找到最优的任务调度策略，同时也降低了用户的调度成本，提高了云服务提供商的整体收益。

目录

第一个书签之前

Abstract

第一章 绪论

1.1 课题的研究背景

1.2 国内外研究现状

1.3 论文的研究内容

1.4 论文的组织结构

第二章 云计算环境下的自主调度体系架构

2.1 引言

2.2 云资源自主调度需求

2.3.1 自主调度体系架构

2.3.2 云代理协商模型

2.3.3 云代理博弈模型

2.4 本章小结

第三章 星型结构下的SLA任务调度评估算法

3.1 引言

3.2 星型结构下的SLA协议模型

3.3 星型结构下的性能与可靠性分析

3.3.1 独立任务集性能与可靠性关联分析

3.3.2 关联任务集性能与可靠性关联分析

3.4 基于通用生成函数的性能与可靠性联合评估算法

3.4.1 独立任务集性能与可靠性联合评估

3.4.2 关联任务集性能与可靠性联合评估

3.5 实验分析

3.5.1 独立任务集实验分析

3.5.2 关联任务集实验分析

3.6 本章小结

第四章 基于NSGA-II的多目标优化调度算法

4.1 引言

4.2 任务集QoS指标分析

4.2.1 服务性能与可靠性

4.2.2 服务成本

4.3 任务集QoS多目标优化问题

4.3.1 任务集约束条件

4.3.2 任务集优化目标

4.4 基于NSGA-II的多目标优化调度算法

4.4.1 非支配排序基因算法

4.4.2 SLA任务调度策略基因编码与运算

4.4.3 最优SLA任务调度策略搜寻算法

4.5 实验分析

4.6 本章小结

第五章 虚拟树型结构下的任务调度评估算法

5.1 引言

5.2 云计算环境下的虚拟树型结构

5.2.1 虚拟树型结构分析

5.2.2 性能与可靠性分析

5.3.1 最小任务生成树

5.3.2 独立任务集性能与可靠性联合评估

5.3.3 关联任务集性能与可靠性联合评估

5.4 实验分析

5.4.1 独立任务集实验分析

5.4.2 关联任务集实验分析

5.5 本章小结

第六章 基于囚徒困境博弈的多代理自主调度算法

6.1 引言

6.2 云代理自主博弈过程

6.3 基于NSGA-II的任务调度策略空间

6.3.1 调度策略基因编码与运算

6.3.2 NSGA-II算法流程

6.4 单用户最优调度策略

6.5 多代理自主博弈调度算法

6.5.1 非合作博弈模型

6.5.2 全局调度策略组合

6.5.3 自主博弈调度算法

6.6 实验分析

6.7 本章小结

第七章 总结与展望

7.1 论文工作总结

7.2 未来研究展望

致 谢

参考文献

攻读博士学位期间取得的成果