软件最坏场景运行时间快速计算方法研究
陈勇
【摘? 要】在安全关键实时系统设计中，为了保证系统的安全运行，实时任务必须在截止期之前完成，否则将产生严重的后果。衡量系统实时性的重要指标是任务的最坏场景运行时间（Worst Case Execution Time， WCET）。论文在传统静态WCET分析方法的基础上，提出了将拓扑排序算法应用到WCET的计算中，较大地提升了WCET的计算效率。
【Abstract】In the design of safety-critical real-time system， in order to ensure the safe operation of the system， the real-time task must be completed before the deadline， otherwise serious consequences may happen. Worst Case Execution Time （WCET） of a task is an important indicator of system real-time performance. Based on the traditional static WCET analysis method， this paper puts forward the application of topological sorting algorithm to the calculation of WCET， which greatly improves the calculation efficiency of WCET.
【关键词】安全关键;实时系统;WCET
【Keywords】safety-critical; real-time system; WCET
【中图分类号】TP301.6? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?【文獻标志码】A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?【文章编号】1673-1069（2021）04-0158-02
1 引言
实时系统中对软件运行时间，相对于非实时系统来说有着严格的时限要求，非实时系统有较高的运行时限容忍度，软件偶然的运行超时并不会造成严重后果，仅仅是降低了系统的吞吐量。而实时系统有刚性的、严格的时间限制，软件运行超出时限后，会导致系统不能实现它的预期目标，或者带来损害甚至导致系统失效，对于安全关键实时系统，系统失效带来的后果可能是灾难性的，故它不允许任何超出时限的错误。实时系统的时间性要求更关注的WCET是在目标环境中的一个给定处理器上，完成一组任务执行的最长可能时间，要求在逻辑结果正确的前提下，WCET在分配的时间范围之内。
实时任务的WCET与软件的输入、采用的算法以及软件运行的目标环境相关。基于程序的源代码或目标代码，通过分析程序中的基本块，对每个函数的控制流进行分析，并获取程序可能的执行路径信息，以便找出最长路径。底层分析主要考虑处理器体系架构对软件运行时间的影响，如何对缓存、流水线、乱序执行、分支预测等特性进行建模来提高WCET估计的精度。WCET计算主要研究如何在控制流分析、底层分析的基础上找出WCET的算法。
2 WCET分析技术
WCET分析方法分为三种：动态测量方法、静态分析方法和混合方法。
动态测量是在目标硬件环境下，基于需求，通过给定不同的输入对程序进行测试。通过收集程序每次的运行时间可以获得程序的最大运行时间。然后对结果增加一定的时间余度以防止测量值低于实际的最坏场景下的运行时间，由于测试不能穷举，所以不能保证结果是安全的。
静态分析方法是在分析处理器性能特性的基础上，分析程序源代码（或目标码）以获取程序运行时特征（如访问的内存地址、循环边界等），最后计算程序所占用的处理器时间。主要过程包括：控制流分析、底层分析、WCET计算。典型WCET静态分析过程如图1所示。目前市场上比较成熟的工具有德国Absint公司的aiT[1]。
混合方法是综合运用静态分析方法和动态测量方法，但这里动态测量与上述动态测量方法的内容是不相同的。在对程序中的小程序单位（如基本块）进行动态测量（即替换了图1中的底层分析过程）后，再进行静态分析得到WCET。
本文描述的是WCET静态分析方法。
3 控制流分析
控制流分析基于程序的源代码或目标代码，通过分析程序中的基本块，对每个函数的控制流进行分析，并获取程序可能的执行路径信息（执行流），以找出最长路径。控制流分析不考虑软件运行环境的硬件信息，分析研究主要集中在控制流的提取、逻辑结构的表示、控制流的表示与转换（如确定循环结构）、循环上界及不可达路径的确定等。控制流的提取主要依据源代码（或目标码）的各种语法结构，如if-else、switch-case结构等（或目标码中的跳转、条件跳转等），而确定循环最大次数，不可达路径，需要更多的语义分析，必要时需要通过注解的方式来获取。控制流的描述法主要有：语法树、域树、时间树、控制流图等[2]。本文基于目标码来生成函数的控制流图，如图2所示。
4 底層分析
如果指令是顺序执行的，则对顺序执行的程序指令，简单相加指令周期就可以得到程序运行时间的一个估计。而具有CACHE、流水线、乱序执行、分支预测等硬件特性的目标处理器上，这种指令周期相加的计算方法只能得出相当不准确的WCET估计。因此，必须结合处理器各种加速特性对目标码进行底层分析，才能获取更为精确的WCET估计。底层分析一般包括：变量值分析、CACHE分析、流水线分析、分支预测分析等。
5 WCET计算
WCET的计算是通过结合控制流分析和底层分析的结果来计算程序的WCET估计值，当前主要有三种计算方法：基于隐藏路径枚举的计算方法（IPET）、基于树的计算方法及基于路径的方法。
基于IPET的计算方法通过建立程序流程和基本块的迭代模型及用数学约束，建立目标函数，对WCET的计算就是进行最大化求解，一般使用的约束包括：结构约束和功能约束。结构约束与程序的控制流有关，功能约束则与循环边界、路径信息和函数调用有关。最大化求解的主要的方法是整数线性规划ILP（Integer Linear Programming）。本文采用基于IPET的计算方法，但在最后计算阶段未使用ILP，而是引入了一种全新的计算方法，基于拓扑排序的计算方法。
5.1 拓扑排序简介
拓扑排序（topological-sort）是指由某个集合上的一个偏序得到该集合上的一个全序的操作。拓扑排序常用来确定一个包含依赖关系集合中，事物发生的先后顺序。拓扑排序是对有向无环图中的顶点的一种排序，排序的规则是：如果存在一条从顶点A到顶点B的路径，那么在排序中，A排在B的前面。
拓扑排序的典型应用是根据作业或任务的相关性来安排它们的顺序。例如，洗衣服时，洗衣机必须先洗出衣服，然后我们才能将衣服放入烘干机。这个特性可以应用到工程上的施工流程。用顶点表示子工程（活动），用有向边表示活动间的先后关系，这就形成了一个AOV网络（activity on vertex network）有向图。我们要对某个工程的施工流程是否可行进行论证，就是必须检测相应的AOV网络是否存在回路，一个AOV网络中如果存在回路，这就意味着某个子工程的开工要以自身的完工为前提条件，这显然是不可能的。确定AOV网络是否存在回路则通过拓扑排序来完成。因此，研究拓扑排序算法是很有实际意义的。
5.2 拓扑排序算法在WCET中的应用
从图2可以看出，函数的控制流图就是一个典型的有向图。顶点表示程序基本块，有向边表示基本块执行的先后顺序，如果从基本块A到基本块B之间存在一条路径，则称基本块A是基本块B的前趋，或称基本块B是基本块A的后继。如果[A， B]是控制流图中的一条边，则称A是B的直接前趋，或称B是A的直接后继。拓扑排序的算法如下：
①在控制流图中选取一个函数入口基本块（没有前趋）。
②在控制流图中删除该基本块及其所发出的所有边。
③重复执行①、②，直至输出全部没有前趋的基本块。
当过程结束时，如果有向图中的所有基本块均已输出，则说明有向图中不存在回路，否则说明有向图存在回路。
使用拓扑排序可以确定有向图中是否有回路，而在控制流图中，只有循环存在时，才会存在回路。因此，使用拓扑排序，不仅可以排列出程序基本块执行的先后顺序，还可以准确地确定函数中的循环起点基本块和循环终点基本块，通过循环变化后，可以将函数控制流图变成完整的拓扑结构图。这样，计算函数WCET的时间，就转化成了对拓扑结构中每一个顶点完成时间的计算。函数的WCET实际上就是最后一个顶点完成的时间。
6 结语
本文对目前WCET分析技术进行了详细的研究讨论，并给出了一个基于目标码分析的WCET分析过程。采用拓扑排序算法，极大地简化了WCET的计算，WCET计算的时间复杂度为O（n），其中n表示函数基本块的数目。经过实际测试的验证，该方法的运算速度快于ILP。
【参考文献】
【1】AbsInt.The industry standard for static timing analysis[EB/OL].https：//www.absint.com/ait.
【2】Kirner R， Puschner P. Classification of WCET analysis techniques[C]// Eighth IEEE International Symposium on Object-Oriented Real-Time Distributed Computing （ISORC'05）. IEEE， 2005.
