如何检查并发程序遵循的进度保证？

Question

在过去的几周里，我一直在研究一些并发程序，我想知道是否有任何工具可以自动检测其操作保证的进展情况，即它是无等待、无锁还是无阻塞。

我在网上搜索，没有找到任何这样的工具。

如何推断程序的进度条件？

Answer 1

假设我有一个名为“等待自由决定器”的程序，它可以读取描述数据结构的并发程序并检测它是否是空闲的，即“保证任何进程都能在有限的步骤中完成任何操作的程序”ala 赫利希的“无等待同步”。然后，给定一个单线程程序P，创建一个程序，我们将把它输入到等待自由决定器中：

class DataStructure:
    def operation(this):
        P
        pass

现在，DataStructure.operation在有限的步骤中完成当且仅当P停止。

这样就能解决停车问题。这是不可能的，所以，由于矛盾，我们不能创造一个等待自由的决策者。