副版本优先级可提升的全局容错调度算法

在主副版本机制的全局容错调度中,副版本运行窗口短,采用优先级继承策略的副版本响应时间长,容易错失截止期.针对副版本实时性差的问题,提出基于优先级提升策略的全局容错调度算法(fault tolerant global scheduling with backup priority promotion, FTGS-BPP),通过赋予副版本比主版本高的优先级,减少副版本在运行过程中受到的干扰,缩短了副版本的响应时间,改善了副版本的实时性,从而减少了实现容错所需的额外处理器资源.仿真结果表明,和采用优先级继承策略的全局容错调度算法相比,FTGS-BPP在调度相同的任务集时明显降低了处理器资源需求.     

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

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

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

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

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

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

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

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

基于杂交遗传算法的多处理器硬实时容错调度算法

传统的硬实时容错调度算法获得了较好的容错性能,但其任务拒绝率、处理器分配偏差比例以及最早完成时间等性能参数不佳,对此提出一种基于杂交遗传算法的优化方案,并对传统的硬实时容错算法进行优化。采用了中心型调度模型,并采用了任务备份方案来实现容错能力。将任务拒绝率、处理器分配偏差比例以及最早完成时间三个优化参数作为遗传算法适应度目标函数的三个带权分量,对其进行优化,通过遗传算法的杂交与迭代计算获得了优化的结果。最终使用不同的任务数量与处理器数量的组合对本算法与传统算法进行对比试验,结果可看出本算法的3个优化参数明显优于传统算法,且总适应度值亦比传统算法有明显改进。     

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

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

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

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

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

基于软件容错模型,提出了允许容错优先级提升的抢占阈值容错调度算法(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*算法能够有效地提高硬实时系统的容错能力.     

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

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

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

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

单处理器容错硬实时调度算法

高可靠实时系统的用户要求系统在出现硬件或软件错误的情况下仍能在规定的实现要求前输出正确的结果。基于时间冗余的容错实时调度是实时系统容错的主要手段。该文对单处理器容错实时调度进行系统、全面的论述,并给出近年来的一些研究成果。     

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

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

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

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

Non-Preemptive Real-Time Scheduling of Multimedia Tasks

Motivated by the special characteristics of multimedia tasks, we consider non-preemptive scheduling of tasks where there exists no (or very limited) information concerning the tasks before they are released. We present impossibility results and analyze algorithms for non-preemptive scheduling in single processor and multiprocessor systems. To evaluate our algorithm we assume that system obtains a value that is proportional to the processing time of the task whenever a task is completed by its deadline. Competitive analysis is used, where the goal is to keep the total value obtained by an on-line algorithm bounded by a function of the total value obtained by an off-line algorithm. In particular, one set of our results considers the competitive ratio of scheduling algorithm when the length of the tasks is not greater than C_max (and not smaller than C_min ). We show that the performance of a scheduling algorithm is improved dramatically when the release time of the tasks is O(C_max) prior to their deadline; achieving a competitive ratio that is close to one.     

Utilization Bounds for Multiprocessor Rate-Monotonic Scheduling

In this paper, we extend Liu and Layland's utilization bound for fixed priority scheduling on uniprocessors to homogeneous multiprocessor systems under a partitioning strategy. Assuming that tasks are pre-emptively scheduled on each processor according to fixed priorities assigned by the Rate-Monotonic policy, and allocated to processors by the First Fit algorithm, we prove that the utilization bound is (n–1)(2^1/2–1)+(m–n+1)(2^1/(m–n+1)–1), where m and n are the number of tasks and processors, respectively. This bound is valid for arbitrary utilization factors. Moreover, if all the tasks have utilization factors under a value , the previous bound is raised and the new utilization bound considering is calculated. Finally, simulation provides the average-case behavior.     

软件容错模型中反向与正向调度算法研究

为了保证实时系统在发生任务失效时仍旧能够正常地工作,通常采用软件容错模型来提高实时系统的容错能力。本文分析了软件容错模型中的BCE容错调度算法,针对该算法中的反向调度和正向调度两个过程,给出了RMB、DMB、FDMB、EDFB四种反向调度算法和RMF、EDFF两种正向调度算法,并指出了反向调度和正向调度相互协调的特性。将各种算法在BCE算法中进行模拟,结果表明,EDFF正向调度算法能够与四种反向调度算法更好地协调,从而获得比RMF正向调度算法更高的调度性能;模拟结果还表明,四种反向调 度算法在BCE算法中的性能相近。最后,本文得出了RMB（或DMB）反向调度算法与EDFF正向调度算法的组合较适用于软件容错模型的结论。