等待自由的定义(指并行编程)

Question

在Maurice Herlihy的论文"Wait-free synchronization“中他定义了wait-free：

并发数据对象的无等待实现是指保证任何进程都可以在有限数量的步骤中完成任何操作，而不管其他进程的执行速度如何。www.cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf

让我们从宇宙中进行一次操作。

(1)该定义是否意味着：“每个进程在相同的有限步数n中完成某个操作op。”？

(2)或者它是否意味着：“每个进程在任意有限个步骤中完成某个操作op。因此，一个进程可以在k个步骤中完成op，另一个进程在j个步骤中完成op，其中k != j。”？

通过阅读定义，我就能理解它的含义(2)。然而，这对我来说没有任何意义，因为一个进程在k个步骤中执行op，并在k+m个步骤中执行另一个时间满足定义，但m个步骤可能是一个等待循环。如果meaning (2)是正确的，谁能向我解释，为什么这描述了无等待？

与(2)相反，意思(1)将保证op在相同数量的步骤k中执行。因此不可能有任何额外的步骤m是必要的，例如在等待循环中。

哪种含义是正确的?为什么？

非常感谢,

sema

Answer 1

答案是定义(2)。考虑到等待循环可能永远不会终止，如果等待的进程无限期运行：“无论其他进程的执行速度如何”。

因此，无限的等待循环实际上意味着给定的进程可能无法在有限数量的步骤中完成操作。

Answer 2

当像这样的理论论文的作者写“有限数量的步骤”时，这意味着存在某个常数k (您不一定知道k)，因此步骤的数量小于k (即，您的等待时间肯定不是无限的)。

我不确定“op”在这个上下文中是什么意思，但通常情况下，当你有一个多线程程序时，线程可能会等待另一个线程做一些事情。

例如:一个线程有一个锁，其他线程等待这个锁被释放，直到它们可以操作。

这个示例不是等待自由的，因为如果持有锁的线程没有机会执行任何操作(这很糟糕，因为这里的要求是无论其他线程如何，其他线程都将继续)，其他线程将注定失败，并且永远不会取得任何进展。

其他示例:有几个线程，每个线程都试图在同一地址上执行CAS

这个示例是无等待的，因为尽管除了一个线程以外的所有线程都会在这样的操作中失败，但无论选择运行哪个线程，都会有进程。

Answer 3

听起来您很担心定义2会允许无限的等待循环，但是这样的循环-无限的-不会满足在有限数量的步骤内完成的要求。

我认为“等待自由”是指取得进展不需要任何参与者等待另一个参与者完成。如果这种等待是必要的，如果一个参与者挂起或运行缓慢，其他参与者也会遭受类似的痛苦。

相比之下，使用无需等待的方法，每个参与者都会尝试自己的操作，并与其他参与者进行竞争性交互。例如，每个线程可能会尝试推进某个状态，如果两个线程“同时”尝试，则只有一个线程应该成功，但没有必要让任何“失败”的参与者重试。他们只是意识到其他人已经完成了这项工作，然后他们继续前进。

而不是专注于“等待轮到我采取行动”，一种无等待的方法鼓励“尝试帮助”，承认其他人也可能在同一时间尝试帮助。每个参与者都必须知道如何检测成功，何时重试，何时放弃，并确信尝试失败只是因为别人先进入了那里。只要工作完成了，由哪个线程完成就无关紧要了。