花嵘 张友裕

摘  要： 基于云任务的动态延迟到达，到达时间具有随机性，进行任务分配到虚拟机执行的仿真模拟。仿真任务是基于排队论的指数分布到达方式，虚拟机的处理速度存在差异。实验思路是高优先级尽可能早的执行，同时避免低优先级任务饿死的思路，并定义了一个消费量作为对比点，对比基于一定等待的调度与贪心调度的差异。通过设置动态等待时间的设置来进行实验，同时测试多组输入数据减少样本的偶然性。对比分析各种数据，验证实验的有效性。并通过CloudSim进行云仿真实验模拟。

关键词： 云计算;任务调度;延迟任务

中图分类号： TP302.1    文献标识码： A    DOI：10.3969/j.issn.1003-6970.2019.10.031

本文著录格式：花嵘，张友裕. 基于延迟任务云资源调度方法的研究[J]. 软件，2019，40（10）：139141+190

Research on Cloud Resource Scheduling Method Based on Delayed Task

HUA Rong， ZHANG You-yu

（College of Computer Science and Engineering， Shandong University of Science and Technology， Qingdao 266510， China）

【Abstract】： Dynamic delay arrival based on cloud tasks， random arrival time， simulation of task assignment to virtual machine execution. The simulation task is based on the arrival of the exponential distribution of the queuing theory， and the processing speed of the virtual machine is different. The experimental idea is to execute the high priority as early as possible， while avoiding the idea of starvation of low priority tasks， and define a consumption as a comparison point， comparing the difference between scheduling based on certain waiting and greedy scheduling. Experiments are performed by setting the dynamic wait time setting， while testing multiple sets of input data reduces the contingency of the sample. Compare and analyze various data to verify the effectiveness of the experiment. And cloud simulation experiment simulation through CloudSim.

【Key words】： Cloud computing; Task scheduling; Delayed task

0  引言

云计算是通过网络利用远程服务器上的资源进行计算，资源量、运算速度可以几十倍上百倍的大于本地计算机最后把结果收集起来，还可以作为一些网站的载体等作用。云计算在现代社会中占据着越来越重要的地位，各种互联网大企业也都在发展各种云业务，包括谷歌、亚马逊、阿里、腾讯等。云资源的使用能减少企业对实体资源投入的花销，同时，也能减少企业物理机，服务器等的迭代更新，也能减少这部分的花销。由于云的广泛使用，关于云上的资源调度，任务调度就成为大家研究的课题之一[10-12]。

云资源调度主要包括两个方面的研究方向[8]。第一种，是基于云任務与运算单元的负载均衡，即把所有任务均匀的分配给各个运算单元，兼顾各运算单元的能力（快处理器尽可能分配更多的资源），以及任务之前的依赖关系，在每一时间尽可能的把所有可用处理器都调用起来。第二种是基于最小花费的资源调度，通过定义资源的单位价值，资源使用量与单位价值乘积，然后各种资源再求和，得到总的资源消耗量[4]。

1  问题提出

现实生活中，云计算资源调度不会按照给定的时间，有序的到来，充满着许多的随机性。我们需要考虑这些随机性的存在，设计出适合动态到达的模型[9]。同时，对该问题需要有一定的衡量标准，我们定义一个消耗量作为判断该算法优劣程度的标准，该算法需要均衡考虑等待时间与执行时间，设计出一个尽可能小的消耗量的算法。

基于此本文的出发点是任务到达后，基于任务优先级等待一定时间，尽可能把执行速度快的处理器分配给优先级更高的任务，让高优先级任务能更早执行更早完成，以此达到更低的消耗量（基于优先级的一个定义量）[13]。同时，即使是低优先级任务也是能够执行的，使任务尽可能不至于等待太长时间。本文的工作目标是确保较高优先级任务能够更快完成，同时兼顾低优先级任务能够完成，不至于发生“饥饿”[6]。

2  具体实现

2.1  参量设置

通过排队论指数分布进行任务到达的随机取样，确保任务的随机性[7]。不过，进行对比实验时，会事先把任务的到达时间预先存取到一个文件内，确保两个对比实验的数据是相同的[3]。

连续的两个任务到达时间间隔为

interval=，x为[0，1]内的随机数

（1）

一般设置为0.05，0.1，0.15等值（值越小间隔越大）。仿真时，先产生一组完整的值，数量为任务的个数，存入一个文本文件内。

定义若干个虚拟机vm（执行单元，用于执行任务），虚拟机的数量为。确保这若干个虚拟机是异构的，要求处理速度要不同，同时执行速度相差不要特别小。

本文定义的cost考虑两部分来源，等待时长与执行时长，假设等待时长的权重为A，执行时长的权重为B，则A+B=1。则cost为

（2）

其中，N为总的任务个数，为任务完成时间，为任务开始执行时，为任务到达时间，P为任务优先级，取值为1-10的整数，cost为这若干个任务的单独花费的总和，三个时间存在如下的关系，

， （3）

执行l为当前任务的长度，v为该任务选择的虚拟机的执行速度（v的可能取值个数为虚拟机的   数量）。

等待时间B*P后的分数因子为（0，1]的值，为了与等待时间相差不大，执行时间A*P后的因子也为该取值范围的值，在定义cost时最后乘上1%这个值，是为了尽可能使两者的值在一个数量级。以此确保计算的cost能相对合理的衡量任务分配的花销问题。也就是说，该值的设置应该是与整体的任务长度以及运算单元的执行速度是相关的。

2.2  调度设计

本文的调度算法是动态延迟等待再分配，通过设定一个含m个元素的队列用来暂存数据，由于分配时是把队列内的所有任务立刻进行分配，所以要确保队列的大小需要小于虚拟机的数量（）。设置一个阈值时间来防止等待时间过长[5]。

（1）记录第一个到达队列内的时间（该值大小为此任务的，同一批次分配内的任务都以此时间作为判断），队列内的任务最大等待时间为。对之后到来的任务会进行一次判断，当任務的优先级高于某值，且空闲虚拟机内有执行速度较快的虚拟机时，进行直接分配，不加入待执行任务队列，当不满足这种情况时，把任务加入待执行队列。应当与到达第一个任务的优先级相关，任务优先级越低等待时间偏向于越长，则此次队列内任务的最晚执行时间为，该执行时间发生的情况为，在阈值时间内，到达的任务个数是小于m的，在规定时间内没有达到足够的任务，直接进行了分配，定义当前到达的任务数量为a个，我们假定所有的任务不会分在同一虚拟机上，即为把a个任务分配给个虚拟机，第一个任务有种选择，第二个任务选择少一，以此类推，则对当前队列内任务可行的分配方案为种，计算所有的cost，并把消费最低的cost作为分配执行方案。

（2）还有一种情形是在截止时间前，已经到达了m个任务。则会在第m个任务到达时，立即开始分配执行任务，则此时的时间是小于的，开始执行的时间即为第m个任务的到达时间。则在这种情况下可能的分配方案个数共为，同样计算所有cost，并从中选择最小值作为最终的执行方案。

（3）当把队列内的任务清空分配之后，会把下一次到达的任务的再次作为新的，并重复上述过程，直到所有任务执行完成。

3  实验仿真

设置虚拟机的个数为5个，5个虚拟机的执行速度分别为100，125，150，175，200，任务的总个数N为30，任务的大小为5000到15000内的随机数，另外，本文假定A=0.7，B=0.3，强调执行时间重于等待时间的量。

仿真实验的是在CloudSim上面测试的[1-2]，该应用是基于Java语言的。我们做的对比实验是，在任务到达的时刻就进行基于贪心分配的计算，高优先级任务分给快一些的虚拟机，低优先级的任务分配较慢的虚拟机，并用相同的输入数据计算两组实验的值，进行对比大小。为保证两组输入是完全一样的，我们先采用要求的随机数的方法产生一组值，具体的数据包括任务的优先级，任务的长度，任务的到达时间，基于3个进行实验，值分别为0.05，0.1，0.15，以此来设置任务到达的时间间隔进行对比实验，每次计算涉及到3个量，30组数，共90个数据，并把该值存入一个文本文件内，执行时先从文本文件内读入数据。在实验之前，先进行简单的计算，我们以最后一个任务的到达时间作为对比量，以此来删除误差较大的量，尽量把到达的时间控制在一定的范围，消除偶然性，同时进行多组实验，排除特殊样本可能存在不合理性的可能。

（1）按上面要求设置的第一组实验，任务到达较快，系数为0.15，取最晚到达任务的时间在170-230的范围内，在贪心情况下，除了每个虚拟机分配的第一个任务，均需要等待一定时间才能执行，也就是说大概25个任务需要进行等待操作，实验结果是，该组实验下优化效果尤为明显。cost值的差值一般能达到7到10左右。

（2）在第一组的基础上，修改指数分布的系数为0.1，取最晚到达任务的时间在250-350的范围内，使任务的到达时间间隔变大，需要等待的任务稍微变少，同时，两组实验cost的差值也变小了，大概平均只能在2到3的水平。

（3）在上两组的基础上，修改指数分布的系数为0.05，取最晚到达任务的时间在520-680的范围内，继续增大任务到达的时间间隔，使任务几乎都能在到达时，都能有空闲的虚拟机，在该组实验下，不仅无优化，反而比基于贪心的对比实验还要差4-6的水平。

（4）在基于（1），（2）的实验结果基础上，加做一组指数分布系数为0.125，取最晚到达任务的时间在200-280的范围内，该组实验结果在（1），（2）的中间水平，有优化效果，cost差值大概为4-6，效果在（1）与（2）的中间水平。

4  结果分析

由于样本的差异性，可能存在一些效果更好，和一些效果一般的情况。但总的来说，效果较为理想。在任务到达的速度快过任务执行的速度时，比较极端的情况是除了第一组值，其他任务的执行均需等待，在趋向于这种情况时，优化效果较好，并随着任务到达速度的减慢（指数分布系数变小，间隔变大），优化效果逐渐变差，甚至当任务到达特别慢时，反而不如另一组实验。原因是在这种情况下，每个任务到达时，都有空闲虚拟机，任务都能直接执行，进行一定的等待，反而是不明智的。

参考文献

[1]Rodrigo N. Calheiros， Rajiv Ranjan， Anton Beloglazov， Cesar A. F. De Rose， and Rajkumar Buyya. CloudSim： A Toolkit for Modeling and Simulation of Cloud Computing Environments and Evaluation of Resource Provisioning Algorithms. Software： Practice and Experience （SPE）[J]， 2011， 41： 23-50.

[2]周婉， 王移芝. 基于卡尔曼预测器的云计算资源调度研究[J]. 软件， 2015， 36（9）： 12-15.

[3]赵琴. 排队论在车间调度中的研究与应用[D]. 兰州： 兰州理工大学. 2013： 9-28.

[4]冯田. 基于sufferage的动态出租车拼车调度算法. 电脑知识与技术[J]. 2011（7）： 7019-7023.

[5]周平， 殷波， 邱雪松， 等. 面向服务可靠性的云资源调度方法. 电子学报[J]. 2019（5）： 1036-1043.

[6]黄坤， 吴俊. Gang调度在云计算任务迁移和饥饿处理中的性能和成本评估[J]. 华中师范大学学报（自然科学版）， 2013（5）： 621-625+631.

[7]姜海燕. 基于指数分布参数的滚动轴承故障特征提取方法. 自动化技术与应用[J]， 2019（3）： 27-30+42.

[8]武凯， 勾学荣， 朱永刚. 云计算资源管理浅析[J]. 软件， 2015， 36（2）： 97-101.

[9]熊舸， 张煜， 杨勇. 基于服务量的异构车载网络资源调度算法[J]. 软件， 2015， 36（5）： 54-60.

[10]刘鹏. 云计算[M]. 第三版. 北京： 电子工业出版社， 2016： 1-12.

[11]姜福成. 云计算的基础结构设计和云应用服务[J]. 软件， 2014， 35（7）： 97-102.

[12]王曉艳. 基于云计算的数据中心建设探讨[J]. 软件， 2014， 35（2）： 129-130.

[13]詹文涛， 艾中良， 刘忠麟， 等. 一种基于YARN的高优先级作业调度实现方案[J]. 软件， 2016（3）： 84-88.