基于任务完成时间的自适应算法性能测试结果

（1）实验环境设置

实验中网络传输率设为1 Gbps，应用3台服务器，通过Hadoop框架执行，每一个任务都需要3个map任务完成，并利用Hadoop的插件，控制分配给系统中每个任务的map时隙数量，从而控制资源的分配。

（2）实验结果分析

图5-8给出了GP算法循环执行的变化情况。

图5-8　GP算法执行情况

在GP算法的控制下，通过图5-8的收敛过程可知，对于Ⅰ类、Ⅱ类、Ⅲ类最晚完成时间的任务执行情况，开始速率较慢，后期趋于一个稳定值，因此算法均在一定迭代次数后能得到一个最优解，并且选择适当的虚拟机的资源量初始值，可以缩短迭代过程。

选取不同类型、不同规模的调度问题，比较算法迭代次数，结果如表5-4～表5-7所示。

表5-4　Ⅰ类最晚完成时间迭代次数

表5-5　Ⅱ类最晚完成时间迭代次数

表5-6　Ⅲ类最晚完成时间迭代次数

表5-7　GP算法平均迭代次数比较

由表5-4～表5-7可知，GP算法可以在有限次迭代中最终求得问题的最优解。

将 GP算法分别与公平调度（Fair Schedule）［102］、随机调度（Random Schedule）［103］、最早-完成时间优先（Earliest Deadline First）［104］三种调度算法比较。四种算法在延迟等待时间上进行比较的结果如图5-9～图5-11所示。

(www.xing528.com)

图5-9　不同任务类型延迟分布情况

公平调度、随机调度、最早-完成时间优先，三种调度算法特点如下：

① 公平调度中每个任务分得相同的资源，保证资源分配的公平性；

② 随机调度中资源随机分配给每个任务使用；

③ 最早-完成时间优先调度中，虚拟机是根据任务的完成时间的顺序，依次获得相应的资源。

首先，120个任务中至少50个是Ⅰ类最晚完成时间，其余任务随机为Ⅱ类最晚完成时间和Ⅲ类最晚完成时间，针对以上设置执行四个调度算法。

在图5-9中，当任务数量为50时，四种算法的延迟情况：应用GP算法时出现的最坏情况的延迟为55ms时，此时，公平调度FS算法延迟为76ms，随机调度RS算法和最早-完成时间优先调度EDF算法对应最坏执行情况下的延迟为87ms。在任务数量逐渐增加的过程中，GP算法延迟波动较小，其他三种算法波动较大，并随着任务数量增加，延迟增加幅度变大。实验结果表明，应用GP调度算法的任务总是接近最晚完成时间完成，其能够在任务完成中合理考虑任务的三种分类，延迟较小，而其他算法具有不同程度的较大延迟。

比较四种算法的任务优先级与延迟情况，如图5-10所示。

图5-10　不同优先级任务延迟分布情况

在图5-10中，对于所有任务设置相同的执行时间为55ms，任务类型为Ⅱ类最晚完成时间，任务的优先级为0～200。

应用GP算法时出现的最坏情况延迟为30ms时，公平调度FS算法、随机调度RS算法和最早-完成时间优先调度EDF算法对应的延迟均高于GP算法运行时的延迟30ms。此时，在四种算法运行的整个过程中，GP算法由于对于任务进行资源分类调度，任务延迟减少幅度较大，并且对于任务执行造成的影响较其他三种算法减弱。

设置任务的数量从50增加到150，比较不同调度算法总的延迟情况，如图5-11所示。其中，至少1/3任务是Ⅰ类最晚完成时间，而其余2/3任务随机分配为Ⅱ类最晚完成时间和Ⅲ类最晚完成时间。

图5-11　不同优先级任务总延迟分布情况

由图5-11可知，四种算法的延迟变化趋势一致，但是当任务被执行时，应用GP算法时虽然延迟增加，但增加幅度较平缓，而公平调度FS算法、随机调度RS算法和最早-完成时间优先调度EDF算法对应的任务执行时的延迟不断扩大。正是由于GP算法具有任务完成时间适应的机制，才能够尽可能满足任务执行的时间、资源需求，降低任务执行延迟。

实验结果表明，对于一组提交到Hadoop框架的任务，由于GP算法具有任务完成时间自适应性，因此，相较于其他三种调度算法，在最晚完成时间内，GP算法调度完成高优先级任务的数量多于其他调度算法；对于多种类型任务的执行实验结果表明，GP算法总的累计延迟时间小于其他调度算法。