面向云计算任务优化调度技术研究

在云计算系统的调度架构中，考虑整个系统的稳定性和容错性，尤其保证用户任务在执行中的正确性及完整性，需要在任务调度管理中加入副本管理机制，这需要在现有云计算调度结构上进行改进。云计算调度结构如图1-4所示。

图1-4　云计算中的资源分配和任务调度

副本管理机制的主要研究内容包括副本放置、副本的复制两方面技术。

（1）在副本放置的具体方法研究中，典型的商业应用例子，如 Amazon S3（Amazon Simple Storage Service）［16］、Google文件系统GFS（Google File System）［17］、Hadoop分布式文件系统HDFS （Hadoop Distribution File System）［18］等。

在副本的放置策略研究方面，又分为两类，HDFS、GFS采用基于集中式的存储目录、定位数据对象的存储位置的策略；而Amazon S3采用基于一致性哈希的副本放置策略。第一种副本放置策略的问题在于，可用的副本存储节点不一定是最佳的副本存储节点，并且 Amazon S3采用的策略算法决策时间较短，没有考虑副本分布的随机性。

因此，针对随机性的不同影响，考虑副本放置的优化问题，在研究方向中可以加入研究副本放置对于系统的不同影响以及动态的副本最优放置策略。

（2）在副本的动态复制策略方面，可以根据系统中的数据的可用性和其应用热度，完成动态副本复制机制；将副本的放置与系统的负载平衡技术联系起来，完善副本的存储技术以及副本处理、冗余处理技术。同时，根据访问记录及访问热度来选择数据信息进行复制，完成动态的、成本敏感的、优化的数据复制策略。列举部分研究进展如表1-1所示。

表1-1　副本放置、复制研究分类

（续表）

因为前期的研究重点在副本本身的更新、放置问题上，没有体现在具体的系统架构上，因此值得进一步研究。

云计算作为新兴的计算技术，任务调度与传统的分布式环境中的任务调度不同。在传统分布式环境下，资源规模是同构的、固定不变的，而在云计算环境中，资源是实时变化的且具有异构性；传统分布式环境根据特定的应用来制定对应的调度策略，而云计算任务优化调度策略能够支持多种类型的应用，亦可同时运行多种应用；在实际应用中，传统分布式环境下的任务优化调度考虑系统整体性能指标，而在云计算环境下，任务优化调度策略不仅要满足用户对于执行时间、成本、资源分配公平性等的目标约束要求，同时需要考虑服务提供商的服务收益。

在云计算服务中，按照服务提供商和资源消费者的关系可以分为三类，即云提供商、服务提供商、用户。各关系间的层次结构如图1-5所示。

位于最底层的云资源提供商向服务提供商提供云计算资源；云服务提供商从云资源提供商处租赁或者购买资源，并按照消耗支付给云资源提供商相应的费用；用户使用服务提供商在云资源上部署的软件。云计算系统用户可以根据需要购买云计算资源或服务，并且不用关心所请求的资源具体部署在什么位置，对于云系统用户来说，云计算系统的资源是无限的。

图1-5　云计算中资源提供及使用的分类描述

因而，云计算作为商业计算，其任务调度策略必须确保用户任务调度的QoS（Quality of Service，QoS）尽可能地得到满足，这是云服务提供商获取服务收益的必要条件。云计算用户任务调度的QoS目标约束条件包括任务的截止时间底线、调度预算、系统的可靠性以及安全性等诸多内容。在考虑用户的QoS目标约束要求时，需要分析用户的QoS需求，并将任务根据不同的优化调度策略，映射到能够满足QoS需求的资源上；在建立任务优化调度策略时将任务调度分为静态任务调度和动态任务调度两种类型。部分研究如表1-2所示。

表1-2　云计算考虑用户利益的任务调度研究

（续表）

(www.xing528.com)

（1）静态任务调度。对于用户来说，最优资源分配方案以及任务优化调度的目标是在任务调度运行过程中，保证任务所经过的路径短、引起的时延小，在一定程度上提高应用的服务质量。

根据上述静态任务调度的特点，将云计算技术与工作流技术相结合完成。云工作流调度是解决在云计算环境中工作流管理系统的流程与任务调度问题，工作流调度算法则具有在满足QoS限制的前提下，对任务进行调度，达到缩短流程运行时间、提高性能的目的。

目前学术界的研究和工业界的应用，都已经对云计算系统中的资源分配问题展开了初步的探索，并取得了一定的成果。但目前基于启发式思想的策略在求解云计算系统中的资源分配问题时存在以下局限性：仅考虑资源分配的可行解，缺乏对解的优劣性的评估，动态分配过程中容易产生碎片资源，分配效率低下；并且，启发式算法更适用于调度单个的工作流，对于调度多个较复杂的工作流，其性能有待提高。

（2）动态任务调度。相对于启发式算法，随着智能算法的出现及发展，在面向用户的需求的体系结构下，利用智能调度算法在满足多个工作流的传输结果的最后期限的前提下，根据工作负载、工作流之间的依赖关系，把整个工作流的最后期限发布到每个任务，然后进行调度执行。

在针对工作流调度方面，根据多个较复杂的工作流应用的特点，针对多个较复杂工作流的应用，提出使任务调度过程优化的调度策略，该策略包含在实例层和任务层进行任务调度。

在实例层的调度是通过提高负载的均衡度，从而进一步提高整个云计算系统的任务调度效率；任务层是通过减少资源调度过程中的冗余时间进行调度的，进而提高整个系统的资源的利用率。但是，由于云计算环境的复杂性，某一方面的优化及改进并不能很好地满足云资源调度的要求以及动态任务的优化调度。

云计算从根本上来说，强调的是按需服务的模式，当为用户请求的任务分配资源时，会出现必须同时提供多个资源以满足用户需求的情况。如要满足用户对某些服务的需求，就需要将云计算中多个资源进行合理分配、有效调度。

作为一种商业服务，面对不同用户各不相同的应用任务调度QoS目标约束要求，云计算在满足用户任务调度QoS目标约束条件的同时，还应尽可能地最大化云服务提供方的服务收益。然而，目前大多数的云计算任务调度策略通常从用户的角度出发，致力于满足用户任务调度的各种QoS目标约束要求与资源请求，而忽略了云服务提供商的服务成本和服务收益问题。

面对云计算的商业应用价值，云计算任务的调度策略重点应转移到在考虑市场驱动或经济驱动的前提下，如何使得算法考虑不同的QoS参数，根据用户定义的某种QoS偏好来调整算法，进而完成对任务的优化调度。而且在商业应用方面的云资源分配、任务调度解决方案是包含了云服务提供商所关心的提高系统性能、云服务提供商的利益解决方案的。

针对以上对于云计算系统中任务优化调度的目的要求，应从以下几个方面考虑提高云服务提供商的利益。部分研究人员的研究方向如表1-3所示。

表1-3　云计算考虑服务提供商的任务调度研究

（1）提高系统的性能，包括缩短任务的响应延时、保证系统的负载平衡、提高系统的利用率。

但是，以上研究依据不同的目标要求进行局部最优解的搜索，收敛速度有一定的差别，不利于保证执行的效率。

（2）作为一种商业计算，为提高服务收益，在云计算任务优化调度问题上，同样要考虑其经济因素。在给定调度的任务集和所需的资源后，云计算任务调度问题研究的目的是寻找一种合适的调度策略，基于该策略，云计算系统将待调度的任务请求分别指派给不同的资源，实现大量的任务在可用的资源之间的合理分配与高效执行。

由此可见，云计算任务调度是一个NP完全问题，针对于此，已有很多相关工作是使用博弈论理论来解决分布式并行计算环境下的资源调度问题，同时，研究人员提出了多种方法来逼近求得该策略的最优解。

以上关于云环境中任务调度研究的工作，虽然在不同的云计算环境中进行了具有针对性的调度策略设计，但仍存在一些问题：

（1）计算的资源需要统一的调度和管理，以便于更好地分配给用户的应用任务，而完善的管理架构需要具备灵活性以及适应云计算中任务动态变化特点的可扩展性。相关的研究工作中，云计算系统中的资源管理、任务调度管理的框架灵活性较弱，缺乏一定的扩展性。

（2）云计算系统中的资源管理需要支持多目标优化，同时，调度策略要综合考虑用户的QoS要求、云服务提供商的资源利用率、服务收益等因素，并且策略需易于实现。相关研究工作考虑的优化目标大多比较简单，缺乏综合性考虑。

（3）云计算系统任务调度策略需要根据任务的动态性特点而灵活易执行。目前已有的相关研究工作关注的问题，多是在几个给定的云服务提供商的组合环境下的任务调度问题，提出的任务优化调度策略没有考虑公平性，在任务调度时缺乏灵活性。

在云计算系统中，在满足用户的要求的同时，云服务提供商的利益同样值得关注，系统中资源的有效分配、任务的高效调度是提高服务提供商效益的关键。

计算服务逐渐成为运营商的计算应用首要的选择方式，目前，谷歌、亚马逊以及微软的云用户数量不断增长。用户任务队列的长度取决于系统的服务响应时间，而资源的分配、系统的负载状况又在不同程度上对响应时间产生影响。考虑服务提供商的收益最大化以及用户的服务质量需求，如何进行资源的合理分配，提高系统的性能，是当前云计算服务亟待解决的问题。