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

Question

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

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

可以告诉如何推断程序的进度条件吗？

Answer 1

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

class DataStructure:
    def operation(this):
        P
        pass

现在DataStructure.operation当且仅当P停止时以有限数量的步骤完成。

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