基于决策树分类的云作业调度算法研究与实现

强 彦，卢军佐，裴 博

（太原理工大学 计算机科学与技术学院，太原030024）

云计算以其高效的服务而著称，是计算机界目前研究的热点［1］。云计算中的虚拟技术、作业调度技术和存储技术是几个重要的研究内容。特别是云的作业调度技术，因为随着云环境下用户数量的增加、服务类别的复杂和作业规模的不断庞大，如何通过改进作业的调度来保证云服务的质量和性能不受影响已成为大家的关注点［2］。例如，当不同种类、大小的作业同时进入服务平台，可能会造成作业调度算法的调度效率低下，造成计算资源的浪费，导致用户满意度降低。笔者通过对传统云调度算法的研究，提出将决策树分类算法引入云调度算法中，实现对传统调度算法的改进，改进后的调度算法对作业进行分类，达到同类作业进入同一个队列接受调度，有效提高了作业执行效率。

1 决策树分类算法

分类是数据挖掘的一种重要手段，能够为一定的工程应用提供决策支持，特别是决策树分类算法是应用最广泛的逻辑方法之一［3］。它能够通过训练数据集的学习来产生相应的决策规则树，并且通过信息增益计算，得到每个属性的重要程度，加快分类速度。目前已成功地应用于Web智能、金融分析、天文学和分子生物学等领域。常用的决策树算法有ID3、C4.5等［4］。其中 C4.5在ID3基础上做出了一些改进，因此本文采用C4.5算法来进行云作业分类［5］。

C4.5算法描述如下。

输入：训练样本samples、候选属性集合attribute list、当前样本T；

输出：一棵决策树；

Step1：创建根节点N；

Step2：如果T都属于同一类C，则返回N为叶节点，标记为类C；

Step3：如果attribute list为空或T中所剩的样本数少于某给定值，则返回N为叶节点，并标记N为T中出现最多的类；

Step4：对于每一个作业属性，计算信息增益率；

Step5：N 的测试属性test.attribute＝attribute list具有最高信息增益率的属性；

Step6：如果测试属性为连续型则找到该属性的分割阈值；

Step7：对于每一个新的叶子节点，如果该叶子节点对应的样本子集T′为空，则分裂此叶子节点生成新叶子节点，并将其标记为T中出现最多的类；否则在该叶子节点上执行C4.5form tree（T′，T′.attribute list），继续对它分裂；

Step8：计算每个节点的分类错误，进行树剪枝。

2 决策树分类作业调度

2.1 网络训练

选取常见的几种不同类型的云作业，分别为WordCount：计算文本里每个词出现的频率；URLGet：模仿网页爬虫的抓取网页行为；CPUActivity：对输入的每个key-value对进行一次计算量巨大的数值计算，如大整数乘法。每种类型的作业的大小不同，因此所占用资源也不同［6］。得到的模拟训练集如表1所示。其中class代表分类的状态，标号为作业的首字母。

表1 训练样本集

选择好训练集后，用算法对作业进行训练，得到训练模型，方便以后利用决策树对作业进行分类。得到的决策树如图1所示。

图1 决策树

从图1中可以看出由C4.5生成决策树，进行的信息增益得到了每个属性的重要程度，信息增益中选择最重要的属性作为分裂属性，其中比较重要的是CPU和Memory，由于其他两个属性对分类的贡献较小，因此在决策树中没有体现。如图1中所示，决策树中存在如下两条规则［7］。

规则1：如果CPU所占资源大于40，那么这些作业划分为一类，否则划分为另外一类；

规则2：对于上面划分好的类，按照Memory划分，如果所占内存大于50则划分为一类，如果所占内存小于等于50则划分为一类。

2.2 决策树分类作业调度

决策树分类作业调度算法的中心思想是：利用决策树算法对训练集进行训练，得到分类模型，利用分类模型对作业进行分类，使得相同的作业进入相同队列，最后对作业进行调度［8］。不仅可以预测每个作业执行时间而且可以使相关作业得到有序执行。算法描述如下。

输入：作业训练集、测试集；

输出：作业分类、调度结果；

Step1：利用上述决策树C4.5算法进行信息增益，创建决策树，训练样本，建立分类模型；信息增益的方法为

其中D为每个属性的值，j＝1，…，n；

Step2：利用Step1创建的分类模型对作业集进行分类；

Step3：预测相应的作业的类型、执行时间，然后按照时间的先后顺序和执行时间的长短，对作业进行分类执行；

Step4：输出作业的实际执行时间。

作业调度模型如图2所示。

图2 作业调度模型

3 实验与分析

本文采用8个节点的集群来评估该算法，其中一个为主控节点，其他为辅助节点［9］。每个节点的配置为Inter双核，2.4Hz，250G硬盘和2G内存，这些节点通过千兆交换机相连。每个节点装有Linux系统和Hadoop平台。实验中Hadoop中参数设置如表2所示。

表2 Hadoop参数设置

实验采取的作业如3.1节所示，模拟不同类型的作业，利用上述决策树调度算法对作业进行调度，分别统计每个作业的类划分情况、作业执行时间、作业等待时间，分析算法效率。

3.1 算法的可行性

模拟20个3种类型的作业进入Hadoop环境［10］后，会按照决策树调度算法将作业分为3个不同的类，来证明算法的可行性。为体现这8个作业的分类状况，本文采用FastMap技术［11］将作业的属性映射到2维上。其结果如图3所示。

图3 作业分类结果

从图3可以看出20个作业进入环境后被分为了3类，在图中分别用不同标识标注，经验证分类的结果和模拟的作业类型完全一致，从而验证了算法的可行性。

3.2 算法的效率验证

模拟8个不同种类的作业，进入Hadoop环境，分别配置Hadoop中默认的调度算法和基于决策树分类的作业调度算法，用2中算法分别对8个作业进行处理，得到这两种算法的作业运行时间和作业等待时间，并比较两种算法的结果，验证算法的效率。

图4为两种算法的作业调度结果，其中图4－a为Hadoop默认的调度算法的执行结果，图4-b为决策树分类作业调度算法的结果。图中横坐标为作业的执行时间，纵坐标为作业的执行顺序。可以看出两种算法的执行顺序是不一样的，由于Hadoop中默认的调度算法为FIFO，因此作业调度顺序为先进先出［12］。而基于决策树调度算法是根据作业的配置训练分类得到作业的估计运行时间才进行的调度，利于作业的合理调度，得到作业的执行顺序为1、2、7、5、3、8、4、6。比较两者作业的总运行时间，FIFO算法的总执行时间为35.6s，而基于决策树调度算法的执行时间为22.7s，缩短了作业的总执行时间，同时使得短作业不至于等待时间过长导致用户满意度降低，证明了该算法具有较高的效率。

图4 两种调度算法的结果

4 结束语

作业调度的效率对Hadoop性能提高至关重要。因此本文提出一种云计算环境下的基于决策树分类算法的作业调度算法，用决策数据对作业的配置进行训练。该算法可以预测进入环境的作业的运行时间，从而来调度作业。通过实验验证该算法是可行的，并且与Hadoop环境中默认的FIFO算法的调度结果进行比较后，验证了该算法的效率。

［1］ Lin C，Tian Y，Yao M.Green network and green evaluation：Mechanism，modeling and evaluation［J］.Chinese Journal of Computers，2011，34（4）：593-612..

［2］ 李亚琼，宋莹，黄永兵.一种面向虚拟化云计算平台的内存优化技术［J］.计算机学报，2011，34（4）：684-693.

［3］ Application of Multi-level Compressed Decision Tree in Computer Forensics［C］∥Proceedings 2010IEEE 2nd Symposium on Web Society，2010.

［4］ Zalewska A M.Relationships between anxiety and job satisfaction—Three approaches：‘Butoom-up’，‘Buttom-down’and‘transactional’［J］.Personality and Individual Differences，2011，5（50）：977-986.

［5］ 徐鹏，林森.基于C4.5决策树的流量分类方法［J］.软件学报，2009，20（10）：2692-2704.

［6］ 李强，郝沁汾，肖利民，等.云计算中虚拟机放置的自适应管理与多目标优化［J］.计算机学报，2011，34（12）：2253-2264.

［7］ 李丽英，唐卓，李仁发.基于LATE的 Hadoop数据局部性改进调度算法［J］.计算机科学，2011，38（11）：67-70.

［8］ Liu Zongtian.Research on Logic Rules for Refinement Learning［C］∥Proceedings of 2010International Colloquium on Computing，Communication，Control and Management（CCCM2010），2010.

［9］ Guo Y J.Research and Implementation of Future Network Computer based on Cloud Computing［C］∥Proceedings of 2010 Third International Symposium on Knowledge Acquisition and Modeling（KAM 2010），2010.

［10］ Wang L Z，Laszewski G V，Dayal J，et al.Towards energy aware scheduling for precedence constrained parallel tasks in a cluster with DVFS［C］∥Procecdings of the 10th IEEE／ACM Int’l Conf on Cluster，Cloud and Grid Computing.Melbourne：IEEE Computer Society，2010.

［11］ 李微，李德仁.基于 HSV色彩空间的 MODIS云检测算法研究［J］.中国图象图形学报，2011，16（9）：1696-1701.

［12］ 张伟哲，张宏莉，张迪，等.云计算平台中多虚拟机内存协同优化策略研究［J］.计算机学报，2011，34（12）：2265-2275.