基于任务分类的延迟调度算法

MapReduce已经成为主流的海量数据处理模式,任务调度作为其关键环节已受到业界广泛关注。针对已有的延迟调度算法存在的问题,即建立在任务都是短任务的理论假设有一定限制,当节点处理不同长度的任务时算法性能严重下降和基于静态的等待时间阈值不能适应不同用户的作业需求,提出了一种基于任务分类的延迟调度算法。该算法通过给不同长度的任务设置不同的等待时间阈值,以适应不同作业的响应需求。通过分析各动态参数,根据所建任务模型调整任务的等待时间阈值。仿真验证该算法在响应时间及负载均衡性方面优于已有的延迟调度算法。     

基于动态等待时间阈值的延迟调度算法

针对已有的延迟调度算法存在的两个问题,即建立在节点会很快空闲的理论假设下有一定限制,当节点不会很快空闲时算法性能严重下降和基于静态的等待时间阈值不能适应云计算数据中心动态的负载变化及不同用户作业的需求,提出了一种基于动态等待时间阈值的延迟调度算法(dynamic waiting time delay scheduling,DWTDS)。该算法通过给无本地数据节点设置节点最大等待时间,以适应节点不会很快空闲的情况;通过分析数据中心各动态参数,根据概率模型调整作业的等待时间阈值。实验验证该算法在响应时间及负载均衡性方面优于已有的延迟调度算法。     

基于优先级的Three-Queue调度算法研究

针对Hadoop平台上调度算法存在的不足,提出了一种改进的调度算法———Triple-Queue算法。在充分考虑数据的本地性后,Triple-Queue算法设计了一种改进的优先级计算模型,以有效地区分用户作业的等级,同时又保证一定程度的公平性,进而减小作业执行时间,避免系统资源浪费。实验结果表明,随着数据量的提高,该算法执行效率明显提高,同时能够较好地解决数据本地性问题。     

基于任务备份的云计算容错调度算法

云计算所提供的服务面向庞大的用户群,随着节点规模的扩大、任务执行时间的增长,云计算的故障率越来越高。为此,提出基于任务备份的云计算容错调度算法。将任务映射到含有该任务输入数据且负载最小的节点,根据云计算的安全等级将任务进行备份,并重新调度失败任务。仿真实验结果表明,该算法具有较好的容错性,任务调度成功率达到99%。     

基于延迟任务云资源调度方法的研究

基于云任务的动态延迟到达,到达时间具有随机性,进行任务分配到虚拟机执行的仿真模拟。仿真任务是基于排队论的指数分布到达方式,虚拟机的处理速度存在差异。实验思路是高优先级尽可能早的执行,同时避免低优先级任务饿死的思路,并定义了一个消费量作为对比点,对比基于一定等待的调度与贪心调度的差异。通过设置动态等待时间的设置来进行实验,同时测试多组输入数据减少样本的偶然性。对比分析各种数据,验证实验的有效性。并通过CloudSim进行云仿真实验模拟。     

基于模拟退火的Map Reduce调度算法

在计算能力作业调度算法的基础上,提出一种基于模拟退火的Map Reduce作业调度算法.利用带记忆功能的模拟退火算法选择最优作业,从而避免陷入局部最优解.在Hadoop平台上的实验结果表明,该算法能减少所有作业的运行时间以及每个作业的等待响应时间,具有较高的作业调度效率及用户满意度.     

基于任务延迟的云计算资源调度算法研究

云计算是基于互联网发展起来的新型计算模式,对网际间各个节点的计算能力达到了充分利用;为了提高用户对云计算的使用效率,一般要为用户任务进行合理的全局资源调度和本地资源调度;对于全局资源调度,提出了一种改进的DAG图方法,充分考虑了任务撤销后对全局资源调度的影响;对于本地资源调度,提出了一种基于任务延迟的资源调度方法,充分考虑了立即调度不能执行时,如何合理地配置本地计算资源和等待时间的问题;实验结果表明,提出的方法能较好地提高全局资源调度和本地资源调度的效能。     

Hadoop作业调度本地性的研究与优化

作为开源云计算平台的核心技术之一,Map Reduce作业处理框架及其作业调度算法,对整个系统的性能起着至关重要的作用,而数据本地性是衡量作业调度算法好坏的一个重要标准,首先本文介绍和分析了Map Reduce基本原理,Map Reduce作业处理机制和Map Reduce作业调度机制及其在数据本地性方面表现出的优缺点等相关内容。其次,针对原生作业调度算法在数据本地性考虑不周全的问题,结合数据预取技术的可行性与优势,通过引入资源预取技术设计并实现一种基于资源预取的Hadoop Map Reduce作业调度算法,使作业执行效率更高。     

MapReduce在Hadoop平台下作业调度算法的改进和实现

该文在Hadoop实现的MapReduce架构基础上,分析了现有的三种作业调度算法,针对当前算法没有考虑服务器负载状况和数据本地性差的缺点,提出了基于可变长度队列的公平调度算法(FSVQ),该算法分析了空闲节点率,并通过采取等待的办法满足考虑数据本地性。实验证明该算法可增加服务器集群的工作效率,减少网络延迟,具有实际的应用意义。     

异构环境下自适应Reduce任务调度算法的研究*

在异构环境下的MapReduce编程模型中,Reduce任务的调度存在随机性,通常在分配任务时既没有考虑数据本地性,也没有考虑计算节点对当前任务的计算能力。针对以上问题,提出一种异构环境下自适应Reduce任务调度算法(SARS),该算法首先根据Reduce任务的输入数据分布选择所含数据量最大的机架;在选择计算节点的过程中,结合节点所含任务的数据量、节点的计算能力和当前节点的忙碌状态来选出任务的执行节点。最后实验结果表明,SARS算法减少了Reduce任务执行时的网络开销,同时也减少了Reduce任务的执行时间。     

数据本地性感知的MapReduce负载均衡策略

现有针对MapReduce的负载均衡调度的研究均未考虑中间数据的分布特点及网络传输的开销,导致额外的网络传输代价与系统效率的下降。为解决上述问题,提出了一种数据本地性感知的负载均衡策略。充分利用YARN中资源管理的新特性,在Map阶段对内存数据溢写的同时进行统计以获取数据分布,根据数据分布情况及各节点的计算能力进行任务调度,减少网络传输开销的同时尽量保证各节点的负载平衡。此外,通过引入细粒度分区与分区的自适应分裂策略,进一步提高在数据倾斜时调度策略的性能。对比实验结果表明,提出的负载均衡调度策略能有效提升性能,同时较好地降低网络总开销。     

An anomaly prevention approach for real-time task scheduling

This research responds to practical requirements in the porting of embedded software over platforms and the well-known multiprocessor anomaly. In particular, we consider the task scheduling problem when the system configuration changes. With mutual-exclusive resource accessing, we show that new violations of the timing constraints of tasks might occur even when a more powerful processor or device is adopted. The concept of scheduler stability and rules are then proposed to prevent scheduling anomaly from occurring in task executions that might be involved with task synchronization or I/O access. Finally, we explore policies for bounding the duration of scheduling anomalies.     

一种基于两级DAG模型的MapReduce工作流异构调度算法

MapReduce编程模型被广泛应用于大数据处理平台,而一个有效的任务调度算法对模型的运行效率至关重要。将MapReduce工作流的Map和Reduce阶段分别拆解为若干个有先后序限定关系的作业,每个作业再拆解为多个任务。之后基于计算集群的可用资源和任务异构性,构建面向作业和任务的2级有向无环图(DAG)模型,同时提出基于2级优先级排序的异构调度算法2-MRHS。算法的第1阶段进行优先级排序,即对作业和任务分别进行优先权值计算,再汇总得到任务的调度队列;第2阶段进行任务分配,即基于最快完成时间将每个任务所包含的数据块子任务分配给最适合的计算结点。采用大批量随机生成的DAG模型进行实验,结果表明与其他相关算法相比,本文算法有更短的调度长度(makespan)且更加稳定。     

Scheduling algorithm based on prefetching in MapReduce clusters

Due to cluster resource competition and task scheduling policy, some map tasks are assigned to nodes without input data, which causes significant data access delay. Data locality is becoming one of the most critical factors to affect performance of MapReduce clusters. As machines in MapReduce clusters have large memory capacities, which are often underutilized, in-memory prefetching input data is an effective way to improve data locality. However, it is still posing serious challenges to cluster designers on what and when to prefetch. To effectively use prefetching, we have built HPSO (High Performance Scheduling Optimizer), a prefetching service based task scheduler to improve data locality for MapReduce jobs. The basic idea is to predict the most appropriate nodes for future map tasks based on current pending tasks and then preload the needed data to memory without any delaying on launching new tasks. To this end, we have implemented HPSO in Hadoop-1.1.2. The experiment results have shown that the method can reduce the map tasks causing remote data delay, and improves the performance of Hadoop clusters.     

一种Hadoop中基于作业类别和截止时间的调度算法

Hadoop是一种开源可靠的分布式计算框架,而MapReduce是处理超大规模数据集的编程模型.鉴于Ha-doop内置的调度器不能很好地处理类别不同且有截止时间的作业的调度,提出了一种基于作业类别和截止时间的作业调度算法.作业分为CPU密集型和I/O密集型,并根据截止时间设置优先级来实现作业的调度.实验结果表明,该算法在充分利用集群的CPU和磁盘I/O的同时,能满足作业的截止期需求,当同一时间段内截止时间相近时算法达到最优,当某一队列中作业截止时间均比另一种队列短时,算法效率最低.     

异构环境下MapReduce动态任务调度技术研究

针对MapReduce在异构环境下各节点性能不均衡,导致整体计算效率低下的问题进行了研究。为此,从节点与任务两方面入手,提出了一种将节点性能量化并排序与将任务按相似度划分相结合的算法。该方法首先根据历史日志以及实时回传的日志信息将节点按照性能高低排序;然后根据任务执行完成的信息,将其与新任务进行比对得到相似度,从而推测出新任务的执行时间,执行时间长的认为是复杂的任务;最后进行动态调度,使高性能节点处理更复杂的任务。在随机生成数据集上的实验结果表明,所提出的动态调度算法与默认调度算法相比,数据集为20G大小时执行速度提高27.4%,数据集为100G大小时执行速度提高了74.1%。