什么是无锁多线程编程？

Question

我见过人/文章/ SO帖子,他们说他们设计了自己的"无锁"容器,用于多线程使用.假设他们有不使用性能击球模量特技(即每个线程只能插入基于某些模)的数据结构如何可以是多线程的,而且无锁???

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

Answer 1

无锁编程的关键是使用硬件内在的原子操作.

事实上,即使锁本身也必须使用那些原子操作!

但锁定和无锁编程之间的区别在于,无锁程序永远不会被任何单个线程完全停止.相比之下,如果在一个锁定程序中,一个线程获得一个锁,然后无限期地被挂起,整个程序就被阻止,无法取得进展.相比之下,即使单个线程无限期暂停,无锁程序也可以取得进展.

这是一个简单的例子:并发计数器增量.我们提出两个版本都是"线程安全的",即可以同时多次调用.首先是锁定版本:

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_*同时调用该函数.在锁定版本中,在锁定线程解锁互斥锁之前,任何线程都无法进行.相比之下,在无锁版本中,所有线程都可以取得进展.如果一个线程被搁置,它就不会分担工作,但其他人都可以继续工作.

值得注意的是,通常无锁编程可以交换吞吐量和平均延迟吞吐量以实现可预测的延迟.也就是说,如果没有太多的争用(由于原子操作很慢并影响系统的其他部分),无锁程序通常比相应的锁定程序更少完成,但它保证永远不会产生不可预测的大的延迟.

Answer 2

对于锁,我们的想法是你获得一个锁,然后知道其他人不能干涉你的工作,然后释放锁.

对于"无锁",这个想法是,你做你的工作,在其他地方,然后尝试原子致力于这项工作,以"看得见的状态",然后重试,如果你失败.

"无锁"的问题是:

• 很难为一些不重要的东西设计一个无锁算法.这是因为只有很多方法可以执行"原子提交"部分(通常依赖于原子"比较和交换",用不同的指针替换指针).
• 如果有争用,它的表现比锁更差,因为你反复做的工作被丢弃/重试
• 设计一个既正确又"公平"的无锁算法几乎是不可能的.这意味着(在争论中)某些任务可能是幸运的(并且反复提交他们的工作并取得进展),而有些任务可能非常不幸(并且反复失败并重试).

这些事物的组合意味着它只适用于低争用的相对简单的事情.

研究人员设计了诸如无锁链表(和FIFO/FILO队列)和一些无锁树之类的东西.我认为没有比这更复杂的东西了.对于这些东西是如何工作的,因为它很难复杂.最理智的方法是确定您感兴趣的数据结构类型,然后在Web上搜索相关研究数据结构的无锁算法.

另请注意,有一种称为"无块"的东西,它就像无锁,除了你知道你总是可以提交工作而不需要重试.设计一个无块算法更难,但争用并不重要,因此其他两个无锁问题就会消失.注意:Kerrek SB答案中的"并发计数器"示例根本不是锁定的,但实际上是无块的.

Answer 3

新的 C 和 C++ 标准（C11 和 C++11）引入了线程以及线程共享原子数据类型和操作。原子操作为两个线程之间发生竞争的操作提供了保证。一旦线程从此类操作返回，就可以确定该操作已完整完成。

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

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

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

Answer 4

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

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

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

然而，为了实现其中之一的底层机制 -最有可能使用一些锁定，但如果正确使用这些技术，则将（假设）锁定数据的时间量保持在最低限度。