非无锁的无障碍算法示例是什么?

introduced the term -第一作者Herlihy介绍了 等待自由 25年前。

锁自由和障碍自由之间的核心区别在于,如果两个或多个线程正在运行,则后者不能保证进度(但如果只有一个线程正在运行,则可以保证进度)。

本文提供了一个无障碍但不无锁的出列示例。

为了更简单,我将只描述一个基于数组的 堆栈 其操作方式相同,无障碍但不无锁。

假设在数组顶部实现一个堆栈,这样堆栈中的零个或多个元素连续存储在数组的开头,然后在所有剩余位置存储“null”元素。堆栈的每个元素都存储为元组: (val, seq) val 是用户提供的价值和 seq 是一个序列号,它是算法的关键(同时也避免了ABA问题) ^1.

要将元素推到堆栈上,首先要定位堆栈中的最后一个元素(位置 A[k-1] )就在第一个之前 元件(位置 A[k] ). 您尝试使用CAS递增 A[k-1] A[k] 并增加其序列号。如果任一CAS失败,请重试。

该结构的正确性在上面的文章中有更详细的描述,但基本上是通过成功地增加 第th个元素确保此时它仍然是列表中的最后一个元素,并通过导致初始CA失败来通知任何同时进行的竞速推送操作“获得下一次机会”。如果第二个CAS成功,则成功添加了一个元素。

请注意,并发推送和弹出操作可能会导致彼此无限期地失败。推动线程会增加 和pop增量 A[k] ,然后当他们看到另一个的增量时,每个都失败了。冲洗并重复。这是livelock的一个示例。

^1. ... 它还避免了完整版本的出列中的“环绕”问题,但我认为在堆栈的情况下不会发生这种情况。

我不确定是否有可能 易于理解的 实例简单的事情通常是无等待(例如,RCU的读卡器端)或无锁(例如,不可能使用livelock的CAS重试循环),甚至不是无障碍的。

看见 Lock-free Progress Guarantees

我认为只有当线程可以取消其他线程部分完成的操作时,才可能没有障碍而没有锁。(从而处理他们自己的操作在醒来时被取消的情况)。我可能错了;也许还有其他方法可以使算法无阻塞但不无锁。

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

如果竞争的退避算法不好,这可能会导致死锁。由于有太多的线程在它上面敲打,他们只能在任何事情完成之前不断地相互抵消。这就是它不能自由锁定的原因。