异构分布式系统中一种新型主副版本调度算法

针对异构分布式系统中处理器数量相对较少时优先级约束条件带来的副版本调度易失败问题，提出一种新型高可靠性主副版本调度算法（HRPB）。任务模型以有向无环图（DAG）表示，该算法共计调度主、副两个版本的任务。在任务优先级排序阶段，根据任务执行时间及截止时限来制定新指标平均最晚开始时间（ALST）进行排序；在任务处理器分配阶段，采取多一重备份策略以解决处理器数量相对较少时优先级约束条件带来的副版本调度易失败问题，并且改进了副版本调度时的可靠性指标计算方法。通过随机生成DAG图进行算法仿真测试，实验结果表明，HRPB比eFRD具有更优的副版本调度成功率、更高的系统可靠性。     

基于HEFT和CPOP的相关任务表调度算法

DAG任务调度是当前研究的热点,DAG任务模型中任务的调度顺序一方面会影响用户服务满意质量,另一方面也会影响云服务资源的利用率,高效的任务调度算法能够使多核处理器的资源分配和并行计算能力更强.表调度算法HEFT算法以及CPOP算法在相关任务调度中存在效率较低等问题.本文基于HEFT算法和CPOP算法,提出了一种相关任务调度模型和相关任务调度算法IHEFT算法,对任务排序和任务调度两个方面进行改进.任务排序阶段,以任务的方差以及平均通信代价作为排序的依据;任务调度阶段,对满足任务复制条件的结点进行任务复制.实验证明,IHEFT算法在任务调度跨度、任务调度平均等待时间以及平均Slack值方面均优于HEFT算法和CPOP算法.     

主桙副版本模型中预分配容错实时调度算法

实时系统中任务的超时完成可能导致灾难性后果,因此要求系统具备容错处理能力,以保证系统出错后的实时性及可靠性。主/副版本模型是提高实时系统容错能力的有效技术。传统的容错实时调度算法通过为副版本预留处理器时间来实现软件容错,为副版本预留的处理器时间在系统运行过程中需动态调整,增加了系统的容错调度开销。提出一种基于res‐backw ards‐RM 预分配子算法的容错实时调度算法BCE*,通过限制预分配过程中高优先级任务的抢占条件,在不影响系统可调度性的同时可以有效避免副版本预留时间的动态调整,降低系统的容错调度开销。仿真实验验证了BC E*算法的可行性及有效性,且在系统出错概率及主版本负载较低的环境下,BC E*算法对系统容错调度开销的优化效果更显著。     

副版本不可抢占的全局容错调度算法

容错是硬实时系统的关键能力,容错调度算法可以在有错误发生的情况下满足任务的实时性需求.在主副版本机制的容错调度算法中,主版本出错后留给副版本运行的时间窗口小,副版本容易错失截止期.针对副版本需要快速响应的问题,提出副版本不可抢占的全局容错调度算法FTGS-NPB（fault-tolerant global scheduling with non-preemptive backups）,赋予副版本全局最高优先级,使副版本在主版本出错后可以立刻获得处理器资源,并且在运行过程中不会被其他任务抢占.这样,副版本可以在最短时间内响应.分别基于截止期分析和响应时间分析建立了FTGS-NPB的可调度性测试,并分析了两种可调度性测试分别适用于不同的优先级分配算法.仿真实验结果表明,FTGS-NPB可以有效地减少实现容错的代价.     

一种云工作流任务调度能效优化算法

工作流任务执行时带来的高能耗不仅会增加云资源提供方的经济成本,而且会降低云系统的可靠性。为了满足截止时间的同时,降低工作流执行能耗,提出一种工作流能效调度算法CWEES。算法将能效优化调度划分为三个阶段：初始任务映射、处理器资源合并和任务松驰。初始任务映射旨在通过任务自底向上分级排序得到任务调度初始序列,处理器资源合并旨在通过重用松驰时间合并相对低效率的处理器,降低资源使用数量,任务松驰旨在为每个任务重新选择带有合适电压/频率等级的最优目标资源,在不违背任务顺序和截止时间约束前提下降低工作流执行总能耗。通过随机工作任务模型对算法的性能进行了仿真实验分析。结果表明,CWEES算法不仅资源利用率更高,而且可以在满足截止时间约束下降低工作流执行能耗,实现执行效率与能耗的均衡。     

对等网络环境下多目标任务容错调度方法研究

为了加强网络环境的可靠性、强化系统运算性能,提出对等网络环境下多目标任务容错调度方法.使用PB算法对处理器进行容错处理,划分任务主、副版本,通过分析任务相应版本与所在处理器的运行时间,构建任务模型与故障模型.拟定多目标任务不同开始时间与时限,通过自适应策略拟定启发式多目标任务容错分配策略,将多目标任务转换为回路任务.设定回路任务的数量与主版、副版本在普通处理器内的运行时间,判断调度序列内任务,计算其在处理器内需要消耗的时间,将结果对比之前拟定的时间判断是否调度成功,成功则启动副版本迭代计算.实验结果表明,所提方法不会因为网络节点数量不同,出现大量任务调度失败的问题,提高了系统性能和网络环境安全.     

一种改进的优先级列表任务调度算法

异构多核处理器任务调度是高性能计算领域的重要问题。针对优先级列表调度算法中存在的优先级排序方法失当、调度结果不理想的问题,提出一种改进的优先级列表任务调度算法。该算法对传统优先级列表任务调度中以任务执行时间平均值作为参数的优先级计算方式进行优化,提出一种基于异构核性能差异性、依赖任务特征加权优先级的排序方式。在此基础上,以当前格局下每个任务的向后关键路径执行时间为权值作为任务分配到处理器内核的依据,克服贪心思想在内核选择中带来的局部最优解问题。此外,在任务分配阶段利用任务复制和区间插入技术,缩短任务最早开始时间,提高处理器利用率。实例分析和模拟实验结果表明,该算法可有效降低任务的执行时间,能发挥异构多核处理器优势。     

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

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

基于最小化传输和完成时间的多DAG调度

针对云计算环境下多个有向无环图(DAG)工作流的调度问题,提出一种基于最小化数据传输时间和任务完成时间(LTCT)的算法,用于处理具有相同优先级的多个DAG工作流之间的调度问题。在多个DAG优先级各不相同时的情况下,给出多优先级多DAG的混合调度算法。实验结果表明,LTCT算法较E-Fairness算法在保证多DAG调度公平性的基础上,能避免额外的数据传输开销,有利于缩短整个工作流的执行Makespan,提高资源的利用率。     

异构集群系统中具有QoS 需求的实时任务容错调度

容错调度是调度问题中一个重要的研究内容,是提高系统可靠性的有效手段.目前已有很多集群系统中实时任务的容错调度算法,但是这些算法都没有考虑到任务的QoS需求问题.提出了一种异构集群系统中具有QoS需求的实时任务容错调度算法FTQ(fault-tolerant QoS-based scheduling).该算法采用主版本/副版本(primary/backup,简称PB)技术,综合考虑了任务的时间限制、任务的QoS需求、系统的可靠性和系统资源的利用率,能够自适应地根据系统负载情况动态地调整任务的QoS级别和副版本的执行模式,从而提高了系统的灵活性、可靠性、可调度性和资源的利用率.对系统的可靠性进行了定量分析,并将其引入到容错调度算法中,提高了系统的可靠性.同时,在调度过程中尽量提前主版本的开始时间,推迟副版本的开始时间,以使任务的副版本采用被动执行模式或者使任务主版本和副版本的重叠部分尽量少,提高了资源的利用率.此外,采用了副版本重叠技术,并分析了副版本的最晚开始时间及其约束条件,提高了任务的调度成功率.通过大量的模拟实验,对FTQ,NOFTQ和DYFARS算法进行了比较.实验结果表明,FTQ算法的性能优于其他方法,具有更好的调度质量.     

异构分布式实时系统中对具有前后依赖关系任务的基于动态可变调度距离容错调度算法

目前的主副版本容错调度算法大多没有考虑任务间的前后依赖关系,但实际中很多任务是具有前后依赖关系的。本文提出了一种基于主副版本动态可变调度距离的任务容错调度算法,该技术通过比较任务间的最晚开始执行时间与最早开始执行时间的差值,安排任务副版本的调度,并且基于此设计了可用于具有前后依赖关系任务调度可重叠技术。本文提出的基于动态可变调度距离的容错调度算法在尽可能让任务最早完成的情况下,提高系统的可靠性,并且优先调度关键路径任务,降低了系统的容错开销。最后通过实验证明本文算法的有效性和优异性。     

云环境下周期和非周期混合实时任务双容错调度算法

云环境中的处理机故障已成为云计算不可忽视的问题,容错成为设计和发展云计算系统的关键需求。针对一些容错调度算法在任务调度过程中调度效率低下以及任务类型单一的问题,提出一种处理机和任务主副版本分组的容错调度方法;并给出了副版本可重叠执行的判定方法,以及任务最坏响应时间的计算公式。通过实验和分析表明,和以前算法相比,将处理机分成两组分别执行任务主版本和任务副版本,减少了任务调度所需进行可调度测试的时间,增加了副版本重叠执行的机会,减少了所需的处理机个数,对提高系统处理机的利用率和容错调度的效率具有重要的意义。     

基于EDF的分布式控制系统容错调度算法

现有的分布式实时系统的容错调度算法要求系统中所有任务的周期相同且等于其时限,而实际中任务的周期常常是互不相同的.根据控制系统中任务的特点,结合任务分配算法与处理器的调度算法,提出了基于基版本/副版本技术和EDF算法的容错调度算法.该算法不要求任务的周期都相同,并通过设置基版本/副版本任务时限控制它们的执行时间不重叠,给出了基版本/副版本任务时限的设置方法,并对任务集的可调度性进行了分析.当任务集可调度时,给出其最大利用率和最小处理器个数的约束条件.最后给出一个仿真实例,结果表明了算法的有效性.     

Hadoop平台下改进的推测任务调度算法

研究对比Hadoop平台下默认的推测任务调度算法和异构环境下LATE调度算法的优势和不足,提出了一种基于Hadoop集群的改进的推测任务调度算法.该算法以节点历史信息对Reduce任务各阶段比例进行动态调整和更新,并对任务实时处理速率进行局部平滑处理来提高预估任务剩余完成时间的准确性,最后采用MCP模型对备份任务有效性进行验证.通过实验结果分析可知:该算法能够有效提升备份任务成功率,减少作业完成时间.     

染缸排产建模及滑动时间窗启发式调度算法

针对染缸排产问题约束复杂、任务规模大、排产效率要求高的特点,为了提高问题模型和算法在实际场景中的适用性,建立了染缸排产增量调度模型,提出了滑动时间窗启发式调度（STWS）算法。该算法以最小化延误代价、洗缸成本、染缸切换成本为优化目标,使用启发式调度规则,按照优先级顺序调度产品;对于每个产品的调度,先用动态拼缸算法和拆缸算法进行批次划分,然后调用批次最佳排序算法调度批次。使用某染纱企业车间实际生产数据仿真调度,所提算法可在10 s内完成月度计划的调度。相对于人工排产方式,所提算法提高了排产效率,显著优化了三个目标,在增量调度中洗缸成本和染缸切换成本也有明显优化。实验结果表明所提算法具有很好的调度能力。     

容错多处理机中一种高效的实时调度算法

针对基于主副版本容错的多处理机中独立的、抢占性的硬实时任务,提出了一种高效的调度算法——TPFTRM(task partition based fault tolerant rate-monotonic)算法.该算法将单机实时RM 算法扩展到容错多处理机上,并且调度过程中从不使用主动执行的任务副版本,而仅使用被动执行和主副重叠方式执行的任务副版本,从而最大限度地利用副版本重叠和分离技术提高了算法调度性能.此外,TPFTRM 根据任务负载不同将任务集合划分成两个不相交的子集进行分配;还根据处理机调度的任务版本不同,将处理机集合划分成3 个不相交的子集进行调度,从而使TPFTRM 调度算法便于理解、实现以及减少了调度所需要的运行时间.模拟实验对各种具有不同周期和任务负载的任务集合进行了调度测试.实验结果表明,TPFTRM与目前所知同类算法相比,在调度相同参数的任务集合时不仅明显减少了调度所需要的处理机数目,还减少了调度所需要的运行时间,从而证实了TPFTRM 算法的高效性.     

实时多处理机系统BEST-FIT启发式容错调度

本文从有效利用资源的角度出发,提出了一种以最小化处理机数目为优化目标的Best-Fit启发式容错调度算法。该算法采用主/副版本备份技术和副版本的主动运行方式与被运行方式相结合的方法,将实时任务的主版本和副版本调度到不同处理机上运行;并且按照Best-Fit启发式策略为实时任务主版本寻找“最佳满足”处理机,使尽可能多的实时任务副版本以被动方式运行。算法既保证了系统的实时性和容错性,也节约了处理机。分析和仿真结果均证明了算法的有效性。     

云计算中基于优先级和费用约束的任务调度算法

针对云计算中的服务质量保证问题,提出一种基于优先级和费用约束的任务调度算法。该算法通过计算任务优先级和资源服务能力,分别对任务和资源进行排序和分组,并根据优先级高低和服务能力强弱建立任务组和资源组间的调度约束关联;再通过计算任务在关联资源组内不同资源上的完成时间和费用,将任务按优先级高低依次调度到具有任务完成时间和费用折中值最小的资源上。与Min-Min和QoS-Guided-Min算法的对比实验结果表明,该算法具有良好的系统性能和负载均衡性,并降低了服务总费用。     

分布式控制系统中多种混合任务的容错调度

分布式控制系统中存在有强实时、软实时和非实时等多种实时性的任务,其中强实时任务必须在其时限前完成,否则会出现灾难性后果,因此必须为分布式控制系统提供一定的容错能力。首先给出了用于调度多种实时性任务的单处理器调度算法——双优先级队列调度算法,并分析算法的可调度性条件。针对分布式控制系统,考虑基版本与副版本的执行时间不同时,结合版本复制技术和单处理器调度算法提出了一种新的容错调度算法。分析了算法的可调度行,给出了可任务集的可调度条件判断方法和基版本任务时限的设置方法。在此基础上,采用启发式静态任务分配算法,保证各处理器的负载均衡。本算法在保证任务容错可调度的条件下,可提高系统中各处理器的利用率,仿真结果表明该算法是有效的。