实时系统容错调度算法综述重点.doc

实时系统容错调度算法综述 学 号 1470832 学生姓名 班 级 计算机技术18班 摘要 本文对容错实时调度常用的基本技术归纳和总结，深入分析和比较了近年来实时容错调度算法，把常见的容错调度算法分类为静态任务调度、动态任务调度和混合任务的调度，的调度算法以及的介绍了的两种容错调度算法 关键词 1 引言 随着实时系统的功能日益强大，应用成本的逐渐降低，实时系统在其应用领域中所处地位迅速提高。如果实时系统无法满足设计要求的运算结果的逻辑正确性和时间正确性，将造成重大的财产损失，甚至人身伤害，导致灾难性的后果。因此，如何保证实时系统具有一定的可靠性以避免灾难性后果的发生，是当前实时系统一个十分重要的研究领域。相对于其它计算机系统而言，实时系统对可靠性要求十分严格。例如，在高炉炼钢的过程中，当错误出现时，实时系统必须能够提供降级服务，以保证能够将钢水排出高炉，因为放弃对高炉的控制将造成巨大的经济损失。因此，实时系统必须采用专门的措施以保证系统可靠性指标的实现。对于安全关键系统中的实时系统，其可靠性的主要考虑是系统的持续工作时间，即系统尽可能连续工作而不出现失效。在这里，失效是指实时系统丧失对安全关键系统的控制能力。 为达到可靠性目标，实时系统的设计人员通常采用容错技术。容错技术主要用于保证系统在出现错误的情况下仍然能够继续运行。近几年来，对容错实时系统的重视程度不断提高，取得了大量有价值的研究成果。目前，容错实时调度算法研究主要集中在理论探讨阶段，致力于设计新颖的资源管理分配策略，在保证系统的时间特性和可靠性的前提下尽可能提高资源利用率，所获得的算法在理论上拥有较高的资源利用率，但运算复杂度较高，要投入实际应用还有待改进。此外，在引入容错策略后，实时系统变得更加复杂，其设计和实现的工作量增加很大，不利于提高实时系统得可靠性。 针对当前容错实时系统研究中存在的问题，有必要设计实用、简单、高效的容错实时调度算法，实现容错调度功能，这对容错实时系统在安全关键系统中的应用具有很大现实意义。 2 常见的容错调度算法 实时容错调度算法根据实时任务的分派和可调度性测试的时机可分为三类 ， 即静态任务调度、动态任务调度和混合任务的调度1]。这里任务的分派是指选择某一个任务到某一处理机上调度的过程；而任务的可调度性测试指的是确定任务是否可以在某一个系统上调度的过程。 表1描述了实时任务的调度分类。其中，(a)表示所有任务的调度和分派都是离线的，在设计阶段进行的，执行严格的时间表，优点在于可预测性好。但由于调度基于简单的调度模型和严格的时间约束，脆弱和缺乏灵活性的。为了克服这种不灵活性，可以在任务进行实际分派时再检测任务的可调度性如(c)。(d )描述的调度方法其可调度性分析和任务分派都是在线进行的事实上，这样的调度分析成了一种接受测试，测试新到来的任务的截止期是否会被错过如果会被错过，则被拒绝调度；否则就进入系统进行调度。显然，这种调度方法是最具有灵活性的，但是在系统负载很重的情况下性能会很差，因此可预测性也很差。最合理的调度方式是(b)中描述的调度方法目前来说基于优先级的调度方式是最能被接受的。 基于以上对实时任务调度的分类，本文对实时容错的调度方法分类如下 2.1静态实时容错调度 静态调度方法中，任务的分配离线进行的，即在实时任务正式在处理机上调度执行前，先把任务在处理机上的分配和调度时间安排好，在任务正式开始执行后按照预先的调度方案执行。这种调度方法主要用于周期任务的调度，它的优点在于能够预先安排好调动，减少任务调度过程中的开销；而缺点在于缺乏灵活性， 在实际的调度中不能够及时地根据系统资源和任务的执行情况进行及时的调整。2-7]提出的算法都是基于静态调度算法的。 可抢占周期任务集的静态容错实时调度的实时任务集模型可以表述：实时任务集S={t1,t2,…tn}，若采用RM作为基本调度算法，任务按周期大小以增序排列(T1T2?Tn)，且各个任务间相互独立。每个任务ti定义为一个四元组Ci, Di, Ti, Pi ，其中，Ci、Di和Ti分别为任务ti的执行时间、时限、周期，且满足Ti=Di。该算法按周期大小定义任务的优先级，周期最短的优先级最高，周期最长的优先级最低，则任务优先级排列如下：P1P2Pn。 下面我们在介绍3种单处理器可抢占周期任务集的静态容错实时调度算[8]：PRA(Private Reservation Algorithm)、CRA(Communal Reservation Algorithm)[9]和FT-RM(Fault-Tolerant RM)算法[10]。 2.1.1 PRA调度 PRA为实时任务预留私有的处理器空闲时间，以保证任务ti在两个连续周期边界[kTi,(k+1)Ti]内能够重复运行(1