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