安全关键实时程序执行时间预测的研究现状浅析

孟凡奇

摘 要：预测安全关键实时程序的执行时间具有重要意义。本文简要分析了程序执行时间预测的研究现状，对欲从事本方向研究的人员会有一定帮助。

关键词：安全关键软件；实时程序；执行时间预测

安全关键系统（safety-critical system，CSC）[1]泛指具有潜在破坏力的一类系统。此类系统一旦失效（例如汽车的ABS失灵）就可能造成人员伤亡、财产损失或环境破坏等严重后果。

安全关键实时程序可理解为在安全关键系统中起重要控制作用的实时程序。需要指出的是，安全关键程序未必是实时程序，而实时程序也未必是安全关键程序。例如，遥控玩具飞机上的控制程序是实时程序，但不是安全关键程序。而医疗X射线机中的程序是安全关键程序，因为辐射剂量控制的不好会对人体造成伤害，但它不是实时程序。

本文余下首先对程序执行时间预测进行一个总览，然后简要分析安全关键实时程序执行时间预测研究现状及方向。

1 程序执行时间预测研究现状

程序执行时间预测技术大体上可以分为3类：动态方法、静态方法以及混合方法。

动态方法也称为基于测量的方法，其基本原理是统计预测（Statistical Prediction），即：使用大量测试用例，多次运行程序，获取程序的执行时间数据，加工后进行预测。

静态方法也称基于分析的方法，其基本原理是图论（graph theory），即：分析程序的控制流图，搜寻特定输入（具体值或者范围）下，满足目标处理器特性约束的穿过程序的最长执行路径。

混合方法，顾名思义，要么先动态后静态，要么先静态后动态。

上述3种方法在预测程序执行时间时各有利弊。动态方法的优点是方法简单，硬件适应性强。缺点是多次测试，时间较长，且由于不能穷举程序的所有执行路径以及硬件状态，因此预测值比实际程序的执行时间范围要小，不能用于安全关键实时程序。静态方法的优点是有数学基础，因此预测值比实际程序的执行时间范围要大，能用于安全关键实时程序。缺点是对硬件建模比较困难，尤其是对含有复杂架构（比如多级Cache、流水线、分支预测等）的处理器建模。混合方法则可以克服两者的缺点，融合两者的优点。

2 程序执行时间预测研究方向

从图1中可以看出，近年来程序执行时间预测所发SCI论文总体是呈上升趋势的，说明这个研究方向是很有前景的。

安全关键实时程序执行时间预测主要使用静态方法。目前，在该领域有两个较好的研究方向。一个面向编码阶段的交互式程序执行时间预测。Harmon[2]等人采用基于语法树的计算方法开发了volta ，该工具面向java程序和JOP处理器，能够在编程过程中即时给出函数的WCET分析值。另一个是面向确认阶段的概率化程序执行时间预测。Cazorla[3]设计了概率可分析的实时系统Proartis，能够给出程序执行时间的概率分布。确认阶段是由第三方对软件进行一致性验证的阶段，安全关键软件经过安全性确认后才可以交给用户使用。

3 结束语

随着信息物理系统的兴起，安全关键实时程序必将应用于更多的领域。为了确保系统安全，必须对程序执行时间进行预测，以保证程序能够在安全的截至时间范围内运行完成。基于测量的方法由于获得的执行时间范围比实际的小，因此不适用于安全关键实时程序。交互式以及概率化的程序执行时间预测，作为静态预测方法，具有很好的研究前景。

[参考文献]

[1]鲁志伟，马文婧，宋文国，等.新立变电站接地系统安全性能研究[J]. 东北电力大学学报，2012，32（6）：28-32.

[2]Harmon T，Schoeberl M，Kirner R，et al.Fast，interactive worst-case execution time analysis with back-annotation[J]. Industrial Informatics，IEEE Transactions on，2012，8（2）：366-377.

[3]Cazorla F J，Quinones E，Vardanega T，et al.Proartis： Probabilistically analyzable real-time systems[J].ACM Transactions on Embedded Computing Systems （TECS），2013， 12（2s）：94.