什么是不锁定无阻塞算法的例子？

Question

所以锁定自由是当你有保证整个系统进展，虽然有些线程可能会饿死。所以基于CAS的实现将提供这种保证。

然后无阻塞是当一个线程保证完成，如果所有其他线程都挂起。

你能给出一个简单的无锁定算法的例子吗？

谢谢！

Answer 1

我推荐阅读introduced the term - 主要作者Herlihy在25年前推出等待自由的概念时启动了整个业务。

锁定自由和梗阻自由之间的核心区别是，如果两个或多个线程运行后并不能保证取得进展（但如果只有一个正在运行）。

本文的肉给你要你想要的，出队是梗阻免费的，但不是无锁的例子。

为了使它更简单，我将只描述一个基于数组的堆栈，它以相同的方式运行，并且无阻塞但不锁定空闲。

想象一下，在一个数组顶部实现一个堆栈，这样堆栈的零个或多个元素将连续存储在数组的开头，然后在所有剩余位置中都是“null”元素。堆栈中的每个元素都存储为元组：(val, seq)，其中val是用户提供的值，seq是对算法很关键的序列号（并且还避免了ABA问题）。

为推动元件压入堆栈，首先定位堆栈中的最后一个元素（位置A[k-1]），这是直接在第一空元件（在A[k]位置）之前。您尝试增量，使用CAS的A[k-1]的序列号（元素没有变化），如果成功，你试图同时替换值null元素在A[k]位置，并增加它的序列号。如果任一CAS失败，则重试。

弹出算法类似，但处理以相反的顺序（递增拳头空元素的序列号，然后努力使最后一个元素null，并且递增的序列号）的元素。

该结构的正确性在上面的文章中有更详细的描述，但基本上通过成功增加第012个元素，你确保在那一刻它仍然是列表中的最后一个元素，并且你通知任何同时参加的比赛通过使他们的初始CAS失败来推动你“获得下一个镜头”的操作。如果第二个CAS成功，您成功添加了一个元素。

注意并发push和pop操作会导致对方失败，无限期。在推进螺纹增量A[k-1]，并在弹出的增量A[k]，然后当他们看到其他的增量每个失败。冲洗并重复。这是活锁的一个例子。

请注意，如果只有一个线程正在运行，问题就会消失，这是阻塞自由中的关键观察。

---

...这也避免了出队的完整版“环绕”的问题，但我不认为在堆栈的情况下发生的。

Answer 2

我不确定是否有可能给出简单的示例。简单的事情通常是无等待的（例如RCU的阅读器侧）或无锁（例如，不可能存在活锁的CAS重试循环），或者甚至不阻塞。

请参阅Lock-free Progress Guarantees分析无锁定多写入器多读取器队列，其中即使在中等运行情况下睡觉的写入器可以阻塞整个队列，即使它是高性能/低争用并且在实践中有用。

---

我认为是阻碍自由而不无锁是唯一可能的，如果线程可以被其它线程取消部分完成的操作。 （并且因此处理当他们唤醒时取消他们自己的操作的情况）。我可能错了;也许还有其他方法算法可以是非阻塞的，但不是无锁的。

这不是我会考虑简单，但https://en.wikipedia.org/wiki/Non-blocking_algorithm说：

一些无障碍的算法，数据结构使用一对“一致性标记”。读取数据结构的过程首先读取一个一致性标记，然后将相关数据读入内部缓冲区，然后读取另一个标记，然后比较标记。如果两个标记相同，数据是一致的。当读取被另一个更新数据结构的进程中断时，标记可能不相同。在这种情况下，进程会丢弃内部缓冲区中的数据并再次尝试。

如果用于争用的退避算法不好，这可能会活锁。由于线程太多，他们可能会在任何事情完成之前不断取消对方。这是什么使它不锁定。