Hadoop 中任务调度算法的改进
苏小会，何婧媛
（西安工业大学计算机科学与工程学院，陕西西安710032）
摘要：针对Hadoop0.20.0中任务调度算法存在的不足，提出一种基于改进遗传算法（IGA ）的任务调度算法。IGA 算法对初始化种、交叉和变异操作进行了一些改进，并引入了最优保留策略和加速进化策略。通过仿真实验将此算法与
Hadoop 现有算法进行比较，实验结果表明，此算法优于Hadoop 现有算法，是一种有效的任务调度算法。
关键词：Hadoop 平台；任务调度；遗传算法；加速进化策略中图分类号：TP302
文献标识码：A
文章编号：1674－6236（2012）22-0033-04
Improvement of task scheduling algorithm in hadoop
SU Xiao -hui ，HE Jing -yuan
（School of Computer Science and Engineering ，Xi ’an Technological University ，Xi ’an 710032，China ）
Abstract:A task scheduling algorithm based on improved genetic algorithm （IGA ）was brought up for the deficiences of the task scheduling algorithms in Hadoop0.20.0.IGA algorithm improved the original colony is initialized and crossover and mutation operation ，and introduces retention optimal strategy and evolution acceleration strategy.There is a contrast between IGA and existing algorithm in Hadoop through simulation experiment ，and the result is:the IGA is better ，it is an effective task scheduling algorithm.
Key words:hadoop platform ；task scheduling ；genetic algorithm ；evolution acceleration strategy
收稿日期：2012-07-23
稿件编号：201207143
作者简介：苏小会（1970—），男，陕西武功人，硕士，副教授。研究方向：智能信息处理与智能控制。
云计算技术发展到现在，已经出现了很多云计算的软件平台，但是功能强、性能稳定的基本都是商业软件，目前只有
hadoop分布式集搭建Hadoop 是可实现大规模分布式计算的开源软件平台[1]，因此
对于Hadoop 的应用和研究也最多。
Hadoop 旨在构建一个具有高可靠性和良好扩展性的分
布式系统，在很多大型网站上都已经得到了应用，可以说是目前最为广泛应用的开源云计算软件平台[1]。Hadoop 有以下优点：扩容能力强、成本低廉、效率高、高可靠性、免费开源及良好的可移植性。
Hadoop0.20.0中的任务调度算法包括FIFO 调度算法
（First In First Out ）、公平调度算法（Fair Scheduler ）和计算能力调度算法（Capacity Scheduler ）。FIFO 算法的整体性能和系统资源的利用率不高；公平调度算法负载不均衡，系统的响应时间长，配置文件的好坏影响整个系统的性能；计算能力调度算法中队列设置和队列组无法自动进行从而影响系统整体性能的提高。因此对于Hadoop 中任务调度算法的改进和优化一直就没有停息，文中根据对任务执行过程的实时监控，依据任务执行结果放的反馈，动态调整后续任务的分配和执行，在现有任务调度算法的基础上提出一种基于改进遗传算法（IGA ）的任务调度算法，该算法最大特点是利用遗传算法的
体搜索技术使得体进化到包含或接近最优解，从而解决现有任务调度算法收敛速度慢、任务完成时间长、负载不均、资源利用率低、系统整体性能低等缺点。
1问题分析
任务调度算法作为Hadoop 平台的核心技术之一，直接
关系到Hadoop 平台的整体性能和对系统资源的利用，本文的研究目标是改进和完善任务调度算法以提高平台的整体性能和系统资源使用率。
1.1Hadoop 中的任务调度算法
Hadoop 的MapReduce 任务调度[2]是一个主动请求的任
务，其任务请求调度过程如图1所示。slave 的SubTaskTracker 主动向master 的TaskTracker 请求任务，当SubTaskTracker 接到任务后，通过自身调度在本slave 建立起SubTask ，执行任务。
这个过程可以简单地概括为以下4个步骤：
1）TaskClient 提交任务；
2）TaskTracker 接收任务生成子任务；3）SubTaskTracker 申请子任务；4）TaskTracker 分配并监控子任务。
对Hadoop 中调度算法的改进也已经有很多研究，文献
[3]中作者提出了一种基于朴素贝叶斯分类的作业调度算法。
改进遗传算法的并行任务调度[4]中提出了一种基于改进遗传算法的并行任务调度算法。文献[5]中HP 实验室开发的
Dynamic Priority schedule 调度，允许用户不断地增加或更改
他们的队列优先顺序来满足当前负载的需要。文献[6]中介绍
电子设计工程
Electronic Design Engineering
第20卷
Vol.20
第22期No.222012年11月Nov.2012
－33－
《电子设计工程》2012年第22期
图1Hadoop的任务请求调度过程示意图
Fig.1Process schematic diagram of the task request scheduling in hadoop
了延迟调度并提出了一种基于特征加权的朴素贝叶斯分类器算法来解决公平调度算法中需要对队列和资源池进行资源配置的问题，
1.2问题分析
Hadoop0.20.0中公平调度算法和计算能力调度算法都需要在分配任务资源之前进行一些配置工作，比如管理员需要对SubTaskTracker上可以同时运行的最大子任务数进行正确设置。但要准确设置最大子任务数，需要管理员深入掌握Hadoop 平台上运行的MapReduce任务和SubTaskTracker两者各自资源使用特点。公平调度算法和计算能力调度算法虽然比FIFO 调度算法有很大程度上的提高，但仍然需要预先设置任务池和用户池的容量或是权重，实际操作中遇到多用户、多任务情况下预先设置任务池和用户池的容量或是权重难度很大。
文中研究不预先设置最大子任务数以及任务池和用户池的容量或是权重，而对任务执行过程进行实时监控，根据任务执行结果的反馈，对后续任务进行动态调度，在现有任务调度算法的基础上对最大子任务数以及任务池和用户池的容量或是权重的取值使用遗传算法进行动态计算，得到最佳取值后再应用公平调度算法或者计算能力调度算法进行调度。IGA任务调度算法试图做出以下一些改进：1）对遗传算法的初始种生成方式进行改进，以达到减少迭代次数，并提高运行速度的目的；
2）用两个适应度来选择种，以便达到总任务的完成时间和任务平均所用时间都较短的目的；
3）在选择、交叉、变异等遗传操作过程中，有可能会破坏当前种中适应度最高的个体，加入最优保留策略来更好的对种进行优胜劣汰以提高算法的收敛精度；
4）采用规则约束的交叉和变异操作以提高个体质量；
5）引入加速进化策略以避免早熟而使得算法停滞的问题。2基于改进遗传算法的设计
2.1初始种生成
基于均匀分布策略的初始种生成方式可以保证随机产生的个体间有明显的差异，使它们比较均匀地分布在解空间上，保证初始种有较丰富的模式，从而提高搜索收敛于全局最优解的可能，再进行几代进化，使得种中解的质量逐渐提高，然后通过寻提交给遗传算法的任务间的相似性，重复使用先前相
似任务的解决方案作为当前任务的种染体个体，以此来形成当前任务的初始种，从总体上减少总的进化次数。IGA的初始种采用基于均匀分布策略通过随机方式产生整个算法的第一代种，以保证有足够的个体差异性。
为实现改进遗传算法的初始种选择性建立问题，本文引入一个历史表用来存储对任务的描述和对应的调度方案。
定义1：任务的描述是任务在资源上执行时间的矩阵ETC[i，j]，ETC矩阵表示各个子任务在每个资源上执行时间，ETC[i，j]表示第i个子任务在第j个资源上执行完成所需要的时间。
定义2：不同样本之间的相似性度量（Similarity Measur-ement）通常采用计算样本间“距离”（Distance）的方法，任务的相似性判断可以通过输入任务的期望执行时间矩阵ETC 与表中存储的历史任务执行时间矩阵计算得到，两个含有k 个元素的向量a（x11，x12，…，x1k）与b（x21，x22，…，x2k），则两向量的相似性可由下式得出：
Simlarity（a，b）=1
1+
k
i=1
Σ（x1i-x2i）2
姨（1）2.2最优保留策略
最优保留策略，即在体交叉、变异之前，先选出本代适应度最高的两个个体进行保留，不参加选择、交叉、变异等遗传操作。而等本代个体完成遗传操作之后，用先前保留的两个个体与完成遗传操作的种中适应度最小的两个
个体进
行替换，这使得种更好的进化，提高了优胜劣汰的质量。
2.3规则约束的交叉和变异操作
交叉将选中个体的基因进行交叉，从而生成包含更优良
结构的新个体。交叉操作在解空间中进行有效的搜索，同时－34－
降低对有效模式的破坏概率。变异随机地改变选中个体串结构数据中某个串的值来产生新个体，以改善算法的局部搜索能力并维持种多样性。由于目前云计算中任务调度的特点，传统的单点、多点和顺序等交叉变异方法不再适用，所以本文采用规则约束的交叉和变异操作。
假设a和b是进行交叉操作的两个个体，则根据以下规则进行交叉：任意将a和b中的一个或者多个串值进行对换，且对换的串值最好是不同的。
变异操作针对选中个体的串结构数据，任意选择n个串中的一个或者多个根据以下规则进行变异：
1）将该串值变异为串结构数据中任意的一个值；
2）将任意串移动到距其所在串结构的前一不同串值的任意位置。
2.4加速进化策略
算法后期的种中容易导致早熟局部收敛，为了避免早熟而使得算法停滞的问题，本文引入了加速进化策略，即在检测到算法的早熟指标D p≤$后，则将交叉和变异的概率均
临时性的提高k倍，文中将k取值为10，以保证在加速进化后的交叉和变异概率达到100%；当早熟指标D p>$后，又将交叉和变异的概率恢复正常。其中$为早熟判断门限值，其值由求解中某代个体平均适应度的量级确定，即1×10x。若50个任务，由平均适应度的量级确定x=-2，则$=0.01。
D p=f max-f min
f ave
（2）其中，f max表示本代个体最大适应度值，f min表示本代个体最小适应度值，f avg表示本代个体平均适应度值。
3基于改进遗传算法的实现
3.1算法流程
根据第2节的描述，算法的求解过程如下：
1）初始化控制参数；
2）对基因进行编码，并随机产生初始种；
3）评价体中每个个体的适应度函数值；
4）选出适应度最高的个体进行保留；
5）根据定义的遗传算子，分别对种进行选择、交叉、变异操作，产生下一代子；
6）将保留的个体与新种中适应度最小的个体进行替换；
7）根据加速进化策略对种进行进化；
8）若满足收敛条件，返回最优解，结束算法；否则，返回到步骤3）。
根据上述描述，可以得到基于IGA的任务调度算法流程图如图2所示。
3.2算法实现
根据3.1节给出的算法流程图，将基于IGA的任务调度算法的过程概括如下：
1）客户端提交MapReduee任务；
2）初始化任务，创建运行子任务列表；
3）SubTaskTraeker空闲时，主动发出心跳请求TaskTraeker分配任务；
4）TaskTracker采用基于IGA的任务调度算法选择一个最优的任务；
5）选择该任务的一个子任务分配给发送心跳请求的SubTaskTracker；
6）SubTaskTracker被分配了子任务后开始运行子任务，子任务完成时告知TaskTracker；
7）TaskTracker在接到子任务完成的通知后，把任务的状态设置为“成功”，并显示一条消息告诉用户。
3.3实验验证
由于实验条件有限，本实验平台是由3台机器构成的集，其中一台作为Master，负责NameNode和TaskTracker的工作，另两台作为Slave，负责DataNode和SubTaskTracker的工作。每台实验机器上均运行Ubuntu10.10系统，java版本1.6，Hadoop版本0.20.2。实验中的三台机器分别设置主机名为hadoop1、hadoop2、hadoop3，其中hadoop1为Master，其他为Slave，图3为Hadoop平台结构示意图，具体配置过程简单概括为以下3步：
图3Hadoop平台结构示意图
Fig.3Schematic diagram of the Hadoop platform
图2基于IGA的任务调度算法流程图
Fig.2Flow chart of the task scheduling algorithm based on
IGA
《电子设计工程》2012年第22期
2006.
[5]刘君华.基于LabWindows/CVI 的虚拟仪器设计[M].北京：电
子工业出版社，2003.
[6]孙晓云，郭立炜，孙会琴.基于LabWindows/CVI 的虚拟仪器
设计与应用[M].北京：电子工业出版社，2005.
1）下载Linux 环境下的JDK 安装包jdk-6u27-linux-i586.bin 进行安装，并配置环境变量。
2）配置SSH 及无密码登陆本机3）安装并配置Hadoop ：
使用前面搭建的Hadoop 集来评估算法的性能。将本文提出的IGA 任务调度算法与Hadoop 平台现有的3种算法进行性能比较实验，选取同一个任务，每次用不同的算法运行这个任务，总共运行10次，记录每次算法运行的时间。初始条件：任务数量为50；收敛条件：1）达到最大进化代数
MaxGen （这里取MaxGen=100）；2）如果连续50代总任务完成
时间和任务平均完成时间都没有变化，认为算法基本收敛，终止算法。在生成初始种时若相似度Simlarity （a ，b ）的取值大于或等于0.75就认为任务a 和b 相似。实验参数如表1所示。
要将调度算法从Hadoop 平台现有的调度算法配置为本文IGA 任务调度算法，需要将已经编写好的IGA 任务调度程序拷贝到Hadoop_Home/lib 下，然后在Hadoop 中修改配置文件并加入IGA 任务调度模块，最后检查调度算法是否运行。对实验结果进行分析后得到图4。
由上图可知，FIFO 算法的运行时间最长，且效率低，但是运行时间比较稳定。公平算法和计算能力算法随着
SubTaskTracker 上最多可同时运行的子任务数以及任务池或
者任务队列的设置不同而存在较大的波动。总的来说公平调度算法和计算能力调度算法的运行时间是低于IGA 算法的。本文提出的IGA 算法虽存在波动，但是运行几次后算法开始收敛并趋于稳定。
4结论
文中通过对Hadoop 现有调度算法和IGA 任务调度算法的性能比较实验可知，IGA 任务调度算法的性能比FIFO 算法要高的多，相对公平算法和计算能力算法存在着优势，不仅提供非常不错的性能同时减轻了管理员和用户的负担、提高了管理效率。通过仿真实验也表明IGA 算法可以对
Hadoop 下编程模式实现较为理想的任务调度，满足了实际操
作中多用户、多任务的需求动态变化，解决了公平调度算法和计算能力调度算法中预先设置困难的问题，使得改进的任务调度算法迭代次数少、收敛速度快、任务完成时间少、负载均衡、资源利用率高、系统整体性能高，是一种有效的任务调度算法。参考文献：
[1]Hadoop[EB/OL].（2011-04-16）[2]宋坤芳.基于蚁算法的云计算资源调度策略研究[D].武
汉：武汉纺织大学，2011.
[3]夏袆.Hadoop 平台下的作业调度算法研究与改进[D].广
州：华南理工大学，2010.
[4]袁雪莉，钟明洋.改进遗传算法的并行任务调度[J].计算
机工程与应用，2011，47（10）:56-59.
YUAN Xue -li ，ZHONG Ming -yang.Parallel task scheduling algorithm using improved genetic algorithm[J].Computer Engineering and Applications ，2011，47（10）:56-59.[5]Sandholm T ，Lai K.Dynamic proportional share scheduling in Hadoop[J].In:Springer:2010:110-131.
[6]余正祥.基于hadoop 平台作业调度算法研究[D].昆明：云
南大学，2011.
图4
性能比较实验
Fig.4Performance comparison test
表1
实验主要参数
Tab.1Test main parameters of experiment
参数名称参数取值
实验次数10种规模50任务数50资源数20进化代数
100
（上接第32页）
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
欢迎订阅2013年度《电子设计工程》（半月刊）
国内邮发代号：52-142
国际发行代号：M2996
订价：15.00元/期360.00元/年
""""""""""""""""""""""""""""""""""
－36－

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。