因此，无锁 是指尽管某些线程可能处于饥饿状态，但您可以保证整个系统都在进步。因此，基于 CAS 的实现将提供此保证。
那么无障碍就是当所有其他线程都挂起时保证一个线程完成。
你能举一个非无锁无障碍算法的简单例子吗？
谢谢!
最佳答案
我建议阅读 introduced the term 的论文- 主要作者 Herlihy 在 25 多年前引入了等待自由的概念时开始了整个业务。
无锁和无阻塞之间的核心区别在于，如果两个或多个线程正在运行，后者不能保证进度(但如果只有一个正在运行，则可以)。
本文的主要内容是您想要的，一个无阻塞但非无锁的出队示例。
为了让它更简单，我将只描述一个基于数组的堆栈，它以相同的方式运行，并且是无阻塞但不是无锁的。
想象一个在数组顶部实现的堆栈，这样堆栈的零个或多个元素连续存储在数组的开头，然后是所有剩余位置的“空”元素。堆栈的每个元素都存储为一个元组:(val, seq) , 其中val是用户提供的值，seq是一个序列号，它是算法的关键(也避免了 ABA 问题1)。
要将元素压入堆栈，您首先要找到堆栈中的最后一个元素(位置 A[k-1])，它紧接在第一个 null 元素之前(位置 A[k])。您尝试使用 CAS 增加 A[k-1] 的序列号(元素不变)，如果成功，您尝试同时替换位置 A[k] 处的空元素的值。并增加其序列号。如果任一 CAS 失败，您将重试。
弹出算法类似，但以相反的顺序处理元素(递增第一个空元素的序列号，然后尝试使最后一个元素为空并递增其序列号)。
此结构的正确性在上面的论文中有更详细的描述，但基本上是通过成功递增 A[k-1] 来实现的。 th 元素你确保在那一刻它仍然是列表中的最后一个元素，并且你通过导致它们的初始 CAS 失败来通知任何并发的竞速推送操作你“获得下一击”。如果第二个 CAS 成功，您就成功添加了一个元素。
请注意，并发的推送和弹出操作可能会无限期地导致彼此失败。推送线程递增A[k-1]并且弹出增量A[k] ，然后每一个都失败了，因为他们看到了另一个的增量。冲洗并重复。这是一个活锁的例子。
请注意，如果只有一个线程在运行，问题就会消失，这是无障碍的关键观察结果。
1 ...它还避免了完整版本的出队中的“环绕”问题，但我认为在堆栈的情况下不会发生这种情况。
关于multithreading - 什么是非无锁无障碍算法的例子？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/46489805/