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

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

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

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

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

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

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

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

改进的最小空闲时间优先调度算法

最小空闲时间优先(least slack first,简称LSF)算法结合任务执行的缓急程度来给任务分配优先级.任务所剩的空闲时间越少,就越需要尽快执行.然而,LSF算法造成任务之间的频繁切换或严重的颠簸现象,增大了系统开销,并限制了其应用.在调度策略中设置抢占阈值可以减少任务之间的切换,但现有的抢占阈值设置方法因受到固定优先级的限制而不适用于LSF算法.为了减轻LSF算法的颠簸现象,基于抢占阈值的思想,提出适用于LSF算法的抢占阈值分配方法,动态地给每个任务配置抢占阈值.任务的抢占阈值是随着任务执行的缓急程度不同而动态地变化的,而且不受任务个数的限制.仿真结果表明,通过对LSF算法的改进,任务之间的切换大大减少,同时降低了任务截止期错失率.该改进型算法对设计和实现实时操作系统具有一定的参考价值.     

低复杂度的阈值优化实时调度算法

嵌入式实时系统在其CPU及内存资源相对稀缺时,必须采用复杂度低,系统开销小的调度算法.基于阈值的调度算法可以提高任务的调度性,减少任务间的切换,以此减少内存需求和系统开销.提出了基于抢占差值的阈值分配优化算法.算法在最小阈值分配法基础上,从高优先级向低优先级方向设置任务的阈值,为任务集找出一组满足最大抢占差值的阈值分配方案.经过理论分析及实例验证,算法可以显著降低任务的切换次数,并且算法的复杂度优于传统的优化算法.     

基于动态抢占阈值的实时调度

具有抢占阈值的调度算法集非抢占调度和纯抢占调度的特点，既减少了由于过多的随意抢占造成的CPU资源浪费，又保证了一定的任务截止期错失率及CPU资源利用率。已有的工作基本集中于讨论任务集完全给定，任务数、任务的优先级及任务的抢占阈值在调度前已完全确定，而且要求不同的任务具有不同的优先级，提出的具有抢占阈值的调度算法，完全放松了对这些条件的限制，即任务的个数不确定，任务的优先级及其抢占阈值在调度过程中可以动态地变化。最后以常用的LSF调度策略为例，结合动态的抢占阈值进行仿真，仿真结果表明，对于不确定的任务集、任务优先级和抢占阈值，利用具有抢占阈值的动态调度算法，降低了任务截止期错失率、提高了CPU的有效使用率。     

EPTS:一种实时动态电压调整的抢占阈值调度器

低功耗目前已成为嵌入式实时系统设计中非常重要的性能需求。动态电压调度DVS机制通过动态调整处理器电压进而有效降低系统功耗,正在逐渐得到广泛应用。抢占阈值调度策略实现双优先级系统,每个任务具有两个优先级,任务优先级被用于任务之间竞争处理器,而抢占阈值作为任务开始运行后实际使用的优先级,从而减少现场切换次数,降低系统功耗,同时也提高整个任务集合的可调度性。本文提出一种在线节能调度算法EPTS,拓展抢占阈值调度模型,在任务执行过程中动态调节处理器电压,力求在保证任务集合可调度性的前提下尽可能减少系统功耗,提高系统性能。而后在AMDAthlon4处理器和RT-Linux平台上实现了EPTS调度器,实验证明对于实际任务集合能够有效节能,提高了处理器的利用率,改善了RT-Linux的实时性能。     

基于推测的无响应任务自适应容错调度算法

已有的 基于静态的执行失败判定时间阈值 的无响应任务容错调度算法,不能适应大数据处理中心动态的集群负载。针对该问题,提出判定无响应任务执行失败时间阈值自适应调整方法。基于该模型,设计了自适应的无响应任务容错调度算法(AFTS)。AFTS算法通过分析作业规模、单个任务大小和剩余作业推测执行时间等参数,自适应地调整无响应任务判定执行失败的时间阈值,以减少无响应任务对整体作业执行效率的影响,降低作业响应时间。基于开发的原型系统,验证了自适应判定方法,测试了算法的性能。实验结果表明,AFTS算法在作业响应时间等方面优于已有的无响应任务容错调度算法。     

异构集群中基于优先级的任务容错调度算法

提出一种基于任务优先级的容错调度算法,任务的优先级并不是由用户指定,而是由任务的开始时间、执行时间和截止期限决定的。该算法能够容忍异构集群系统中一个节点故障,采用主动/被动副版本相结合的执行方式和重叠技术的备份方式,提高系统资源利用率。通过实验证明了该算法在容错调度中的可靠性和高效性。     

实时调度中条件保证预算的分析

重点研究了固定优先级抢占调度(FPPS)下的条件保证预算(CGB)的可调度性.先引入占用时间和进度的概念,对于具有任意周期和相位的实时资源调度,基于最好情况时间以及最坏情况时间等基础分析技术将周期按照一定规则划分为不同区域并分别加以分析,详细阐述并推理得出计算系统中可以使用的CGB大小的算法.在系统资源可调度性上,提出的计算CGB的方法可以对资源进行更好地配置,提高了资源的有效利用率.     

Improved Task and Resource Partitioning Under the Resource-Oriented Partitioned Scheduling

Coordinated partitioning and resource sharing have attracted considerable research interest in the field of real-time multiprocessor systems. However, finding an optimal partition is widely known as NP-hard, even for independent tasks. A recently proposed resource-oriented partitioned (ROP) fixed-priority scheduling that partitions tasks and shared resources respectively has been shown to achieve a non-trivial speedup factor guarantee, which promotes the research of coordinated scheduling to a new level. Despite the theoretical elegance, the schedulability performance of ROP scheduling is restricted by the heuristic partitioning methods used in the original study. In this paper, we address the partitioning problem for tasks and shared resources under the ROP scheduling. A unified schedulability analysis framework for the ROP scheduling is proposed in the first place. A sophisticated partitioning approach based on integer linear programming (ILP) is then proposed based on the unified analysis. Empirical results show that the proposed methods improve the schedulability of ROP scheduling significantly, and the runtime complexity for searching a solution is reduced prominently compared with other ILP-based approaches as well.

     

Fault-tolerant and real-time scheduling for mixed-criticality systems

The design and analysis of real-time scheduling algorithms for safety-critical systems is a challenging problem due to the temporal dependencies among different design constraints. This paper considers scheduling sporadic tasks with three interrelated design constraints: (i) meeting the hard deadlines of application tasks, (ii) providing fault tolerance by executing backups, and (iii) respecting the criticality of each task to facilitate system’s certification. First, a new approach to model mixed-criticality systems from the perspective of fault tolerance is proposed. Second, a uniprocessor fixed-priority scheduling algorithm, called fault-tolerant mixed-criticality (FTMC) scheduling, is designed for the proposed model. The FTMC algorithm executes backups to recover from task errors caused by hardware or software faults. Third, a sufficient schedulability test is derived, when satisfied for a (mixed-criticality) task set, guarantees that all deadlines are met even if backups are executed to recover from errors. Finally, evaluations illustrate the effectiveness of the proposed test.     

一种能量收集嵌入式系统自适应调度算法

能量收集嵌入式系统(energy harvesting embedded system,简称EHES)的任务调度算法需要考虑能量收集单元的能量输出、能量存储单元的能量水平和能量消耗单元的能耗.实时任务在满足能量约束的条件下,才可能满足时间约束.在这个背景下,传统固定优先级调度算法不再适用于EHES.提出一种基于分组的自适应任务调度算法,它能根据能量收集单元由于能量输出的不确定性而造成的非能量约束情况和能量约束情况,自适应地选择任务调度算法.在非能量约束的情况下,减少任务抢占次数,增强任务的可调度性;在能量约束情况下,减少电池模式切换次数,提高能量存储单元的平均能量水平,从而降低系统能量约束.在一个可进行大范围任务集合仿真的实验环境下对提出的算法进行验证,并将基于分组的自适应调度算法与现有的两个经典算法进行了对比.     

FPTS:一种任务间存在共享资源时的抢占阈值调度算法

受到广泛关注的抢占阈值调度算法能够有效减少现场切换次数,防止不必要的任务抢占,降低资源额外消耗,提高任务集合的可调度性.目前该调度算法的研究工作大多围绕独立任务集合展开,在实际实时系统中任务经常需要互斥访问共享资源,任务之间由于资源共享而导致的相关性对于任务集合的优先级分配和抢占阈值分配都有很大的影响.SRP协议是在实时系统中得到广泛应用的资源访问控制协议,具有死锁避免、提前阻塞、共享任务栈等一系列优良特性.将SRP和抢占阈值调度算法结合起来,提出FPTS调度模型,给出相应的可调度性判定公式,考虑在任务之间使用SRP协议时求解任务抢占阅值分配,最后给出计算抢占阈值分配的伪多项式时间算法.     

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

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

Energy-efficient scheduling of real-time tasks with shared resources

This paper explores the energy-efficient scheduling of real-time tasks on a non-ideal DVS processor in the presence of resource sharing. We assume that tasks are periodic, preemptive and may access to shared resources. When dynamic-priority and fixed-priority scheduling are considered, we use the earliest deadline first (EDF) algorithm and the rate monotonic (RM) algorithm to schedule the given set of tasks. Based on the stack resource policy (SRP), we propose an approach, called blocking-aware two-speed (BATS) algorithm, to synchronize the tasks with shared resources and to calculate appropriate execution speeds so that the shared resources can be accessed in a mutual exclusive manner and the energy consumption can be reduced. Particularly, BATS uses a static low speed to execute tasks initially, and then it switches to a high speed dynamically whenever a task blocks a higher priority task. More specifically, the processor runs at the high speed from the beginning of the blocking until the deadline of the blocked task or the processor becomes idle. In order to guarantee that the deadlines of tasks are met, the static low speed and the dynamic high speeds are derived based on the theoretical analysis of the schedulability of tasks. Compared with existing work, BATS achieves more energy saving because its dynamic high speeds are lower than that of existing work and the processor has less chance to execute tasks at the high speeds. The schedulability analysis and the properties of our proposed BATS are provided in this paper. We also evaluated the capabilities of BATS by a series of experiments, for which we have some encouraging results.     

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

异构分布式实时仿真系统是一类特殊的实时系统,基于改进的SP(spare processor)容错模型(checkpoint-based spare processor,简称CSP)对其容错问题进行了研究.首先,根据仿真系统的特点提出了两个命题,这是后续工作的基础;而后,基于Markov链对仿真任务的最坏反应时间进行了分析,并提出了仿真任务的可调度性分析规则;最后,基于CSP容错模型和上述可调度分析规则提出了异构分布式实时仿真系统的容错调度算法CSP-RTFT.算法的仿真结果表明:该算法较之基于SP模型的算法SP-RTFT可获得更好的稳定性、更高的任务接收率;缺点是资源利用率比PB模型下的算法要低.     

基于RM与EDF的实时混合调度算法研究

通过对实时系统中静态调度算法RM和动态调度算法EDF的研究与分析,针对两种调度算法在实际应用中的问题,提出了一种基于阈值δ的混合调度算法,将RM与EDF调度算法相结合,并从数学角度描述了混合调度算法的可调度性与实时任务的周期、执行时间等属性之间的关系,给出了混合调度算法可调度性的充分必要条件。最后用实验验证了混合调度算法的有效性。     

单调速率调度算法的可调度性分析与仿真

单调速率调度算法是一种经典的周期任务调度算法，在采用单调速率调度算法调度周期任务前对算法的可调度性进行分析和仿真是十分必要的。该文介绍了单调速率调度算法的基本调度规则和可调度的充分必要条件，分别基于Windows平台的多线程机制和实时操作系统SACOS的RMS管理器对单调速率调度算法的可调度性进行仿真，并对仿真结：果进行了评价与分析。仿真结果表明，这两种方法可为单调速率调度算法的可调度性分析提供有益的指导。