异构环境下改进的late调度算法

《异构环境下改进的late调度算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、异构环境下改进的LATE调度算法　　摘要：针对异构环境下LATE算法在选择备份任务及执行节点时的不足，提出一个改进的IR-LATE调度算法。算法通过计算为剩余完成时间最长、最需要备份的慢任务启动备份，并将其按负载不同进行分类，结合轮询算法，将备份任务分配到负载最小且成功/负载比高的节点上执行。实验结果表明，该算法与LATE算法比较，有效的将作业完成时间缩短了30%左右，提高了执行效率，进而促进系统的负载均衡。　　关键词：异构环境；LATE；调度算法；慢任务；负载均衡　　中图分类号：TP301.6文献标识码：A　　Abstract：Analy

2、zingtheexistingschedulerintheheterogeneousenvironment，andconsideringthelackofLATEschedulingalgorithminallocatingTaskTrackertoexecutebackuptasks，thispaperputforwardanimprovedIRLATEschedulingalgorithm.Theslowtaskswiththelongesttimeremainingandthemostneedingthebackupwerefound

3、outbycalculating.Theywereclassifiedaccordingtothedifferentload.ThenthebackuptaskswereassignedtotheTaskTrackerwithaminimumworkloadandhighsuccess/workloadratiocombinedwithRoundRobinalgorithm.Theexperimentalresultsshowthat，comparedwithLATEalgorithm，thealgorithmiseffectiveinsh

4、orteningtheoperationexecutiontimeby30%andimprovingtheexecution8efficiency，thuscontributingtotheloadbalancingsystem.　　Keywords：heterogeneousenvironment；LATE；schedulingalgorithm；slowtask；loadbalancing　　1引言　　互联网的迅猛崛起给人们带来了丰富的网络生活，随之也加剧了海量数据亟待处理和存储的需求，于是专家们将并行计算的思想迁移到集群计算上，云计算

5、[1]应运而生。Hadoop[2]是一个云环境下开源的大数据处理平台，是MapReduce[3]调度方式和GFS[4]数据存储方式的开源实现，无疑成为大数据时代的宠儿。　　由硬件配置迥异的节点组成的Hadoop集群，其中运行着多个Job，如何让调度器对资源进行合理分配，以期使得集群资源能被更有效的利用成为一个不可忽视的方面，而其中的关键点就是调度策略的合理设计。Hadoop自带的调度算法：FIFO算法、Fair算法[5]、Capacity算法[6]及金嘉晖等人提出的等待时间阈值的自适应模型[7]均是以同构系统为前提的，而未考虑其异构性。LA

6、TE[8]调度算法，由MZaharia等人研究，针对异构环境下的慢任务探测提出一种通过估计任务剩余完成时间，选择快节点为最长剩余完成时间的任务启动备份的调度策略，虽然其计算效率有所提高，却不曾考虑任务及节点的负载类型。8　　本文在分析研究前人成果的基础上，对LATE调度算法在备份任务及执行节点的选择方面提出了改进。首先将提交的作业按负载类型进行分类，获取慢任务中剩余时间最长的slowTask并为其启动备份，然后在选择执行备份任务的快节点时，根据负载类型，结合轮询算法，选择存在空闲槽且成功/负载比高的最快节点，以期达到缩短作业完成时间，提高资

7、源利用率，优化集群负载。　　2相关工作分类及定义　　2.1作业负载分类　　按照文献[9]的负载分类机制，将任务负载分为CPU_bound和I/O_bound两类。在Hadoop环境中运行的作业，只有全部的Map任务结束才会执行Reduce任务，因此本文仅考虑Map任务。Map任务执行可分解为3步操作：　　（1）初始化输入数据；　　（2）计算Map任务；　　（3）将输出结果存储到本地磁盘。　　任务负载分类所用到的符号定义见表1。　　3.2算法描述　　每个节点将自身的CCPU，Cmem，Cdisk，Cnw信息、任务成功率和节点的负载信息通过He

8、artbeat发送给JobTracker，JobTracker在接收到这些信息后重新计算workload值，并更新BurdenforCPUList和BurdenforIOList