在计算能力调度算法中没有全面考虑各资源特征的分配是否满足作业多样的服务要求，提出一种基于优先级的计算能力加权调度算法，根据作业的优先级以及提交时间等因素来计算作业的权重。依据作业的权重对作业队列进行排序并分配空闲的slot给队首的作业，从而避免调度陷入局部最优也能更好地满足作业的多样性服务要求。在搭建的Hadoop平台上进行实验表明，改进后的算法能较均衡地分配系统资源减少一些作业的等待时间，并且运行全部作业的用时有所减少。
戴小平,张宜力: Hadoop平台下计算能力调度算法的改进与实现 2015,51(19 (3)选择task,考虑lask的 locality和资源使用情况。 askcapacity、 blocksize和 avgtasksize对同一队列的作业 计算能力调度算法应用于较多小作业时性能较差,米说都是定值所以可以简化权重公式为 容易陷入局部最优,夲文的算法主要是在计算能力调度 priority weight[i (ctime task 的基础上优化步骤(2)中的作业选择策略,优化后的策 ∑ priorily[i sume alas 咯更加公平,避免选择策略陷入局部最优,从而提高了 从公式(6)可以看出作业的优先级是对权重影响最 整个系统的效率和用户满意度 大的因子,这是因为(mc+as)>1。这样不仪能实 在原算法中作业队列是按照作业提交时间和作业 优先级进行排序,然后选择队列头部的作业。在本算法现作业的差异化词度,还能够更公平地调度作业,尤其 中首先根据作业权重对每个队列的作业进行排序,然后 是一些优先级较低的小作业。 将这个空闲的st分配给选中队列的第一个作业的task42算法的实现 (该作业必须满足步骤(2)中的两个条件)。可以看出, 1)数据结构设计 作业的权重是选择的重要参考依据。 bQueue的调度队列中每个元素 joiNto的数据结 考虑到1 ask Tracker主动请求task的模式以及 Hadoop构为 仟务调度体系非抢占模式的特六,为了使调度的任务避 class JahScheduling In fo 免长期的等待,同时各个任务调度权重又能根据实际情 Jobld jobld; 况进行调整,可以通过下面一系列推导得到权重的公式 JobPriority priority 假设用V表示一个轮转周期内处理数据的总量, long starttime 般情况下Map务的数量远远超过 Reduce f务的数量。 int tasks um=o 因此,用系统能够同时运行的Map任务数量的能力来表 int finshed task num =0 double weight=0 示系统的所能处理任务数量的能力,记为 taskcapacity 而且每个Map任务所处理的数据量为输入数据的分块 本文算法在 Job Schedulinglnfo中增加了几个参数, 大小即为IDFS中数据块的大小,记为 block size(一股设解析如下 为64MB),所以每一个轮转周期系统所处理的数据量为: taskNum:作业的任务数量: V= taskcapacity x hlock size (1) finshedTaskNum:作业已完成的任务数; 用 avgtasksize表示某job划分的任务平均大小, jobsite weight:作业的权重。 表示某job的大小, tasknum ber表示job的任务数,则有 (2)权重的计算方法 avgtasksize[]= jobsite[il (2) 权重的计算要基于作业的优先级、作业的提交时间 lasknumberlil 以及作业的完成量,其中优先级对应的值如表1所示 如果jb的权重为 weight[为了保证优先级的 作用和有效性,某个job的优先级与所有job优先级之和 苌1优先级对应的具体值 的比值应该基本等于这个job执行的数据量与队列一个 Priority valuc VERY HIGH 4.0 轮转周期的数据量的比值,即有 3.0 avglasksize[i]x weight[] prioritvli (3) NORMAL taskcapacity x blocksize priority lil LOW 1.0 于是就可以得到 算法的供代码如下 cigh taskcapacity x blocksize x priority il (4) avgtasksize[]x∑ priority] Input: JobInfo Output: null 根据实际情况对权重进行动态的调整遥免算法陷 1./*权重的变化取决于 factor的变化* 入局部最优,这里的实际情况就是队列中作业的等待时 2 update parameter of job/*更新当前 jobInfo的信息* 间以及作业完成度(未完成task全部的task)。因此计 3. factor-unfinished task numbers/task Num +current time 算作业权重要将作业的等待时间以及作业的完成度考 rtT 虑进去,由此可得: 4. if unfinished task numbers of job: >0 weight[i] taskcapacity x blocksize x priority then avgtasksize[ix∑ prior /*sum( priority)是队列中所以作业优先级值的和*/ ctime task stime atask (5) 5. job weight=( priority/sum( priority ))factor 其中, ctime表示当前时间,stme表示作业提交时间, 7. job weight=0 task表示未完成任务数, atask代表任务的总数。 8. end if 权重是同一队列中作业排列的依据,在公式(5)中 (3)算法的其他内容描述 64 015,51(19) Computer Engineering and Applications计算机工程与应用 本算法中要将 JobQueue中作业根据作业的权重进 表3作业详细信息 行排序,实现的关键部分就是增加一个新的比较器.通 作业大小MB作业优先级 过比较器来对队列排序。比较器伪代码描述如下 作业1 4 LOW 作业2 512 LOW Input: JobInfo job, Joblnfo job 2 作业3 512 NORMAL Output: int 作业4 NORMAL 1./res是权重比较的结果* 作业5 5l2 HIGH 2.if job weight<job2 weight 作业6 HIGH 作业7 VERY HIGH 作业8 SI VERY HIGH 4. cl 1 weight==job2 weight ? 0: 1) 7.if res-=0 then γ在权重相等的情况下,进一步比较作业的优先级* 8. if jobl priority<job2 priority then 0123456789101114151617 10. else 时间 res=(jobI priority==job2 priority? 0: 1) 图2FIFO调度器运行结果图 12. end if /sres仍然等于零时直接比较作业的ID来求出res*/ 13. if res==0 4 then res -job1 Id compare to job1 16.end if 8 5实验结果及分析 123456 89101112 时间/m 实验采用三台虚拟机,操作系统为 Linux ubuntu 图3计算能力调度器运行结果图 10.042, Java version为1.6.010rc2, Hadoop版本为0.202。 将其中一台作为主机 Master,其余的两台分别作为 Slave 使用最常川的 WordCount(从文本数据统计单词次数)作 业来测试调度的改进。算法部分参数配置如表2所示 表2算法参数配置 属性值 取值 supports-priority T queue. default capacity 3456 minimum-user-limit-percent 时间/min maximum-initialized-jobs-per-user 2 图4本文算法运行结果图 实验!将八个作业传到集群上运行,作业的详细信 对比实验结果可以看出三个调度算法的执行顺序 息如表3。 均不相同,时长不一。FIFO算法是按照作业的优先级 FIFO调度器中得到的运行时间如图2所示。 和进入队列先后时间顺序执行的,没有考虑作业的长短 将 Hadoop0.20.2计算能力调度器插入到集群屮。以及不同作业的需求,执行总时间最长,计算能力调度 同样将上面的八个作业传到集群上运行得到的运行时算法和本文算法执行顺序不同是因为算法的选择作业 间如图3所示 策略不同。对比图3和图4,可以看出图4中的部分小作 将本文的调度算法插入到集群中,得到的运行时间业执行时间提前,执行顺序并没有严格按照作业的优先 如图4所示 级进行执行;还可以看出虽然部分作业的执行时间廷长 戴小平,张宜力: Hadoop平台下计算能力调度算法的改进与实现 2015,51(19 了但是等待作业执行时间提前了。这是因为在作业执6结束语 行的尾段,作业的完成度较高而等待作业的完成度较 作业调度器关系到 Hadoop平台整体的性能和系统 低,调度器动态调整了作业的权重,等待作业的权重这的资源使用效率,以及云计算服务的能力。本文提出了 时候有可能大于运行的作业,这样就减少了等待作业的一种基于优先级的计算能力加权调度算法,当系统出现 响应时间。同时可以看出,优化后的作业选择策略使得空的slot时,作业的选择策略不仅仅考虑作业的优先 总时间比计算能力调度算法减少了两分多钟。 级而是同时将作业的等待时间和作业完成度动态的考 实验2测试更一般的情况,提交八个作业到集群上虑进去。这种策略避免了作业调度器陷入局部最优,同 运行。作业的优先级和大小是不尽同的,集群分别使用时能够减少某些相对较高优先级小作业的等待时间,在 FIFO、本文算法和计算能力调度算法,完成时间对比如一定程度上优化了作业选择策略,减少了总运行时间, 图5所 提高了系统的使用效率 FIFO 参考文献 计算能力算法 本文算法 []刘鹏云计算[M]2版北京:电子工业出版社,2011. 三10 onlargeclustersjj.communicationsoftheAcm,2008 51(1):107-113 [3 Ralf L Googles MapReduce programming model-revisited[J 345678 Scicncc of Computcr Programming, 2008, 70(1): 1-30 完成作业个数 4] wbite T Hadoop权威指南[M]曾大聃,周傲英,译北京:清 图5作业在不同调度算法下的完成时间对比 华大学出版社,2010 5 Apache Hadoopeb/ol]-2013-09-01.httP: //hadoop. apache 从图5可以看出虽然本文算法在完成前几个作业和 原算法的用时上并没有太大的优势,但是随着作业数的增(6]赵春燕云环境下作业调度算法研究与实现[D北京:北京 加本文算法逐渐显现出优势。因此可以预测,在大的多用 交通大学,2009:20-58 户多任务的集群上本文算法的效率肯定将超过原算法。[7]罗军舟,金嘉晖,送爱波,等云计算体系架构与关健技术 实验3将三个不尽相同的作业组上传到集群上,并 通信学报,2011,32(7):3-21. 用本文算法和计算能力调度算法进行测试。每组八个8 Fair SchedulerEB/oL20130901htp: hadoop. apache 作业,作业的优先级随机分配,J-a是小作业占多数的作 org/common/docs/r0 20.2/ fair scheduler.htmL. 业组,b是大作业和小作业的数量相当的作业组,c是 [9]capacityScheduler[eb/ol].[2013-09-01.http://hadoop.Apache 大作业占多数的作业组,得到结果如图6所示。 org/common/docs/r0.20.2/capacity scheduler htmI [10] Torabzadch F, 7andich M Cloud thcory-bascd simulated annealing approach for scheduling in the two-stage 计算能力算法 本文算法 assembly flowshop[J]. Advances in Engineering Software 15 2010,41(10):1243-1298 12 [11 Zaharia M, Borthakur D, Sen Sarma J, et al. Delay scheduling A simple tcchniquc for achieving locality and fairness in cluster scheduling[C]/proceedings of EuroSys 10 Nev York. NY USA: ACM, 2010: 265-278 J-a J-b [12 Matei Z, Dhruba B, Joydeep s, et al. Delay scheduling 图6三组作业在两种调度算法下的时间比较 A simple technique for achieving locality and fairness in cluster scheduling[C]/Proc of the 5th European Con 从图6可以看出来不同类型的作业组在本文算法下 ference on Computer Systems, 2010: 265-278 运行的时间均比计算能力调度算法要少。在作业组中有 [1]3]李建锋,彭舰云计算环境下基于改进遗传算法的任务调 较多小作业的时候本文算法可以减少总运行时间,当作 度算法[J计算机应用,2011,31(1):184-186 业组中大作业占据绝大多数时,4文算法就退化为与计141邓自立云计算中的网络拓扑设计和 Hadoop合研究Dl 算能力调度算法类似。结合实验对比图可以得出本文 合肥:中国科学技术大学 算法减少了部分作业等待时间,优化了作业选择策暾,[15陈艳金 Mapreduce模型在 Hadoop平台下实现作业调度 使得作业组的总运行时间减少,提高了用户的满意度。 算法的研究和改进[D]广州:华南理工大学,2011