基于异构分布式系统的实时容错调度算法

目前文献中研究的实时容错调度算法都是基于同构分布式系统，系统中的所有处理机完全相同。该文首先建立了一个基于异构分布式系统实时容错调度模型，异构分布式系统中的各个处理机均不相同。基于该异构分布式系统模型，该文引入了可靠性代价（reliability cost）概念，并提出两种静态实时容错调度算法（RTFTNO和RTFTRC）用于调度周期性实时容错任务。算法RTFTRC在调度任务时，尽量使系统的可靠性代价最小；而算法RTFTNO在调度实时任务时，没有考虑系统的可靠性代价。该文详细讨论了两种调度算法的性能。性能模拟实验分别比较了两个算法的可靠性代价，超时比率和可调度性；并研究了任务的计算时间与可靠性代价的关系以及调度长度阈值与最小处理机个数的关系。实验结果表明，算法RTFTRC的性能优于算法RTFTNO。     

单机实时系统中的一种混合型实时容错调度算法

目前研究单机实时系统的调度算法文章大多只能调度单一类型的任务。本文在PKSA算法的基础上，建立了一种混合型实时容错模型，提出一种调度算法不仅可以调度有容错需求的周期任务，同时也能够调度无容错需求的周期任务和非周期非实时任务，实现了调度混合型任务的目的。     

单机实时系统中的一种混合型实时容错调度算法

目前研究单机实时系统的调度算法文章大多只能调度单一类型的任务。本文在PKSA算法的基础上,建立了一种混合型实时容错模型,提出一种调度算法不仅可以调度有容错需求的周期任务,同时也能够调度无容错需求的周期任务和非周期非实时任务,实现了调度混合型任务的目的。     

分布式实时系统的容错调度算法

提出了两种分布式实时容错调度算法：副版本后调度算法（ＢＫＣＬ）及无容错需求后调度算法（ＮＦＲＬ）,并研究了算法的时间复杂度,这两种容雕工算法能同时调度具有容错需求的实时任务和无容错需求的实时任务,ＢＫＣＬ和ＮＦＲＬ所产生的调度可保证：在分布式系统中一个节点机失效的情况下,具有容错需求的实时任务仍然可在截止时间内完成,在描述了两个实时容错调度算法之后,分别证明了这两个算法的容错调度正确性。接着,阐述     

NFRL:一种分布系统的实时容错调度算法

在硬实时系统的应用中,如果硬实时任务不能在规定的时限完成,将会产生人员伤亡, 失等严重后果,为了保证在系统出错的情况下,硬实时任务仍然在能戴止时限之前完成,必须研究实时容错技术。本文从实时容错调度算法的角度出发,提出一种基于分布式系统的实时容错调度算法,并研究了该算法的时间复杂度,同时给出一个实例说明该容错调度算法的调度过程。这种容错调算法称为“无容错需求后调度算法（ＮＦＲＬ）,该实时容错调度算法     

软件容错模型中的容错实时调度算法

在软件容错模型的容错实时调度算法中,主部分可执行性的预测精度是影响调度算法性能的关键.针对此问题提出了DPA(deep-prediction based algorithm)和EDPA(EDF-based DPA)算法.算法考虑当前时间至替代部分通知时间之间的任务执行情况,通过构建预测表对待执行主部分的可执行性进行精确预测.当主部分不发生错误时算法根据预测表调度任务. DPA依照预测表中通知时间的先后顺序调度主部分,而EDPA则按照EDF算法调度预测表中的主部分.模拟结果表明,DPA和EDPA较目前同类算法可获得更多的主部分执行时间,降低CPU的消耗.当软件错误率较低、任务周期较短时,算法能够以较小的调度开销获得较高的调度性能.     

实时容错调度算法的自动模拟系统模型与设计

实时容错技术是实时系统中的关键技术之一,而实时容错调度算法则是实时容错研究领域中需要重点研究的问题。传统的实时容错调度算法的性能模拟是通过手工完成的,如果采用自动模拟方法,可以提高模拟实验的效率和准确性。首先给出一个实时容错调度算法的自动模拟系统模型,该模型定义了自动模拟系统中的关键参数。然后,提出了实时容错调度自动模拟算法。最后,研究了该自动模拟系统的软件结构。文章研究的自动模拟系统具重要的指导     

实时容错调度算法的自动模拟系统模型与设计

实时容错技术是实时系统中的关键技术之一,而实时容错调度算法则是实时容错研究领域中需要重点研究的问题.传统的实时容错调度算法的性能模拟是通过手工完成的,如果采用自动模拟方法,可以提高模拟实验的效率和准确性.首先给出一个实时容错调度算法的自动模拟系统模型,该模型定义了自动模拟系统中的关键参数.然后,提出了实时容错调度自动模拟算法.最后,研究了该自动模拟系统的软件结构.文章研究的自动模拟系统具重要的指导意义,可以参考该系统设计其他类型的调度算法的自动模拟系统.该系统的实现可大大节省用于研究实时容错调度算法的时间和费用.     

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

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

基于EDF的分布式系统实时容错调度算法

将分布式系统的任务分配算法与处理器局部调度算法相结合，提出一种主动备份的、基于EDF的分布式系统实时容错调度算法，其特点是主／副版本执行时间可以重叠。给出了该调度算法的任务集可调度的充分条件、任务集可调度所需最小处理器个数的计算方法。模拟结果比较了主动备份容错调度算法与被动备份容错调度算法，结果表明卞动备份算法效率更优。     

基于软件容错的动态实时调度算法

在硬实时系统中,由于任务超时完成将会导致灾难性后果,因而硬实时系统具有严格的时间及可靠性限制条件.目前实时容错调度算法大部分针对硬件的容错,很少考虑软件运行的故障.提出了一种类似EDF基于软件容错的动态实时调度算法EBPA(expectation-based probing algorithm),该算法在任务执行过程中通过基于期望值的若干试探性检测步骤,提高了任务可执行性的预测,尽可能避免了任务早期的错误对后续任务的影响,因此提高了任务的完成率并同时有效地减少了浪费的CPU时间片.通过实验测试,同目前所知的同类算法相比,具有更佳的调度性能-调度成本比.     

基于软件容错的动态实时调度算法

在硬实时系统中，由于任务超时完成将会导致灾难性后果，因而硬实时系统具有严格的时间及可靠性限制条件．目前实时容错调度算法大多针对硬件的容错，很少考虑软件运行的故障．提出了一种类似EDF的软件容错的动态实时调度算法PKSA(Probng-step Algorithm)，本算法在任务执行过程中，通过若干试探性检测步骤，提高了任务可执行性的预测，尽可能地避免了任务早期的失败对后续任务的影响，因此提高了任务的完成率，并同时有效地减少了浪费的CPU时间片．通过实验测试．同目前所知的同类算法相比，具有更佳的调度性能-调度成本比.     

硬实时系统中基于软件容错的动态调度算法

在硬实时系统中,由于任务超时完成将会导致灾难性后果,因而硬实时系统具有严格的时间及可靠性限制条件.目前实时容错调度算法大部分针对硬件的容错,很少考虑软件运行的故障.提出了两种类似EDF(earliest deadline first)的软件容错的动态实时调度算法:PKSA(probing K-step algorithm)和CUBA(changing utilization-based algorithm).两种算法在任务执行过程中,通过若干试探性检测步骤,提高了任务可执行性的预测,尽可能地避免了任务早期的失败对后续任务的影响,因此提高了任务的完成率,同时也有效地减少了浪费的CPU时间片数量.通过实验测试,与目前所知的同类算法相比,具有更佳的调度性能--调度成本平衡性.     

异构分布式系统中基于负载均衡的容错调度算法

提出了基于主/从版本的具有容错功能的进程调度算法HDALF和HDLDF,且分别给出两种算法的时间复杂度并对算法的负载均衡性和节点资源利用率作了讨论.与以往容错调度算法不同的是,此算法是在被动进程复制模式下、适合于异构分布式系统的容错调度算法.而以往的研究都是建立在主从版本进程有相等的负载或执行时间相同的模型基础上,或者仅适合于同构分布式系统.实验结果表明,HDALF算法和HDLDF算法的性能比基于同构分布式模型下的两阶段算法更加优越.并且得出了这样的结果：当系统发生故障前后的负载均衡性权值相等时,在负载均衡和处理机资源利用率方面,HDLDF算法都要优于HDALF算法.     

硬实时系统中基于软件容错模型的容错调度算法

在硬实时系统中,由于任务超时完成将会导致灾难性后果,因此硬实时系统必须具有实时性和可靠性保障.软件容错模型是提高硬实时系统容错能力的一种有效方法.针对硬实时系统中容错优先级两种分配策略存在的不足,基于软件容错模型提出了一种容错优先级可提升的双重优先级分配策略.该方法通过为替代版本分配双重优先级,不仅能够提高硬实时系统的容错能力,同时还能够显著减少任务间的抢占次数.为了获得双重优先级分配的最佳策略,基于任务最坏响应时间的可调度性分析,首先提出了一种最大的双重优先级配置搜索算法(MDPCSA).然后结合MDPCSA算法,提出了一种最优的双重优先级配置搜索算法（ODPCSA）.仿真实验表明,与两种分配策略相比,在提高系统容错能力和降低抢占开销方面更为有效.     

一种实时异构系统的集成动态调度算法

提出了一种实时异构系统的集成动态调度算法.该算法通过一个新的任务分配策略以及软实时任务的服务质量QoS(quality of service)降级策略,不仅以统一方式完成了对实时异构系统中硬、软实时任务的集成动态调度,而且提高了算法的调度成功率.同时,还进行了大量的模拟研究.这些模拟以传统的近视算法为基准,将其应用在实时异构系统集成动态调度时的调度成功率与新算法进行比较,模拟结果表明,在多种任务参数取值下,新算法的调度成功率均高于传统的近视算法.     

异构分布式控制系统中实时任务的调度算法

分布式控制系统是一种应用极为广泛的异构分布式实时系统，系统中同时存在有多种实时任务，如何将这些任务分配到各个处理器上并保证它们的时限是系统关键技术之一．在结合启发式任务分配算法和单处理器任务调度算法的基础上，提出了一种分布式控制系统的调度算法．该算法考虑了各个处理器的负载均衡，同时又能满足所有任务的时限．仿真结果表明了算法的有效性．