41

我看到有人/文章/SO 帖子说他们为多线程使用设计了自己的“无锁”容器。假设他们没有使用影响性能的模数技巧（即每个线程只能基于某个模数插入），数据结构怎么能是多线程的又是无锁的？

这个问题是针对 C 和 C++ 的。

4

4 回答 4

51

无锁编程的关键是使用硬件固有的原子操作。

事实上，即使是锁本身也必须使用那些原子操作！

但是锁定和无锁编程之间的区别在于，无锁程序永远不会被任何单个线程完全停止。相反，如果在一个锁定程序中，一个线程获得了一个锁，然后无限期地挂起，整个程序就会被阻塞并且无法继续进行。相比之下，即使单个线程无限期挂起，无锁程序也能取得进展。

这是一个简单的示例：并发计数器增量。我们提出了两个版本，它们都是“线程安全的”，即可以同时调用多次。首先是锁定版本：

int counter = 0;
std::mutex counter_mutex;

void increment_with_lock()
{
    std::lock_guard<std::mutex> _(counter_mutex);
    ++counter;
}

现在是无锁版本：

std::atomic<int> counter(0);

void increment_lockfree()
{
    ++counter;
}

现在想象数百个线程都increment_*同时调用该函数。在锁定版本中，在持有锁的线程解锁互斥体之前，任何线程都无法取得进展。相比之下，在无锁版本中，所有线程都可以进行。如果一个线程被搁置，它就不会分担工作，但其他人都可以继续他们的工作。

值得注意的是，通常无锁编程会以吞吐量和平均延迟吞吐量换取可预测的延迟。也就是说，如果没有太多争用，无锁程序通常会比相应的锁定程序完成得更少（因为原子操作很慢并且会影响系统的大部分其余部分），但它保证永远不会产生不可预测的结果大延迟。

于 2012-12-23T14:58:39.997 回答
26

对于锁，想法是你获得一个锁，然后在知道没有其他人可以干涉的情况下做你的工作，然后释放锁。

对于“无锁”，想法是您在其他地方完成工作，然后尝试以原子方式将该工作提交到“可见状态”，如果失败则重试。

“无锁”的问题是：

  • 很难为不平凡的事情设计无锁算法。这是因为只有这么多方法可以完成“原子提交”部分（通常依赖于用不同指针替换指针的原子“比较和交换”）。
  • 如果存在争用，它的性能会比锁更差，因为您反复做被丢弃/重试的工作
  • 设计一个既正确又“公平”的无锁算法几乎是不可能的。这意味着（在竞争中）一些任务可能是幸运的（并且反复提交他们的工作并取得进展），而另一些可能非常不幸（并且反复失败并重试）。

这些东西的结合意味着它只适用于低竞争下相对简单的东西。

研究人员设计了诸如无锁链表（和 FIFO/FILO 队列）和一些无锁树之类的东西。我认为没有比这些更复杂的了。对于这些事情是如何工作的，因为很难，所以很复杂。最明智的方法是确定您对哪种类型的数据结构感兴趣，然后在网上搜索有关该数据结构的无锁算法的相关研究。

另请注意，有一种称为“无块”的东西，它类似于无锁，只是您知道您始终可以提交工作而无需重试。设计一个无块算法更难，但争用并不重要，因此其他两个无锁问题就消失了。注意：Kerrek SB 的答案中的“并发计数器”示例根本不是无锁的，但实际上是无块的。

于 2012-12-23T15:19:48.283 回答
7

“无锁”的想法并不是真的没有任何锁，这个想法是通过使用一些允许我们在大多数操作中不使用锁的技术来最小化锁和/或临界区的数量。

它可以使用乐观设计或事务内存来实现，在这种情况下，您不会为所有操作锁定数据，而只是在某些特定点上（在事务内存中执行事务时，或者当您需要在乐观设计中回滚时）。

其他替代方案基于某些命令的原子实现，例如CAS（比较和交换），它甚至允许我们在给定实现的情况下解决共识问题。通过在引用上进行交换（并且没有线程在处理公共数据），CAS 机制允许我们轻松实现无锁乐观设计（当且仅当没有人更改它时才交换到新数据，并且这是原子完成的）。

然而，为了实现其中之一的底层机制 -很可能会使用一些锁定，但如果正确使用这些技术，数据将被锁定的时间量（应该）保持在最短。

于 2012-12-23T14:51:46.450 回答
7

新的 C 和 C++ 标准（C11 和 C++11）引入了线程，并且线程共享原子数据类型和操作。原子操作为在两个线程之间运行的操作提供保证。一旦线程从这样的操作中返回，就可以确定该操作已经全部完成。

现代处理器上存在对此类原子操作的典型处理器支持，用于比较和交换 (CAS) 或原子增量。

除了原子之外，数据类型还可以具有“无锁”属性。这也许应该被称为“无状态”，因为这个属性意味着对这种类型的操作永远不会使对象处于中间状态，即使它被中断处理程序中断或另一个线程的读取落在中间的更新。

几种原子类型可能（或可能不是）无锁，有宏来测试该属性。总有一种类型可以保证是无锁的，即atomic_flag.

于 2012-12-23T16:53:09.127 回答