以下对象是否处于空闲状态？

Question

这是完整的问题：

以下属性是否等同于说对象 x 是 免等待？

对于 x 的每个无限历史 H，每个需要无限数量的线程 H 中的步骤完成了无数次方法调用。

所以我对wait-free的理解是无论如何，调用方法的线程都会以有限的步骤完成方法的执行。从例子中我们知道每个线程都会完成无限个方法。如果不是wait-free，那么它应该在某种方法中停止（因此它应该采取无限数量的步骤来完成该方法），因此它无法完成无限数量的方法（因为它已在方法中的某个地方停止）。所以它是等待-免费。

上述推理正确吗？我希望得到更准确/正确的答案。

Answer 1

是的，我同意你的逻辑。这里有更详细的解释

让我们解决这里的主要问题——不同大小的无穷大。我们可能会担心一个方法会采取无限多的步骤，但在我们分配给线程的“无限多的步骤”之前仍然完成（正如房间里的数学专业人士所知，确实有不同类型的无穷大） ).

对我们来说幸运的是，在这种情况下，我们的数量、采取的步骤和调用的方法都是可数无限的（我总是能够定义从自然数到给定步骤/给定方法索引的映射）。

事实：让

m

成为

x

的一种方法，在给定一些历史

H

的情况下，需要无限数量的步骤才能完成。然后，如果

N

是在调用

m

之后发生的某个有限步骤索引，那么无论线程调用

m

仍将位于

m

中的步骤

N

。

一旦进入这样的方法，我们就永远在那里。因此，如果我们在某个有限步骤

M

上输入此方法，那么我们只能完成最多

M-1

方法（这违反了我们完成无限数量方法的假设）。因此，这样的方法永远不会存在，并且我们的对象

a

的所有方法对于每个可能的结果总是在有限数量的步骤中完成（因为我们有无限的历史，我们所说的数量是也是可数的）。这相当于

x

无需等待。