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

Question

不管市场上有什么静态分析工具，理论上有没有可能使用静态分析工具证明Java (或任何其他命令式语言)代码没有竞争条件？

Answer 1

"Java代码没有竞争条件“这句话非常含糊。也许你指的是其中之一：

Java

• 静态分析工具能证明没有程序有竞争条件吗？显然不是，因为确实存在具有竞争conditions.
• Can的Java程序，静态分析工具总是证明没有竞争条件的Java程序没有竞争条件？不，因为这等同于解决停顿问题(将静态竞争条件放在可能终止也可能不终止的循环之后。要判断竞争是否真的会发生，您需要知道静态分析工具terminates).
• Can循环有时是否证明没有竞争条件的Java程序没有竞争条件？是。事实上，这样的工具可能会非常有用。

Answer 2

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

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

Answer 3

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

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

正如在其他答案中所指出的，对于特别复杂的代码来说，适当的建模可能是困难或不可能的，这些代码模糊了实际进行的调用或访问的数据成员。然而，对于合理的代码，这实际上在数学上不应该是不可能的(而不是非常慢)。

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