基于QoS的云任务调度算法研究

房超　黄春梅

摘  要：随着云计算的发展，越来越多的人开始使用“云”来处理他们的业务，这对公有云平台提出了一些重要挑战：如何让公有云平台在不断激增的云业务模式下，既能保证云用户的服务满意度，同时也能稳步提高云服务商（Cloud Service Providers）的收益。首先建立了任务调度算法以及QoS需求约束等相关模型，然后将QoS（Quality of Service）需求约束分别引入到三种传统任务调度算法（FCFS（RR）、MinMin和MaxMin算法）中对其进行改进，接着将改进后的算法与传统任务调度算法之间进行比较，通过选取在任务完成度、任务最终完成时间（MakeSpan）、任务平均执行时间（这些影响用户的服务满意度），以及云服务商总收益等方面的指标表现，最后确定了一个较好的改进MinMin任务调度算法（I-MinMin算法）。实验通过CloudSim进行模拟，并采用了现有的阿里云ECS云服务器中的虚拟机实例相关数据。结果表明：在任务量不断增加的情况下，I-MinMin算法在用户的服务满意度各方面，以及云服务商总收益等指标表现上要更优于其他算法，更好地实现了用户和云服务商的双重利益。

关键词：云计算;任务调度算法;QoS需求;用户服务满意度;云服务商总收益

中图分类号：TP391     文献标识码：A

Abstract：With the development of cloud computing，more and more people begin to use "cloud" to manage their business，which poses some important challenges for public cloud platforms.For example，how to make public cloud platforms，under the ever-growing cloud business model，to ensure the service satisfaction of cloud users and steady improvement of the revenue of cloud service providers （Cloud Service Providers）.Relevant models such as task scheduling algorithms and QoS requirement constraints were established first.Then the QoS （Quality of Service） requirement constraints were introduced into three traditional task scheduling algorithms （FCFS （RR），MinMin，and MaxMin algorithms） for improvement.Then this paper compares the improved algorithm with traditional task scheduling algorithm.The three improved algorithms are compared with the original algorithms in terms of task completion，task final completion time （MakeSpan），average task execution time （these affect user service satisfaction），and the total revenue of cloud service providers' performance.Lastly，a better improved MinMin task scheduling algorithm （I-MinMin algorithm） was determined.The experiment was simulated by CloudSim，and the relevant data of the virtual machine instance in the existing Alibaba Cloud ECS cloud server was used.The results show that the I-MinMin algorithm outperforms other algorithms in terms of user service satisfaction and the total revenue of cloud service providers in the context of increasing tasks，therefore better achieve the dual interest of both users and cloud service providers.

Keywords：cloud computing;task scheduling algorithm;QoS demand;user service satisfaction;total profits of  cloud service providers

1   引言（Introduction）

在公有云中，云服務商利用内部IT资源池构建成了一个可以处理各种服务请求的云数据中心，当用户提交服务请求时，这些请求首先会被数据中心代理所接收，然后代理会根据一些资源调度算法将请求分发至数据中心的每一台虚拟机中执行。通常，用户的服务请求会被解析成各类云任务（以下简称任务），用户服务请求的处理过程相当于为任务选择合适的虚拟机的过程，数据中心需要制定合适的任务调度算法来处理各种任务。

一般，任务调度算法需要考虑到每一个任务的各项QoS需求[1]，以及每一台虚拟机的资源使用情况，以此来制定合理的任务调度算法，实现任务的合理分配以及资源的高效利用。当任务数较少时，数据中心的资源量足够满足任务的各项QoS需求（比如用户的价格需求等），因此，使用一些传统任务调度算法即可实现这些目标;但当任务数不断增加时，如果继续使用原来的任务调度算法，将有可能导致任务延迟，数据中心资源利用率降低等问题，最终使得一些任务调度不能满足他们自身的QoS需求，用户的服务满意度大大降低，同时也使得云服务商获取不到用户所支付的报酬。长此以往，云服务商将不能获得足够的收益以支撑整个云数据中心的持续运行。因此，设计一个可以应对任务请求不断增加情况下的高效任务调度算法，对于提高用户的服务满意度以及增加云服务商的收益至关重要。

2   相关工作（Related work）

在云计算中，任务可以分为独立任务、关联任务和混合任务，本文研究的主要是独立任务的调度算法，因此，只对独立任务的调度算法做相关介绍。

关于独立任务调度算法，可以将其分为传统任务调度算法和启发式的任务调度算法。一些传统的任务调度算法，例如先进先出（FIFO）算法[2]、轮转调度（RR）算法、MinMin算法[3]、MaxMin算法和Sufferage算法等，这些算法一般比较简单且执行速度较快。FIFO算法通常与轮转调度算法相结合（FIFO（RR）算法）以实现任务的合理调度，通过先进先出的方式从提交的任务队列中选择任务，然后按照轮转的方式将任务分配到每一台虚拟机中，虽然该算法有一定的负载均衡性，但它却忽略了任务和虚拟机的异构特性，并不适合现在的云计算异构环境;MinMin算法属于批调度算法，同时它也是一种实现简单，执行时间快的算法，该算法的思想是最先映射任务长度小的任务，并且映射到计算最快的虚拟机上，但这种算法容易导致负载大多集中在能力较强的资源节点上，使得资源负载极度不均衡;MaxMin算法与MinMin算法类似，首先都需要计算每一任务在所有计算节点上的最早完成时间，不同的是，MaxMin算法优先调度大任务，任务到资源的映射是选择最早完成时间最大的任务映射到所对应的计算节点上，但会增加任务的平均完成时间。一些启发式的任务调度算法，如：粒子群算法（PSO）[4]、蚁群算法（ACO）[5]、遗传算法GA（Genetic Algorithm）和博弈论算法等[6，7]。这些启发式调度算法虽然在某些方面比传统任务调度算法具有更好的性能[8]，但算法实现起来较复杂，且实用性不强，有时在某些方面反而不如改进的传统任务调度算法更加简单、有效。因此，这里不做过多阐述，只对一些改进的传统任务调度算法作相关介绍。

关于改进的传统任务调度算法，本文主要从用户服务满意度以及云服务商收益这两方面进行介绍。在用户服务满意度方面，大多数学者都是基于QoS需求来进行改进的，比如，何晓珊等[9]基于QoS修改了MinMin调度算法，根据用户QoS需求对系统吞吐率进行优化，获得了一定的性能改进。孙大为等[10]根据用户应用偏好对QoS中的用户效用进行量化，并结合免疫克隆算法，给出了多维QoS优化的适应度函数，改进了算法的收敛能力，提高了算法的性能;在增加云服务商收益方面。Buyya等[11]人提出基于经济模型资源调度方法，通过SLA（Service Leveal Aggent）资源分配器来实现资源提供者与资源使用者之间的协商，实现资源的优化分配。Deelman等[12]利用亚马孙收费标准和一个真实的天文学应用，仿真实验了不同执行方法和资源提供方案下的性价比。Assuncao等[13]人研究了企业组织利用云服务提供商基础设施扩展企业本地基础设施的收益問题。Deepak等[14]人提出了对于云缓存查询服务的一个新颖定价需求方案设计，实现利润的最大化。Hamid等[15]人提出一种多QoS利润感知调度算法（MQ-PAS），该算法通过考虑每个作业的可用预算来定义任务优先级，从而提高供应商的利润。在将用户服务满意度和云服务商收益相结合方面，一种比较成熟的解决方案是面向云计算的工作流，简称“云工作流”，在这方面，柴学智等人[16]对云工作流的产生、发展，以及在云计算中的独特优势进行了详细的阐述。武丽芬等[17]人提出满足截止时间和预算的双QoS约束调度算法（DBWS），该算法将工作流调度划分为任务选择和资源选择两个阶段，并设计了时间质量和代价质量两个均衡因素，同类算法在调度成功率与同步满足QoS约束上进行了比较。方伯芃等[18]人从用户的QoS和云服务商的运营成本双方利益出发，建立了一个面向QoS与成本感知的云工作流调度模型，并提出了一种基于任务序列划分的两段式编码遗传算法，该算法以租户流程租约和虚拟机实例负载为约束，通过两段式交叉、编译算子进行种群的迭代进化，以实现对云工作流服务费用与云资源使用成本的调度优化。

3   问题模型（Problem models）

为便于分析，本文规定每台虚拟机每次只能执行一个任务，多台虚拟机可以同时执行，且任务一旦被执行将不能被抢占，直到任务执行完成，虚拟机才可执行下一个任务。本文首先建立了云任务、虚拟机以及主机等基本模型（或公式）;然后建立了调度算法相关模型（或公式）;最后是调度目标模型（或公式）。此外，本文模型中所用到的变量i、j和k分别表示任务标号、虚拟机标号和主机标号，它们均满足0≤i≤m-1、0≤j≤n-1及0≤k≤s，其中m、n和s分别表示任务总数、虚拟机总数和主机总数，由于模型（或公式）较多，本文以列表的形式展示，如表1—表3所示。

QoSconst表示QoS需求约束，包括虚拟机vj执行任务ti所产生的预计执行收益不能超过该任务的最高可接受价格，以及任务ti在虚拟机vj上的预计完成时间不能超过该任务的截止时间 （16）

所有任务在执行完成后，未违反QoS需求约束（QoSconst）的任务将会产生云服务商收益，因此，记录这些未违约任务的数量可以很好地反应出云服务商总收益的变化。

为了提高用户的服务满意度，算法应该在任务量不断增加的过程中，始终保持较高的任务完成度TCR（Task Completion Rate）、较低的任务最终完成时间（MakeSpan）以及任务平均执行时间ATET（Average Task Execution Time）;服务商方面，主要选择的是保持云服务商的总收益Profitcsp持续增加，另外，TDR（Task Default Rate）用于分析算法的QoS违约率变化。

4   算法与实验（Algorithms and experiments）

本文通过在三种传统任务调度算法中嵌入QoS需求约束来对其进行改进，目的是为了寻找一种具有较好的用户服务满意度，以及云服务商总收益的改进算法。三种传统任务调度算法分别是FCFS（RR）算法、MinMin算法及MaxMin算法，改进后的算法分别称为I-FCFS（RR）算法、I-MinMin算法及I-MaxMin算法。下面开始对三种改进版传统任务调度算法进行说明与实验。

4.1   对传统任务调度算法的改进

本文对传统任务调度算法不做过多介绍，只对改进版的传统任务调度算法进行相关分析，它们都是通过在原有算法中嵌入QoS需求约束进行的，如表4—表6所示。

上述三种改进版传统任务调度算法在为任务选择合适的虚拟机过程中，每一步都要经过QoS需求的层层约束。在满足QoS需求约束的情况下，任务会被放置到合适的虚拟机中;在不满足QoS需求约束的情况下，任务会被取消。

4.2   实验相关参数

本文试验采用CloudSim进行模拟，总共创建了五台主机、20台虚拟机。虚拟机的属性数据采用的是阿里云服务器ECS中真实实例的数据。另外，本文将0—3600个任务以300个为单位平均分成了12组，作为不同任务量的任务集。实验过程中的相关参数如表7所示。

表7中虚拟机的数据采用的是阿里云云服务器ECS中共享型实例的标准数据。在阿里云服务器ECS定价界面中选择华东2地域，实例价格信息选择入门级用户、经典网络、非Windows系统，以及优化的I/O即可找到这些虚拟机实例的相关数据信息，如图1所示。

依照阿里云帮助文档中关于云服务器ECS的共享型实例说明，本文共选取了ecs.xn4.small、ecs.n4.small、ecs.xn4.large、ecs.mn4.small及ecs.mn4.large四种不同类型的实例（虚拟机），这些实例使用的都是2.5GHz主频的Intel?Xeon?E5-2682 v4（Broadwell）处理器，带宽都为0.5Gbit/s（512Mb/s），由此可以得到这些实例在正常情况下的Cpu最高主频为2.5GHz。因此本文假设这五种不同类型虚拟机的主频分别拥有0.5GHz、1GHz、1.5GHz、2GHz和2.5GHz这五种主频，且所有Cpu的每个机器周期都等于四个时钟周期，每条指令等于三个机器周期，则该Cpu的时钟周期数（每条指令执行的时钟周期个数）为3*4=12个，最终由公式：Cpu的运算能力=主频/时钟周期数，可以得到了表7中五种类型虚拟机的Cpu运算能力。

本文将0—3600个任务按照每300个为递增的顺序来模拟不断增加的云任务集，总共分成12份;将任务的长度（指令数）以10000百万为单位平均分成了10份;将截止时间以1小时为单位平均分成了10份;将最高可接受价格以0.01元为单位平均分成了10份。使用CloudSim进行模拟的过程大体如下：

（1）初始化CloudSim，创建CloudinformationSerVice服务;

（2）创建数据中心（包含创建主机的过程）;

（3）创建数据中心代理;

（4）创建虚拟机，并提交给数据中心代理;

（5）创建任务，并提交到数据中心代理;

（6）开始模拟;

（7）停止模拟;

（8）输出模拟结果。

下面将对实验的结果进行分析。

4.3   改进版传统任务调度算法实验结果与分析

在对实验结果进行分析时，本文选取了影响用户服务满意度和云服务商收益的四种指标，以及QoS违约率、未违约任务数等，并使用折线图的方式比较了六种任务调度算法在12种不同任务集中的表现及变化，如图2、图3和图4所示。

（a）任务完成度（TCR）

（a）Task completion rate

（b）任务最终完成时间（MakeSpan）

（b）Task final completion time

（c）任務平均执行时间（ATET）

（c）Average rask execution time

（d）云服务商总收益（Profitcsp）

（d）Cloud service provider's total profit

算法的QoS违约率和未违约任务数统计如图3和图4所示。

从以上各图可以看出：在任务量不断增加的过程中，三种传统任务调度算法（FCFS（RR）、MinMin和MaxMin算法）始终保持100%的任务完成度。这是由于传统任务调度算法在任务调度时，没有考虑到用户提交的任务中所要求的各项QoS需求，只是笼统的将任务全部分配到虚拟机当中。因此，这种方法虽然可以将所有任务都执行完成，但却造成了大量任务违约，从图3中也可以看出它们的QoS违约率基本处于增加的状态，用户将不会为这些违约的任务支付任何费用，这种情况会在任务不断增多的情况下愈发明显。除FCFS（RR）算法外，MinMin和MaxMin算法的任务最终完成时间（MakeSpan）一直处于稳步上升的趋势，但又由于任务的最终完成数也是一直增加的，故任务平均完成时间取决于他们各自的增加幅度。而这三种算法的服务商总收益前期一直处于上升的趋势，后期则趋于平稳。这是由于此时的数据中心已经达到了任务处理的“饱和”上限，系统已经无法处理更多的任务，从图2（b）中也可看出此点。而随着可以处理的任务达到顶峰，服务商总收益也将获得最高值（图4中未违约任务趋于平衡）。相对于传统任务调度算法，三种改进的任务调度算法（I-FCFS（RR）、I-MinMin和I-MaxMin算法）由于考虑了用户的QoS需求，即对任务进行了筛选，避免了用户QoS需求违约（如图3它们的QoS违约率始终为0），因此它们的任务完成度取决于任务的最终完成数与所有提交的任务数比值，从图2（a）可以看出它们的任务完成度一直处于下降的趋势。在前一小段，他们的任务最终完成时间（MakeSpan）处于小步上升的状态，云服务商的总收益不断增加（从图4中可以看出），后期大半段，它们依旧会出现“饱和”的现象，其任务最终完成时间与云服务商总收益基本保持平衡状态。