硬实时容错调度算法研究

论文摘要

具有容错能力的硬实时系统要求在系统发生局部故障情况下所有任务仍然能在截止期限之前正确完成,否则会导致灾难性的后果,被广泛地应用到航天、军事等关键领域。硬实时容错调度算法通过软件方法构造任务调度秩序并从理论上证明该秩序的实时性和可靠性,属于实时系统的重要研究领域。硬实时系统种类繁多,新的应用需求层出不穷,对原有的硬实时容错调度理论提出了新的挑战。因此,需要对现有的硬实时容错调度算法进行扩充以适应新的需求。主/副版本技术是分布式硬实时系统中重要的容错机制。在该机制中,每个任务的主副版本分别分配到不同的处理机上。FTRMFF （Fault-Tolerant Rate-Monotonic First-Fit）算法利用主/副版本技术作为容错手段,通过首次适应方式按照RMS（Rate-Monotonic Scheduling）优先级依次将任务分配到能同时满足实时性和可靠性的处理机上,是一种经典的分布式容错调度算法。然而,以首次适应方式来分配处理机很难充分挖掘处理机的负载能力。针对这种情况,首先定义空闲因子来量化处理机中空闲资源。然后提出紧凑因子的概念来反映分配到同一个处理机上的任务之间的相容程度。最后提出的基于紧凑因子的启发式硬实时容错调度算法在为任务分配处理机时遵循紧凑因子最大化的原则。该算法能增加周期任务间的相容性,从而提高分布式系统的调度性能。副版本根据触发时间可分为主动副版本和被动副版本。主动副版本与其主版本同时触发,而被动副本则在其主版本失效后才触发,其距离截止期限的时间间隔相对变小。FTRMFF算法的副版本优先级继承策略不利于被动副版本对处理器空闲资源的充分利用。针对这种情况,以最坏响应时间分析为基础,提出基于被动副版本优先级提高策略的硬实时容错调度算法。该算法挪用高优先级任务的空闲时间来处理低优先级任务的容错,从而保证出错的任务满足截止期限的要求。并且根据这种分配策略的性质,设计了优先级提高因子搜索算法。经过研究分析,适当提高被动副版本的优先级能增加被动副版本的可调度性,从而提高处理机利用率。副版本优先级提高策略实质上是考虑到被动副版本执行的紧迫程度较高而提出来的。类似情况也会出现在处理机发生故障之后。具体来说,发生故障时刻所在的周期内的实例相对于后续的实例的执行窗口更小,紧迫程度更高。为实现紧迫实例满足截止期限的目标,提出启发式非紧迫周期延迟策略。该策略尽可能推迟非紧迫实例的执行从而合理挪动空闲资源使得低优先级实例有更多的机会完成其紧迫周期内的执行。另外,具体给出了任务在紧迫周期的最坏响应时间和非紧迫周期内的最大可延迟时间的精确计算方法。对于单处理机硬实时系统,在设计节能容错调度算法时需要考虑动态电压调整技术对瞬时错误发生概率的负面影响将处理器空闲资源全部用于降低工作电压不仅造成替代任务无充裕时间进行容错,而且替代任务执行本身会增加系统能耗开销。为解决这些负面影响,通过定量分析电压/频率与错误概率的关系以期望功耗最小化为目标提出任务最优频率的概念。然后,根据任务在最优频率下的节能效率定义能耗优先级,并提出启发式节能容错调度算法。该算法将处理器空闲时间优先分配给能耗优先级高的任务,从而最大限度地将空闲资源转化为能耗下降。与单处理机系统相比,动态电压调整技术对多处理机系统的影响更加复杂。低功耗技术会延长主版本的最坏响应时间进而破坏副版本的类型,可能造成副版本由主动方式转为被动方式。增加的容错冗余不仅增加硬件代价而且产生更多的能耗。针对这种复杂情况,首先对容错和节能在消耗处理器时间方面进行定量分析。在此基础上,将FTRMFF算法中的容错完成时间测试扩展为节能容错完成时间测试。以节能容错完成时间测试作为可调度性判定准则,提出启发式节能容错硬实时调度算法。该算法在保证系统硬实时性和可靠性前提下,最大化地将剩余空闲资源转化为能耗的降低。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 研究背景、目的及意义
• 1.2 国内外研究概况
• 1.3 研究内容
• 2 基于紧凑因子的分布式调度算法
• 2.1 调度模型与假设
• 2.2 问题的提出
• 2.3 可调度性分析
• 2.4 算法描述
• 2.5 模拟实验
• 2.6 小结
• 3 基于被动副版本优先级提高策略的分布式调度算法
• 3.1 问题的提出
• 3.2 可调度性分析
• 3.3 算法描述
• 3.4 性能分析
• 3.5 模拟实验
• 3.6 小结
• 4 基于非紧迫周期延迟策略的分布式调度算法
• 4.1 问题的提出
• 4.2 可调度性分析
• 4.3 算法描述
• 4.4 实例分析
• 4.5 模拟实验
• 4.6 小结
• 5 基于单处理机的节能调度算法
• 5.1 调度模型
• 5.2 问题的提出
• 5.3 可调度性分析
• 5.4 算法描述
• 5.5 模拟实验
• 5.6 小结
• 6 基于多处理机的节能调度算法
• 6.1 问题的提出
• 6.2 可调度性分析
• 6.3 算法描述
• 6.4 模拟实验
• 6.5 小结
• 7 全文总结与研究展望
• 7.1 全文总结
• 7.2 研究展望
• 致谢
• 参考文献
• 附录 攻读博士学位期间发表及录用的论文目录