理论上是否有可能使用静态分析工具证明 Java 代码没有竞争条件



无论市场上有哪些静态分析工具,理论上是否有可能使用静态分析工具证明Java(或任何其他命令式语言)代码没有竞争条件?

"Java 代码没有竞争条件"这句话非常模糊。 也许你的意思是这些之一:

  • 静态分析工具能否证明没有 Java 程序具有竞争条件? 显然不是,因为确实存在具有竞争条件的Java程序。

  • 静态分析工具能否始终证明无竞争条件的 Java 程序没有竞争条件? 否,因为这等效于解决停止问题(在可能会或可能不会终止的循环之后放置静态争用条件)。 要判断比赛是否真的会发生,您需要知道循环是否终止)。

  • 静态分析工具有时能否证明无竞争条件的 Java 程序没有竞争条件? 是的。 事实上,这样的工具可能非常有用。

这只是我的直觉,但我会说不,至少对于一般的Java程序。证明某些程序没有竞争条件应该不会太难(简单来说,任何单线程程序,识别单线程并不难)。但是要为所有Java程序做出决定?我怀疑Java的并发模型太不受限制了。

我认为可以证明在任意 Java 代码中决定没有竞争条件等同于停止问题,因为某些东西(最明显的是公共静态字段)对所有线程都是隐式访问的,并且它们可以通过反射访问,任意复杂的代码确定用于查找它们的字符串。

这应该可以使用像 spin(http://spinroot.com/spin/whatispin.html) 这样的模型检查器来实现。

但是,您需要创建从java到模型语言的转换,并且这种模型检查在计算上非常昂贵(包括占用大量内存),因此其可行性是另一个问题。

如其他答案所述,对于特别复杂的代码,适当的建模可能很困难或不可能,这些代码掩盖了实际调用或访问的数据成员。但是,对于合理的代码,这实际上在数学上不应该是不可能的(而不是非常慢的)。

也不可能考虑代码外部的任何特定竞争条件 - 因此,如果存在竞争条件的实际风险,将某些内容建模为非原子的原子 IO 操作将导致无效模型。

最新更新