基于延迟主动副版本的分布式实时容错调度算法

主/副版本备份技术是分布式系统常用的实时容错调度方法,然而传统的主动方式副版本即使在无处理机故障时也需要在备份处理机上完全运行,增加了处理机消耗.提出一种基于固定优先级调度算法的延迟主动副版本(deferred active backup-copy)备份技术,该技术通过尽量向后调度主动方式的副版本,并在主版本成功执行时终止副版本的执行来减少备份的冗余度.在此基础上,提出一种基于该技术的以最小化处理机数目为优化目标的启发式任务分配算法——基于延迟主动副版本的最佳适应算法DABCBF(deferred active backup-copy based best-fit algorithm).DABCBF在保证系统的实时性和容错能力的前提条件下,通过尽量减少主版本的最坏响应时间来最大程度地减少冗余,以节省处理机.最后通过仿真实验,证明了算法的可行性和有效性.

分布式系统中基于主/副版本的实时容错调度综述

对分布式系统中基于主/副版本技术的实时容错调度算法进行了归纳和总结,从主/副版本执行的关系、任务的调度方式以及调度环境等各个方面深入分析和比较了近年来基于主/副版本的实时容错调度算法,并指出它们各自的优缺点和适应环境。最后指出了本研究领域的未来研究发展方向。

基于被动副版本优先级提高策略的分布式实时容错调度

FTRMFF(fault-tolerant rate-monotonic first-fit)分布式容错算法具有实现简单、调度开销小的优点,但是副版本的优先级继承策略不利于处理器空闲资源的充分利用.针对这个问题并结合各类型任务的最坏响应时间的分析,提出IPPBS(improving priority for passive backup based scheduling)算法.IPPBS算法能在不破坏处理机上已分配任务的可调度性的前提下,适当提高待分配的被动副版本的优先级来缩短响应时间,增加其在现有处理机上的可调度性,从而提高处理器的利用率.在此基础上,给出了具体的优先级提高因子搜索算法.仿真实验验证了IPPBS算法的可行性和有效性,较FTRMFF算法可节约的处理器个数百分比最高可达13%.

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

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

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

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

基于副版本零调整策略的实时任务主副版本容错调度

为了降低硬实时周期性任务主副版本容错调度的副版本调整开销,提出了一种BEDFNENF容错调度算法.采用反向最早截止期优先(BEDF)策略为副版本预分配处理器时间,运行时则采用零调整最早通知时间优先(NENF)策略调度主版本.结果表明,BEDF-NENF算法能够按照最后机会策略调度副版本.当主版本错误概率不大于0.05时,BEDF-NENF算法的副版本调整平均比较次数和副版本调整时间比率均为0,与BEDF-RM算法、BEDF-EDF算法、BEDF-ENF算法的主版本完成率之差约为1%.BEDF-NENF算法不仅能够取得与同类调度算法接近的主版本完成率,而且能够通过省略副版本重新调整操作来降低调度的复杂性,节省调度时间.

副版本延迟的多处理器全局实时容错调度算法

针对多处理器硬实时系统运行过程中任务出错问题,提出一种基于主副版本策略的固定优先级全局容错调度算法FTGS-BD(fault tolerant global scheduling with backup delay)。该算法使用主动副版本和被动副版本,在保证实时性的前提下根据任务需求和硬件性能尽可能的推迟主动副版本的运行,并在不需要副版本响应时回收分配给副版本的资源,从而减少实现容错所需的代价。仿真结果表明,和仅使用被动副版本的全局容错调度算法相比,在调度相同的任务集时,FTGS-BD最多可以减少20%的处理器资源需求,平均减少12%。FTGS-BD能够应用于主副版本总使用率最大值大于1的任务集。

基于延迟副版本的分布式控制系统容错调度算法

针对分布式控制系统中的周期性实时任务,基于版本复制技术设计一种新的容错调度算法.该算法将主动副版本技术、被动副版本技术和副版本重叠技术融合起来,充分利用它们的优点.算法通过延迟副版本的开始执行时间减少主/副版本执行时间的重叠,从而减少副版本的冗余度并提高处理器的利用率.给出了任务集容错可调度性的判别定理和副版本冗余时间的计算方法.在采用以最小化"最坏情况响应时间"的最佳适应方法和首次适应任务分配方法的基础上,给出启发式任务分配算法.最后对算法进行了仿真实验,实验结果表明了算法的有效性和可行性.

基于模拟退火算法的改进主/副版本调度算法

针对异构分布式系统中面向任务优先级约束的调度问题,提出一种基于模拟退火算法的改进主/副版本调度算法SAPB。任务模型以有向无环图DAG表示,该算法共计调度主、副2个版本的任务。在任务优先级排序阶段,采取HEFT的任务排序方法,避免了eFRD等主/副版本调度算法中任务模型描述的局限性问题;在任务处理器分配阶段,采取模拟退火算法搜索满足截止时限条件下具有更高可靠性的调度结果,并且采取多一重备份策略以解决处理器数量相对较少时任务优先级约束带来的副版本调度易失败问题。最后,通过随机生成的DAG图进行仿真实验,结果表明,相比eFRD等算法SAPB具有更优的副版本可调度性和更高的系统可靠性。

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

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

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

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

异构分布式系统中实时周期任务的容错调度算法

提出一个基于抢占性实时周期任务的可靠性调度模型,该模型与现有可靠性模型相比充分考虑了单处理机故障容错情况下的系统可靠性,因而更加接近现实和精确.在此基础上,提出一个基于异构分布式系统的实时容错调度算法IRDFTAHS,IRDFTAHS算法以提高系统的可靠性为目标来进行任务的分配,从而在不增加硬件代价的前提条件下通过调度增加了系统的可靠性.该算法同时支持主动和被动两种方式的副版本,使得容错调度算法具有更大的灵活性.最后,通过仿真实验对IRDFTAHS和现有的调度算法在几个方面进行比较.实验结果表明,IRDFTAHS算法的综合性能优于现有算法.

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

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

面向容错的对地观测卫星实时任务调度研究

提出一种面向容错的对地观测卫星任务调度模型,该模型采用主版本/副版本技术可以实现对任意时刻一颗卫星失效时的容错.在容错调度模型的基础上,提出了一种卫星容错调度算法FTSS.FTSS采用重叠技术,有效提高了卫星资源利用率.此外,FTSS采用了任务合成策略可以有效减少实际执行任务的个数从而进一步提高系统的可调度性.为了验证FTSS算法的性能,本文通过模拟实验对FTSS与其它3个基准算法进行了比较分析.实验结果表明FTSS优于其它算法,适合卫星实时任务容错调度.

虚拟化云平台中实时任务容错调度算法研究

为了在云平台下满足实时系统的高可靠性要求,提出了一种虚拟化云平台中的容错调度算法(FSVC,fault-tolerant scheduling algorithm in virtualized clouds),FSVC通过主副版本方法来实现对物理主机的容错,采用副版本重叠技术与虚拟机迁移技术来提高算法的调度性能。为了达到容错的要求,分析了这2种技术应满足的约束。此外,FSVC中包含了一种两阶段策略以进一步提高算法性能。大量仿真实验表明,在虚拟化云平台中,FSVC能有效地提高系统可调度性与资源利用率。

异构分布式系统混合型实时容错调度算法

基/副版本技术是实现实时分布式系统容错的一个重要手段。提出了一种异构分布式混合型容错模型,该模型与传统的异构分布式实时调度模型相比同时考虑了周期和非周期调度任务。在此基础上给出3种容错调度算法:以可调度性为目的SSA算法、以可靠性为目的RSA算法、以负载均衡性为目的BSA算法。算法能够在异构系统中同时调度具有周期和非周期容错需求的实时任务,且能够保证在异构系统中某节点机失效情况下,实时任务仍然能在截止时间内完成。最后从可调度性、可靠性代价、负载均衡性、周期与非周期任务数及任务周期与粒度5个方面对算法进行了分析。模拟实验结果显示算法各有优缺点,所以在选择调度算法时应该根据异构系统的特点来选择。

面向硬实时系统的容错调度算法研究

目前基于软件容错模型的调度算法大部分都是针对如何提高主版本可执行性的预测精度,很少考虑如何提高主版本的完成率.基于这一问题,本文提出一种基于软件容错模型的实时调度算法(kernel),该算法有选择地重新执行某些失败的主版本并允许其运行在更高的优先级别上,尽最大努力地提高了主版本的完成率,改善了输出结果的计算精度.仿真实验表明,与同类算法相比,kernel算法在提高系统容错能力方面更为有效.

异构平台实时任务的可用性提升容错调度算法

随着互联网+、云计算以及大数据等领域的迅速发展,异构平台成为部署科学计算、工业控制、云存储等关键应用的重要平台.由于平台内处理机性能及软硬件体系结构的异构性,异构平台表现出良好的可扩展性与高性价比.但是平台规模扩大和系统应用日趋复杂导致异构平台上实时任务的可调度性变差,系统可用性降低.针对此问题,提出了一种异构平台实时任务的可用性提升容错调度算法(availability improving fault-tolerant scheduling algorithm,AIFSAL).以处理器利用率和可用性成本为依据设计任务调度整体框架结构、处理机、任务以及调度模型;结合可用性成本设计算法并通过主副版本备份(primary/backup copy,PB)方法实现容错,任务副版本根据处理器利用率不同选择被动或重叠方式执行以减少系统冗余开销,提高可调度性,调度中无论任务主、副版本均优先选择可用性成本低的处理机以提高系统可用性;对任务分配情况和可调度性进行理论分析以证明AIFSAL的可行性.仿真实验与比较分析表明,AIFSAL较可用性约束(availability approached task scheduling algorithm,AATSAL)算法、单调速率扩展(task partition based fault-tolerant rate-monotonic,TPFTRM)算法以及最早完成时间(MinMin)算法在不降低可调度性的基础上有效地提升了系统可用性,减少了系统综合开销,综合性能提高显著.

混合关键任务可靠调度方法与调度性分析

为了解决云计算环境下混合关键性任务的可靠调度问题,提出了一种基于主副版本两阶段的混合关键任务可靠调度方法.算法首先对需要调度的混合关键性任务进行优先级划分,按照调度截止期最短的原则将主版本任务调度到目标虚拟机上,对副版本任务按照复制成本最低的原则使用重叠方法进行调度;再对调度到不同虚拟机上的主副版本任务进行可调度分析,对于不能满足分析的任务启动更高关键性等级进行处理.实验结果表明了混合关键任务可靠调度方法具有较高的可靠性和负载平衡能力.

异构分布式系统动态实时容错调度启发式算法

传统的异构分布式实时调度算法基本没有考虑任务的动态特性。提出一种非周期不可抢占式异构分布式的动态容错模型,在该模型上基于不同调度需求给出两种不同容错调度算法:DRFSA(Dynamic and Reliability-driven of hybrid with Fault-tolerant Scheduling Algorithm)算法与DSFSA(Dynamic and Schedulability-driven of hybrid with Fault-tolerant Scheduling Algorithm)算法。DRFSA算法以提高可靠性代价为调度目标,通过合理调度提高系统可靠性。DSFSA算法以可调度性为调度目标,通过减少任务执行时间来增加系统可调度性。算法能够在异构系统中调度动态的实时任务,且能够尽可能响应任务需求。