什么是非无锁无障碍算法的例子？
What is an example of obstruction-free algorithm that is not lock-free?
所以 lock-freedom 是当您可以保证整个系统取得进展时，尽管某些线程可能会饿死。因此，基于 CAS 的实现将提供此保证。
那么无障碍就是当所有其他线程都挂起时保证一个线程完成。
你能举一个非无锁无障碍算法的简单例子吗？
谢谢！
我不确定是否可以给出一个简单的例子。简单的事情通常是无等待的（例如 RCU 的 reader 端）或无锁的（例如活锁不可能的 CAS 重试循环），甚至不是无障碍的。
参见 对无锁多写入器多reader 队列的分析，其中在运行中休眠的写入器可以阻塞整个队列，即使它是高性能/低争用的在实践中很有用。
我认为只有当线程可以取消其他线程的部分完成操作时，才可能实现无阻塞而不是无锁。 （从而处理当他们醒来时取消自己的操作的情况）。我可能错了；也许还有其他方法可以使算法成为非阻塞但不是无锁的。
这不是我认为的简单，但https://en.wikipedia.org/wiki/Non-blocking_algorithm说：
Some obstruction-free algorithms use a pair of "consistency markers" in the data structure. Processes reading the data structure first read one consistency marker, then read the relevant data into an internal buffer, then read the other marker, and then compare the markers. The data is consistent if the two markers are identical. Markers may be non-identical when the read is interrupted by another process updating the data structure. In such a case, the process discards the data in the internal buffer and tries again.
如果争用退避算法不好，这可能会导致活锁。由于有太多的线程对其进行锤击，它们可能会在任何事情完成之前不断地相互取消。这就是它不是无锁的原因。
我建议阅读 introduced the term 的论文 - 主要作者 Herlihy 在 25 多年前引入了 等待自由 的概念时开始了整个业务.
无锁和无阻塞之间的核心区别在于，如果两个或多个线程是 运行，后者不能保证进度（但如果只有一个是 运行，则可以）。
这篇论文的内容给了你想要的，一个无阻塞但不是无锁的出列示例。
为了更简单，我只描述一个基于数组的堆栈，它以相同的方式运行，并且是无阻塞但不是无锁的。
想象一个在数组顶部实现的堆栈，这样堆栈的零个或多个元素连续存储在数组的开头，然后是 "null" 个元素在所有剩余位置。堆栈的每个元素都存储为一个元组：(val, seq)，其中 val 是用户提供的值，seq 是一个序列号，它是算法的关键（也避免了ABA问题1).
要将元素压入堆栈，首先要找到堆栈中的最后一个元素（位置 A[k-1]），该元素紧接在第一个 null 元素之前（位于位置 A[k])。您尝试使用 CAS 增加 A[k-1] 的序列号（元素不变），如果成功，您尝试同时替换位置 A[k] 处的空元素的值并增加其序列数字。如果任一 CAS 失败，您重试。
弹出算法类似，但以相反的顺序处理元素（递增第一个空元素的序列号，然后尝试使最后一个元素为空并递增其序列号）。
此结构的正确性在上面的论文中有更详细的描述，但基本上通过成功递增第 A[k-1] 个元素，您可以确保在那一刻它仍然是列表中的最后一个元素，并且您通过导致其初始 CAS 失败来通知任何并发的竞速推送操作您 "get the next shot"。如果第二个 CAS 成功，您就成功添加了一个元素。
请注意，并发的推送和弹出操作可能会无限期地导致彼此失败。推送线程递增 A[k-1] 并且弹出线程递增 A[k]，然后每个都失败，因为它们看到另一个递增。冲洗并重复。这是一个活锁的例子。
请注意，如果只有一个线程 运行，问题就会消失，这是无障碍的关键观察结果。
1 ...它也避免了"wraparound"完全版本出队的问题，但我认为在堆栈的情况下不会发生.
所以 lock-freedom 是当您可以保证整个系统取得进展时，尽管某些线程可能会饿死。因此，基于 CAS 的实现将提供此保证。
那么无障碍就是当所有其他线程都挂起时保证一个线程完成。
你能举一个非无锁无障碍算法的简单例子吗？
谢谢！
我不确定是否可以给出一个简单的例子。简单的事情通常是无等待的（例如 RCU 的 reader 端）或无锁的（例如活锁不可能的 CAS 重试循环），甚至不是无障碍的。
参见
我认为只有当线程可以取消其他线程的部分完成操作时，才可能实现无阻塞而不是无锁。 （从而处理当他们醒来时取消自己的操作的情况）。我可能错了；也许还有其他方法可以使算法成为非阻塞但不是无锁的。
这不是我认为的简单，但https://en.wikipedia.org/wiki/Non-blocking_algorithm说：
Some obstruction-free algorithms use a pair of "consistency markers" in the data structure. Processes reading the data structure first read one consistency marker, then read the relevant data into an internal buffer, then read the other marker, and then compare the markers. The data is consistent if the two markers are identical. Markers may be non-identical when the read is interrupted by another process updating the data structure. In such a case, the process discards the data in the internal buffer and tries again.
如果争用退避算法不好，这可能会导致活锁。由于有太多的线程对其进行锤击，它们可能会在任何事情完成之前不断地相互取消。这就是它不是无锁的原因。
我建议阅读 introduced the term 的论文 - 主要作者 Herlihy 在 25 多年前引入了 等待自由 的概念时开始了整个业务.
无锁和无阻塞之间的核心区别在于，如果两个或多个线程是 运行，后者不能保证进度（但如果只有一个是 运行，则可以）。
这篇论文的内容给了你想要的，一个无阻塞但不是无锁的出列示例。
为了更简单，我只描述一个基于数组的堆栈，它以相同的方式运行，并且是无阻塞但不是无锁的。
想象一个在数组顶部实现的堆栈，这样堆栈的零个或多个元素连续存储在数组的开头，然后是 "null" 个元素在所有剩余位置。堆栈的每个元素都存储为一个元组：(val, seq)，其中 val 是用户提供的值，seq 是一个序列号，它是算法的关键（也避免了ABA问题1).
要将元素压入堆栈，首先要找到堆栈中的最后一个元素（位置 A[k-1]），该元素紧接在第一个 null 元素之前（位于位置 A[k])。您尝试使用 CAS 增加 A[k-1] 的序列号（元素不变），如果成功，您尝试同时替换位置 A[k] 处的空元素的值并增加其序列数字。如果任一 CAS 失败，您重试。
弹出算法类似，但以相反的顺序处理元素（递增第一个空元素的序列号，然后尝试使最后一个元素为空并递增其序列号）。
此结构的正确性在上面的论文中有更详细的描述，但基本上通过成功递增第 A[k-1] 个元素，您可以确保在那一刻它仍然是列表中的最后一个元素，并且您通过导致其初始 CAS 失败来通知任何并发的竞速推送操作您 "get the next shot"。如果第二个 CAS 成功，您就成功添加了一个元素。
请注意，并发的推送和弹出操作可能会无限期地导致彼此失败。推送线程递增 A[k-1] 并且弹出线程递增 A[k]，然后每个都失败，因为它们看到另一个递增。冲洗并重复。这是一个活锁的例子。
请注意，如果只有一个线程 运行，问题就会消失，这是无障碍的关键观察结果。
1 ...它也避免了"wraparound"完全版本出队的问题，但我认为在堆栈的情况下不会发生.