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

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

基于推测的无响应任务自适应容错调度算法

已有的 基于静态的执行失败判定时间阈值 的无响应任务容错调度算法,不能适应大数据处理中心动态的集群负载。针对该问题,提出判定无响应任务执行失败时间阈值自适应调整方法。基于该模型,设计了自适应的无响应任务容错调度算法(AFTS)。AFTS算法通过分析作业规模、单个任务大小和剩余作业推测执行时间等参数,自适应地调整无响应任务判定执行失败的时间阈值,以减少无响应任务对整体作业执行效率的影响,降低作业响应时间。基于开发的原型系统,验证了自适应判定方法,测试了算法的性能。实验结果表明,AFTS算法在作业响应时间等方面优于已有的无响应任务容错调度算法。     

基于平均等待时间约束的松弛预留机制

传统预留机制存在预留请求拒绝率高、可能会延迟本地作业执行的缺陷。为此,提出一种基于平均等待时间(MWT)约束的松弛预留机制,并给出相应的预留接纳算法。采用松弛预留策略,在每个资源上设置任务等待时间阈值,若调度队列中排队任务的MWT超过该阈值,调度系统将使部分排队任务尽快获得空闲资源,从而减少MWT。实验结果表明,该预留机制能有效保障排队任务的MWT、提高资源利用率、降低预留请求拒绝率。     

云计算中一种多DAG工作流可抢占式调度策略

为解决多用户工作流调度过程中的公平性问题,提高资源利用率,满足不同用户DAG工作流的不同QoS需求,提出了抢占式多DAG工作流动态调度模型。该算法将DAG工作流按照QoS需求进行优先级划分,采用高优先级作业优先占有资源的原则调度作业。相同优先级DAG工作流的任务依据带有启发性信息的slowdown进行资源抢占,进一步提高了作业调度的公平性;对于不同优先级的作业调度,提出了基于阈值的回填算法,该算法在保证作业调度公平的同时提高了资源利用率。     

基于集群拓扑结构的工作流调度研究

针对MapReduce的默认调度策略先进先出(FIFO)在执行任务时考虑本地性调度带来的任务等待时间长、资源利用率不高和没有考虑任务的优先级等问题,提出一种基于集群拓扑结构的工作流实时调度算法。MapReduce在对工作流进行Map处理时,首先根据taskTracker的计算能力和数据大小对map阶段工作流的完成时间进行估计,得到一个完成时间隶属函数,然后再利用集群的拓扑结构,得到taskTracker在集群中的距离隶属函数,根据这两个隶属函数来对集群中的taskTracker在工作流处理时间和数据传输时间进行综合性能评估,这样可以有效地缩短任务的等待时间并提高资源的利用率。同时该算法采用对作业进行优先级划分的方式,满足不同类型作业的需求。大量的实验结果表明:该优化策略在平均完成时间和平均等待时间方面要优于FIFO算法,可以有效提高工作流处理的实时性。     

异构系统中一种基于可用性的抢占式任务调度算法*

针对大多数现有的异构系统调度算法没有考虑由多类任务特别是抢占式任务所引起的可用性需求的不足,在现有基于可用性的非抢占式任务调度算法的基础上,通过计算任务的平均等待时间来确定优先级等级,对异构系统中多类抢占式任务的可用性约束的调度问题进行了探索,提出了一种基于可用性的抢占式优先调度算法P-SSAC。该算法在不增加硬件代价的前提条件下通过调度增加了系统的可用性,缩短了任务的平均等待时间,同时该算法可对抢占式的任务进行有效调度。仿真实验结果表明,该算法有效实现了异构系统可用性和任务等待时间之间的折中。     

同构Hadoop集群环境下改进的延迟调度算法

在Hadoop框架下计算资源和数据资源可以在不同物理位置的特点产生本地化问题。延迟调度算法的产生旨在解决本地化问题, 此算法根据任务待处理数据的物理位置作为作业的计算节点, 调度任务至目标节点。但是可能出现同一作业中若干任务集中运行在某一计算节点, 导致作业达不到理想的并行效果。针对原有的延迟调度算法, 提出延迟一容量调度算法, 允许部分任务选择非本地化节点作为原延迟调度算法中任务的目标计算节点, 以提高作业的响应时间与增加作业的并行程度。最后通过实验对比分析, 改进后的算法在执行效率和并行效果明显优于原延迟调度算法。     

基于任务复制的网格任务调度算法

网格中资源之间存在着通信延迟,通过任务复制的冗余,可以减少任务之间的通信开销,缩短整个计算程序的计算时间。目前网格中的任务调度算法基本上是没有考虑任务复制的;而基于任务复制调度算法往往会产生过多的复制任务,增大系统开销,甚至有可能延迟计算时间。由于基于任务复制的任务调度是一个NP问题,因此本文提出了一种基于任务复制的网格资源调度算法,以减少调度长度为主要目标、减少任务复制量和资源占用量为次要目标。该算法在调度长度和任务复制数量以及占用资源数量方面都等于或优于其它算法。     

基于延迟调度策略的Reduce调度优化算法

在大规模的Hadoop集群中,良好的任务调度策略对提高数据本地性、减小网络传输开销、减少作业执行时间以及提高集群的作业吞吐量都有着重要的影响。本文针对Hadoop架构中Reduce任务的数据本地性较低问题,提出了一种基于延迟调度策略的Reduce任务调度优化算法,通过提高Reduce任务的数据本地性来减少作业执行时间以及提高作业吞吐量,该算法在Hadoop架构的Early Shuffle阶段,使用多级延迟调度策略来提高Reduce任务的数据本地性。最后重写原生公平调度器代码实现了该调度算法,并与原生公平调度器进行了对比实验分析,实验结果表明该算法明显减少了作业执行时间,提高了集群的作业吞吐量。     

实时控制系统中固定优先级调度的延迟与抖动控制

在基于固定优先级调度实时控制系统中,任务的延迟与抖动是影响系统稳定性的重要因素,提出一种基于可抢占时间阈值的延迟与抖动控制策略,给出一种保证系统可调度的最优闽值分配算法,并通过对任务延迟和抖动的分析量化出阀值分配后的争最大可能IO延迟及抖动.最后通过仿真实验验证了该策略的有效性.     

信息物理融合系统的动态多优先级调度

信息物理融合系统(Cyber-physical Systems,CPS)的复杂和异构性给设计者带来了不少挑战,其中任务的多样性使得传统的调度策略不能满足CPS的性能需求.提出了专门针对基于大规模传感器网络的CPS的动态多优先级调度策略.根据任务类型分配4级缓存队列:第1级是来自控制器待处理的实时任务,拥有最高的可抢占式优先级;第2级是来自控制器待转发的实时任务,拥有次高的可抢占式优先级;第3级是来自其他节点待转发的非实时任务,拥有第三高的非抢占式优先级;第4级是来自本地待发送的非实时任务,拥有最低的非抢占式优先级.设计了抢占与非抢占混合的动态调度策略来减少任务的平均等待时间,加入了等待时间阈值机制来保证第4级任务的公平性.通过理论分析和仿真实验对调度策略的性能做了评价.仿真结果显示,动态多优先级调度策略在提高系统性能和稳定性上要优于传统优先级调度.     

多MapReduce作业协同下的大数据挖掘类算法资源效率优化

由于任意的MapReduce作业都需要独立地进行任务调度、资源分配等一系列复杂的操作,这使得同一算法协同的多个MapReduce作业之间,存在着大量的冗余磁盘I/O及资源重复申请操作,导致计算过程中资源利用效率低下。大数据挖掘类算法通常被切分成多个MapReduce job协作完成。以ItemBased算法为例,对多MapReduce作业协同下的大数据挖掘算法存在的资源效率问题进行了分析,提出基于DistributedCache的ItemBased算法,利用DistributedCache将多个MapReduce job之间的I/O数据进行缓存处理,打破作业之间独立性的缺陷,减少map与reduce任务之间的等待时延。实验结果表明,DistributedCache能够提高MapReduce作业的数据读取速度,利用DistributedCache重构后的算法极大地减少了map与reduce任务之间的等待时延,资源效率提高3倍以上。     

基于多核处理器的关联任务并行感知调度算法

关联任务在多核处理器上并行调度所产生的通信时延,会对任务调度长度和处理器利用率造成负面影响,为了改善多核系统对关联任务的处理性能,针对关联任务在多核处理器上的调度特点,提出一种并行感知调度算法。计算各任务与终点间的最长路径值,按照该值的降序来分配任务调度次序,在分配处理器内核时兼顾关联度和任务最早可执行时间,设置最佳匹配评价函数。实验结果表明,与busHEFT和DTSV算法相比,该算法具有更短的任务调度时延、更少的通信量以及更高的处理器利用率。     

Honey bee behavior inspired load balancing of tasks in cloud computing environments

Scheduling of tasks in cloud computing is an NP-hard optimization problem. Load balancing of non-preemptive independent tasks on virtual machines (VMs) is an important aspect of task scheduling in clouds. Whenever certain VMs are overloaded and remaining VMs are under loaded with tasks for processing, the load has to be balanced to achieve optimal machine utilization. In this paper, we propose an algorithm named honey bee behavior inspired load balancing (HBB-LB), which aims to achieve well balanced load across virtual machines for maximizing the throughput. The proposed algorithm also balances the priorities of tasks on the machines in such a way that the amount of waiting time of the tasks in the queue is minimal. We have compared the proposed algorithm with existing load balancing and scheduling algorithms. The experimental results show that the algorithm is effective when compared with existing algorithms. Our approach illustrates that there is a significant improvement in average execution time and reduction in waiting time of tasks on queue.     

网络管理中多agent的半在线调度算法

多agent调度算法在基于多agent的网络管理中对任务执行效率起着至关重要的作用.现有的多agent调度算法由于缺乏考虑任务间的依赖关系,使得面对复杂任务系统时会产生大量的网络负载和等待时间.为此,在建立一个适合网络管理任务特点的多agent调度框架的基础上,提出了一种基于任务依赖关系的多agent半在线调度算法.理论分析和测试结果表明,这种半在线调度算法优于已有的全在线调度算法,其性能更接近离线最优调度算法,从而为网络管理任务中多agent的动态调度提供了一种新的途径.     

网格环境下一种可调目标的启发式调度策略

针对网格环境下不同类型的任务执行时间相差较大的问题,提出了基于任务平均执行时间的忍耐度的概念,重新构造了启发式规则,体现了任务QoS的要求;并将这种服务质量的需求与任务完成时间相结合,给出了一个可调节的局部目标函数,实现了一种基于任务完成时间和任务服务质量的启发式调度算法OA-Sufferage;最后,给出了服务率(service ratio)的概念和定义,定量地衡量任务得到的服务质量.实验结果表明,该策略优先调度那些等待时间相对于执行时间较大的任务,提高了任务的服务率;而且可以通过调节局部目标函数中的偏好因子(preference factor),追求任务完成时间和QoS的不同目标,更加适合开放复杂的网格环境.     

基于动态抢占阈值的实时调度

具有抢占阈值的调度算法集非抢占调度和纯抢占调度的特点，既减少了由于过多的随意抢占造成的CPU资源浪费，又保证了一定的任务截止期错失率及CPU资源利用率。已有的工作基本集中于讨论任务集完全给定，任务数、任务的优先级及任务的抢占阈值在调度前已完全确定，而且要求不同的任务具有不同的优先级，提出的具有抢占阈值的调度算法，完全放松了对这些条件的限制，即任务的个数不确定，任务的优先级及其抢占阈值在调度过程中可以动态地变化。最后以常用的LSF调度策略为例，结合动态的抢占阈值进行仿真，仿真结果表明，对于不确定的任务集、任务优先级和抢占阈值，利用具有抢占阈值的动态调度算法，降低了任务截止期错失率、提高了CPU的有效使用率。     

基于放置代价的可重构系统任务统一调度算法

高效的任务调度算法对可重构系统的性能有极大的影响。针对目前可重构系统任务在线调度算法的不足,提出了一种基于放置代价的调度算法。该算法考虑了3种代价,分别为:硬件任务在FPGA上的执行时间、占用的FPGA面积以及FPGA的碎片情况,并且也考虑了软硬件任务的统一调度。在调度过程中,当代价超过设定的阈值时,就拒绝其在FPGA上运行,并由CPU执行其软实现。通过合理地拒绝一些代价较大的任务,能够从整体上提高任务调度成功率。实验表明,同已有算法相比,该算法能够获得更高的任务截止保证率。