什么是无障碍算法的一个例子，不是无锁的？

Question

因此，锁自由度是指您可以保证整个系统都在进步，尽管有些线程可能会饿死。因此，基于CAS的实现将提供这一保证。

然后，如果所有其他线程都挂起，那么obstruction-freedom就是保证一个线程完成的时候。

你能给出一个简单的例子，说明一种非无锁的无障碍算法吗？

谢谢!

Answer 1

我不确定能否举一个简单的例子。简单的东西通常是无等待的(例如RCU的读取器端)或无锁的(例如CAS重试循环，在不可能生动活泼的情况下)，或者甚至不是无阻塞的。

有关无锁多写器多读取器队列的分析，请参阅无锁进度保证，其中睡在中间操作中的写入器可以阻塞整个队列，尽管它具有高性能/低争用性，并且在实践中很有用。

我认为，只有当线程可以取消其他线程部分完成的操作时，才有可能在没有锁的情况下实现无阻塞。(从而处理当他们醒来时自己的操作被取消的情况)。我可能弄错了；也许还有其他方法可以使algo非阻塞，但不是无锁的。

这不是我认为简单的事情，但算法说：

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

如果争用的退避算法不好，这可能会生动活泼。有太多的线程锤打在上面，它们可以在做任何事情之前不断地取消对方。这就是为什么它不是没有锁的原因。