无等待定义（并行编程术语）：

Question

4

在Maurice Herlihy的论文“无等待同步”中，他定义了无等待：

“并发数据对象的无等待实现是指保证任何进程可以在有限步骤内完成任何操作，而不管其他进程的执行速度。” www.cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf 让我们从宇宙中选择一个操作op。

（1）这个定义是否意味着：“每个进程以相同的有限步数n完成某个操作op。”？

（2）还是它意味着：“每个进程都可以在任意有限步数内完成某个操作op。因此，一个进程可以在k步中完成op，另一个进程可以在j步中完成op，其中k！= j。”？

仅通过阅读定义，我会理解意义（2）。然而，对我来说这毫无意义，因为在k步和k + m步中执行op的进程符合该定义，但是m步可能是等待循环。如果意思（2）是正确的，那么有人能向我解释一下，为什么这描述了无等待吗？

与（2）相比，意义（1）将保证op在相同的步骤k中执行。因此，不能有任何额外的步骤m是必要的，例如在等待循环中。

哪个含义是正确的？为什么？

非常感谢，

sema

- sema

4个回答

1

当理论论文的作者写下“有限步骤”时，意味着存在某个常数k（您不一定知道k），使得步骤数小于k（即您的等待时间肯定不会无限长）。

我不确定这里的“op”是什么意思，但通常情况下，在多线程程序中，线程可能会等待其他线程执行某些操作。

例如：一个线程拥有锁，其他线程等待该锁被释放后才能进行操作。

此示例不是无等待的，因为如果持有锁的线程没有机会执行任何操作（这很糟糕，因为要求在任何其他线程的情况下，其他线程都将继续运行），则其他线程注定会失败，并且永远不会取得任何进展。

另一个例子：有几个线程都试图在同一地址上CAS。

此示例是无等待的，因为虽然除了一个线程外，所有线程都会在此类操作中失败，但无论选择哪些线程运行，总会有进展。

- Anna

谢谢，你的回答支持了意义（1）。如果我理解你的回答正确，每个操作（或更好地说“每个操作的执行路径”，因为由条件和逻辑循环等引起的不同路径）都与一定数量的步骤k相关联。（这是我对意义（1）“...有限数量n的步骤”的意图。）但是你的回答与回答“答案意味着定义（2）。[...]”相矛盾。 - sema

'k'是一个限制条件，它是一个未知数（可能非常大）。我并没有完全理解你问题中(1)和(2)的含义。显然，一些线程可能会在其他线程之前完成，但是如果给予运行的机会，它们仍将在有限的步骤内完成。 - Anna

1

看起来你担心定义2会导致无限等待循环，但这样的循环——因为是无限的——不满足在有限步骤内完成的要求。

我认为“无等待”意味着推进不需要任何参与者等待另一个参与者完成。如果必须等待，如果一个参与者挂起或操作缓慢，其他参与者也会遭受同样的困境。

相比之下，采用无等待方法，每个参与者都尝试其操作并适应与其他参与者的竞争互动。例如，每个线程可以尝试推进某些状态，如果两个线程同时尝试，则只有一个线程应该成功，但没有任何需要“失败”的参与者重试的必要。他们只需认识到别人已经完成了工作，然后继续前进。

与其专注于“等待轮到我行动”，无等待方法鼓励“试图帮助”，承认其他人可能同时也在尝试帮助。每个参与者都必须知道如何检测成功，何时重试以及何时放弃，有信心尝试失败仅因为别人已经先行一步。只要完成工作，哪个线程完成都无所谓。

- seh

0

无等待（Wait-free）本质上意味着它不需要同步即可在多处理环境中使用。"有限步骤"指的是不必等待同步设备（例如互斥锁）的未知时间长度（可能是无限期的死锁），而另一个进程执行关键部分。

- Michael Melanson

它并不一定指常规意义上的死锁，而可能是线程之间不幸的时序问题（可能是由于缓慢的线程等原因）。 - Anna

“不幸的时机”可能导致任意长时间的延迟。但是，除非其他进程存在故障并且在终止时从未释放资源，或者发生死锁，否则这些延迟是有限的... - Michael Melanson

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Konrad Rudolph · Accepted Answer

答案意味着定义（2）。请考虑等待循环可能永远不会终止，如果被等待的进程无限运行：“无论其他进程的执行速度如何”。

因此，无限等待循环有效地意味着给定进程可能无法在有限步骤内完成操作。