容错实时系统可调度性分析研究

实时系统在工业、商业和军事领域中得到了广泛应用,这类系统对响应时间具有严格的要求,尤其是强实时系统,如果不能满足响应时限,将可能导致灾难性的后果。因此在实时系统设计过程中必须提供相应的手段来保证整个系统运行的实时性。可调度性分析是一种验证计算机系统是否满足实时性要求的方法,广泛应用于实时系统的开发过程。但是随着应用需求的不断提高,实时系统的设计也变得越来越复杂,尤其是实时操作系统、容错技术以及分布式计算技术在实时系统中的大量应用,现有的分析方法已无法满足复杂的应用需求。本文以实时控制系统的开发为背景,研究了在采用符合OSEK/VDX标准的实时操作系统,主/副版本任务错误机制,以及在分布式系统环境下,进行系统可调度性分析的方法。本文的工作主要集中在以下四个方面: 1.混合抢占和分组抢占调度下的系统可调度性分析研究。混合抢占和分组抢占调度是OSEK/VDX操作系统规范推荐的两种实时调度策略,目前并未见到针对这两种调度策略的可调度性分析研究。本文分别针对这两种调度策略提出了计算任务最大响应时间的方法,通过对任务最大响应时间和截止时间的比较判定系统的可调度性。为了分析容错机制对系统可调度性的影响,将主/副版本容错机制分别与混合抢占调度和分组抢占调度相结合,提出了容错机制下任务最大响应时间的计算方法,并在此算法基础上给出了系统可承受最小错误间隔的算法。 2.抢占门限调度下的系统可调度性分析研究。抢占门限调度比混合抢占和分组抢占具有更强的灵活性和通用型。但是目前针对这种调度策略的可调度性分析只考虑了系统正常运行的情况,并未考虑容错机制的影响。为此本文对这种调度策略进行了可调度性分析的容错扩展研究,提出了主/副版本容错机制下的任务最大响应时间计算方法。为了获得最优的系统容错性能,还提出了优化遍历算法和启发式算法来计算系统抢占门限优先级分配的最优策略。 3.分布式实时系统的可调度性分析研究。现有的针对分布式实时系统的可调度性分析方法无法在满足分析精确性的同时保证较高的计算性能,在实际应用中无法满足复杂实时系统设计对可调度性分析的性能要求。为解决这一问题,本文针对事务周期不大于其截止时间的情况,提出了线性分布式系统事务端到端最大响应时间和最小响应时间的计算方法。该方法充分考虑了任务和消息的本地、全局依赖关系以及释放抖动的影响,可以获得精确的分析结果。通过关键时刻分析和规范形式转换,降低了算法的计算复杂度。实验表明,本文提出的分布式系统可调度