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

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

容错优先级可提升的抢占阈值容错调度算法

基于软件容错模型,提出了允许容错优先级提升的抢占阈值容错调度算法(extended fault-tolerantfixed-priority with preemption threshold,简称FT-FPPT*).该算法能够在抢占式容错调度算法(fault-tolerantfixed-priority preemptive,简称FT-FPP)和抢占阈值容错调度算法(fault-tolerant fixed-priority with preemptionthreshold,简称FT-FPPT)无法提高系统容错能力的情况下,进一步提高系统的容错能力.为了获得系统中任务优先级分配的最佳策略,基于任务最坏响应时间的可调度性分析,提出了一种最优的优先级配置搜索算法(priorityassignment search algorithm,简称PASA).经过深入分析和实验证明,与FT-FPPT算法相比,FT-FPPT*算法能够有效地提高硬实时系统的容错能力.     

面向多处理器的实时周期任务容错调度算法研究

主副版本策略是多处理器系统实时任务调度中处理容错问题的一种重要方式.根据分布式控制系统的特点,本文提出一种改进的FTRMBF算法-PR-FTRMBF,以提高系统周期任务的可调度性.在FTRMBF等已有的调度算法中,当没有处理器分配给当前副版本时,将为副版本分配新的处理器;本文提出的改进算法则以回溯的方式重新分配主版本.在保证系统实时性能和容错能力的前提下,节省了处理器数目.仿真实验表明,与FTRMBF算法相比,改进算法显著提高了系统任务的可调度性.     

基于改进型统一调度算法改善任务集的可调度性

实时系统要求任务在最差情况下能在其截止时间前获得结果,若超过了其截止时间,也会认为是错误的行为,所以改进任务可调度性分析、提高任务集可调度性尤其重要。统一调度能结合固定优先级调度的优点,防止不必要的抢占,降低资源额外销耗,能够提高任务集合的可调度性;但其任务的可调度性分析方法过于粗糙,影响任务最差响应时间分析的结果,降低了任务集的可调度性。针对存在的问题,基于统一调度,增加任务运行阶段数,重新建立任务模型,并提出通过分配任务抢占阈值、调整运行阶段的抢占阈值与长度,优化任务可容忍阻塞,改善任务集可调度性的算法。最后,实验表明,与统一调度算法及其他算法相比,所提出的调度算法能够有效改善任务集的可调度性。     

多处理器硬实时系统的抢占阈值调度研究

在实时系统中,抢占在提高系统灵活性的同时带来额外的系统开销,特别在多处理器平台上抢占导致的作业迁移会造成相当大的性能下降,减少不必要的抢占是硬实时系统研究的重要方向.抢占阈值调度是处于抢占调度和不可抢占调度之间的一种混合调度方法,在保持调度能力的基础上限制抢占.基于截止期分析建立了多处理器硬实时系统抢占阈值调度的可调度性判定条件,针对抢占阈值调度提出一种改进的优先级分配算法OPA-MLL,并建立了抢占阈值分配(preemption threshold assignment,PTA)算法.仿真结果表明,采用OPA-MLL算法和PTA算法分别给任务集分配优先级和抢占阈值时,可调度任务集比率明显提高,同时能最大程度限制抢占次数.     

不可抢占式EDF调度算法的可调度性分析

现有的不可抢占式EDF调度算法的可调度性分析判定条件限定实时任务的截止期必须等于其周期,限制了它的使用范围。论文突破这一限制,提出了更具一般性的可调度性分析判定充要条件。通过对可调度性判定充要条件的分析,提出了基于不可抢占式EDF调度算法的周期性实时系统可调度性分析算法。     

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

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

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

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

一种混合优先级的防危调度算法

为增强实时系统任务过载时的防危性,提出一种混合优先级的防危调度算法,其优先级由相对截止期优先级和相对松弛度优先级组成,通过相对松弛度预测任务的可完成性,并采用完全抢占方式防止处理器资源的竞争抖动。仿真结果表明,该算法可充分利用处理器资源,能在发生瞬时过载时有效降低任务的截止期错失率。     

抢占阈值调度算法的分析与研究

本文详细论述了应用于静态优先级实时系统的抢占阈值调度算法。描述了算法实现和任务集合可调度性判定公式的推导,分析了算法的性能特点,阐述了抢占阈值调度是静态优先级嵌入式实时系统开发中调度算法的合适选择。     

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

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

Aperiodic servers in a deadline scheduling environment

A real-time system may have tasks with soft deadlines, as well as hard deadlines. While earliest-deadline-first scheduling is effective for hard-deadline tasks, applying it to soft-deadline tasks may waste schedulable processor capacity or sacrifice average response time. Better average response time may be obtained, while still guaranteeing hard deadlines, with an aperiodic server. Three scheduling algorithms for aperiodic servers are described, and schedulability tests are derived for them. A simulation provides performance data for these three algorithms on random aperiodic tasks. The performances of the deadline aperiodic servers are compared with those of several alternatives, including background service, a deadline polling server, and rate-monotonic servers, and with estimates based on the M/M/1 queueing model. This adds to the evidence in support of deadline scheduling,versus fixed priority scheduling.     

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

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

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

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

突发性故障模式下实时任务的优先级分配策略

在容错实时系统中,可调度性分析是确保实时任务在限定时间内完成的重要手段。分析了突发性故障模式的可调度性问题,针对该故障模式下已有策略的不足,设计了优先级分配策略,并根据策略的性质实现了容错优先级变迁因子的搜索算法。深入的分析和实验证明,这种策略能够有效地提高系统的容错能力。     

CAN总线中改进的EDF调度算法可调度性分析

针对于CAN总线的调度问题,因现有的平均分区EDF调度算法在对于优先级反转问题上收效甚微,从而导致消息缺乏一定的可调度性,故提出一种改进的基于幂函数分区的EDF算法;同时借助量化误差的概念,对该调度算法进行可调度性分析,充分论证了在该调度算法下,消息可调度的判定条件;采用CANoe平台进行实验仿真,对比平均分区EDF调度算法和双幂函数分区EDF调度算法,经试验测试验证了双幂函数分区EDF调度算法的可行性和优越性,改善了消息的最坏响应时间,提高了CAN网络通讯的实时性。     

容错优先级混合式分配搜索算法

在实时系统中,由于任务未能及时产生正确结果将导致灾难性后果,容错对于实时系统的有效性及可靠性至关重要.基于最坏响应时间计算的可调度性分析,提出了一种容错优先级混合式分配搜索算法.这种算法通过允许替代任务既能运行在高优先级别上,又可运行在低优先级别上,有效地提高了系统的容错能力.通过实验测试,与目前所知的同类算法相比,在提高系统容错能力方面更为有效.     

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

针对分布式实时系统,在分析了单处理调度算法的基础上,结合版本复制技术和首次适应方法,给出了一种容错调度算法。分析了算法的可调度性,给出任务的可调度性条件。在满足任务容错可调度的情况下,以提高处理器的利用率为目标,对基版本时限进行了优化,给出了基版本优化时限的求取算法。仿真结果表明,本文算法将可以得到比FTEDFFF和FTRMFF更高的处理器利用率。     

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

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