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

Question

这几周我在做一些并发程序，想知道有没有什么工具可以自动检测它的操作保证了什么样的进度条件，即是否是无等待，无锁或无障碍。

我在网上搜索了一下，没有找到这样的工具。

能说说如何推断一个程序的进度情况吗？

Answer 1

假设我有一个名为 wait-freedom decider 的程序，它可以读取描述数据结构的并发程序并检测它是否是 wait free，即 "one that guarantees that any process can complete any operation in a finite number of steps"阿拉Herlihy's "Wait-Free Synchronization"。然后，给定一个 单线程 程序 P，创建一个我们将输入等待自由决策程序的程序：

class DataStructure:
    def operation(this):
        P
        pass

现在，当且仅当 P 停止时，DataStructure.operation 会在有限步数内完成。

这将解决停机问题。那是不可能的，所以，矛盾的是，我们一定不能创建一个等待自由的决策器。