实时系统最坏执行时间分析及测试

殷锋社，汤小明

（陕西工业职业技术学院，陕西咸阳，712000中航工业西安飞行自动控制研究所，陕西西安，710075）

0 引言

实时系统指能够在指定时间内完成一定的计算和处理功能，并对外部事件作出响应的计算机系统。实时系统的正确性不仅取决于其输出结果的正确性，还取决于产生输出结果的时间的正确性。根据实时系统对时间性要求的不同，实时系统可分为软实时系统和硬实时系统。在软实时系统中，未在规定的时间内完成某项指定的功能或对外部事件作出响应，将会降低系统的性能，如视频点播系统（VOD）等。而在硬实时系统中，不满足系统的时间特性要求则可能引起重大的灾难性后果，如飞行控制系统。控制律设计是飞行控制系统中非常重要的组成部分，在系统设计的最初，对控制算法设计的实时性进行分析及测试，是控制算法设计中非常重要的一个内容。

1 程序最坏执行时间

静态最坏时间分析在考虑程序所有可能的输入，系统状态和软硬件间交互的前提下，对软件和硬件进行数学建模来分析确定程序的最坏执行时间，而不用真实地运行程序。静态程序最坏执行时间分析开始于上世纪八十年代，历经二十多年的发展，取得了显著的成果，已经成为实时系统的一个重要研究领域。

WCET 分析包括动态度量、静态分析和混合方法共3 种方法。

动态度量方法就是直接运行程序以测量程序的执行时间，而由于通过验证所有的输入条件来测量最坏执行时间通常难以实现，动态度量方法很难保证所得到结果是安全的，极可能会低估系统的最坏执行时间。

混合方法是既包括静态分析也包括动态度量的方法。该方法首先对程序进行分析，根据分析结果进行测试，或者先度量，然后在度量的基础上静态计算程序的WCET 值。

静态分析方法根据程序的流信息，针对运行程序的处理器特性估算出程序的最坏执行时间。而由于程序流信息分析的复杂性，特别是现代处理器体系架构大都采用Cache 和流水线，超标量等技术，其建模非常复杂，静态分析和计算也非常复杂。但静态分析方法能够保证得到的结果是安全的，而且能够不运行程序就获得结果，从而成为程序最坏执行时间WCET 分析研究的主流。

2 静态WCET 分析

静态WCET 分析依赖于程序的模型和时间行为特性。静态WCET分析必须是准确而且安全的。对程序WCET 的低估可能导致程序在规定时间内不能完成所分配的工作，造成不可预知的后果。而过高的WCET 分析则丧失其作用并造成硬件资源的浪费。为了实现以上目的，静态WCET 分析主要分为了三个阶段：流分析，低层分析和WCET 计算。

2.1 流分析

流分析用于分析程序中可能及不可能的程序流信息。比如说，哪些函数可能会被调用，循环的迭代次数，条件判断语句之间的相关性等。分析可以基于源代码，也可以基于目标代码或中间代码。流分析又可以大致分为以下三个阶段：

a)程序信息提取。程序流信息的提取阶段主要是对程序的分析，抽象提取法是本阶段使用的典型方法之一。抽象提取法是在不执行程序的前提下，利用程序所有可能的输入分析程序的行为特性。

b)程序结构信息表示。提取所得的程序流信息可以用图、语法树或程序代码的形式表示，表示的方式应考虑到不仅便于阅读，而且便于工具自动处理。

c)信息计算的转化。在完成信息的表示后，需要将表示形式转化为一种计算方式。在转化过程中，可能需要将一些不会影响分析安全性的因素撇弃。

2.2 低层分析

由于控制算法的最终实现与底层硬件也是密切相关，因此需要针对目标代码根据目标硬件获取算法程序的实际行为特性，称为低层分析。相对而言，以上所讲的流分析也称为高层分析。低层分析又可以分为全局低层分析和局部低层分析。

a)全局低层分析。全局低层分析主要包括高速缓存（Cache），流水线（pipeline）及动态分支预取等的分析。对高速缓存，需要针对缓存的类型是数据缓存还是指令缓存，分析缓存的替换（调度）策略，每一行的大小，访问某一行时的加载延迟等。对动态预取指令的分析包括预取缓冲区的大小，替换策略以及动态预取失败后的延迟等。

b)局部低层分析。局部低层分析一条单独的指令及其临近指令执行时间的硬件特性，如管道重叠，存储器的存取速度，指令或数据的可缓存性(Cacheability)等。

2.3 静态WCET 计算方法

在完成程序的流分析和低层分析后，就可以开始计算程序的最差执行时间。在计算方法上，主要分为三种：

a)基于路径的计算方法：计算路径的执行时间，然后找出最长路径的执行时间即为程序最差执行时间。

b)基于隐藏路径列举（IPET Implicit Path Enumeration Techniques）的计算方法：将程序分解为两个约束集，一个表示程序的结构信息，另一个表示程序执行时最大循环迭代次数，在这两个约束集上寻求最大化目标函数获取程序最差执行时间。

c)基于语法树的计算方法：根据编译后的汇编代码，提取程序的控制流图，根据不同语法结构的不同规则，采用自底向上的语法树回溯算法，计算程序最差执行时间。

3 静态WCET 分析工具

静态WCET 经过十多年的研究发展，不仅取得显著的学术成果，而且也逐渐产生了一些好的WCET 分析工具，原型工具如SWEET,Heptane，商用工具如aiT 和BOUNT-T 开始在工程中取得应用。

BOUND_T 是由芬兰航天中心为欧洲航天协会开发的WCET 分析工具，基于可执行代码进行静态WCET 分析，分析过程独立于程序的源代码，可以对多种不同语言开发的程序进行WCET 分析。

aiT 是由德国AbsInt 公司开发为嵌入式系统开发的WCET 分析工具，基于程序的可执行代码建立后续分析所需的流信息，在高速缓存和流水线分析中采用了抽象解释的方法。

4 WCET 分析评估

为了检测aiT 及BOUND_T 的适用性，AbsInt 公司和芬兰航天中心都对自己的软件工具进行了工程试用。AbsInt 公司利用aiT对实时操作系统OSE 中的系统调用和关中断代码段基于ARM7 硬件平台进行了WCET 分析。结果显示，关中断代码段非常适合WCET分析，因为这部分代码通常比较简短而且没有太多循环，对这部分代码的WCET 可以完全自动地完成。但由于系统调用中包括例外处理和循环，其WCET 分析不能自动完成。BOUND_T 对欧洲航天协会CryoSat 卫星的控制和数据管理系统（CDMU Control and Data Management Unit）进行了WCET 分析，结果表明，BOUND_T 可以用于对CDMU 进行WCET 估计，但是，目前尚不足以自动完成整个分析过程。

AbsInt 公司同时还尝试将aiT 与CCS 开发工具的开发流程进行整合，在此过程中，他们将使用aiT 所得到的WCET 分析结果与动态测试的结果进行了对比，见下表1。其中动态测试结果是通过使用逻辑分析仪获取的。

通过上表我们可以发现，与仿真所估计的时间的比较，aiT 分析所得的WCET 较长，说明静态WCET 具有良好的安全性。但是，我们也可以看出，静态WCET 分析很可能过高地估计程序的最坏执行时间，即其精确性仍有待进一步的改进。

5 结论

如果在系统设计的最初，使用静态WCET 分析获取程序的最差执行时间，而在程序下载到目标机中后，使用逻辑分析仪对所获取的最差执行时间进行进一步的精确，可能是一个比较理想的应用方式。我们相信，随着静态WCET 分析技术的发展以及WCET 工具的不断完善，静态WCET 分析在控制算法设计中，将会获得系统设计师们更多的关注，并取得更广泛地应用。

[1]实时系统程序最差情况执行时间(WCET) 的分析,姬孟洛,齐治昌,计算机科学,2006，第10 期；

[2]一种基于抽象解释的WCET 自动分析工具，姬孟洛,李军，计算机工程，2006，第14 期；

[3]实时系统最坏执行时间分析，刘育芳,张立臣，计算机应用研究，2005年，第11 期；

[4]Evaluating Static Worst-Case Execution-Time Analysis for a Commercial Real-Time Operating System，Daniel Sandell，2004 ；

[5]Evaluation of Static Time Analysis for CC Systems，Ola Eriksson，2005；

[6]Experience from industrial WCET Analysis Case Studies,Andreas Ermedahl,Jan Gustafsson,Bj’’orn Lisper,2005；