无锁多线程编程是什么？

Question

无锁多线程编程是什么？

c++cmultithreadingalgorithmlocking

51

我看到一些人/文章/SO帖子说他们为多线程使用设计了自己的“无锁”容器。假设他们没有使用性能受损的模数技巧（即每个线程只能基于某些模数插入），那么数据结构如何同时支持多线程和无锁？？？

这个问题适用于C和C ++。

- user997112

5

无锁通常不意味着“任何锁”，它的意思类似于事务内存，或者乐观设计，在这种情况下，您不会为每个操作使用锁，但是偶尔需要一些锁（用于回滚或执行事务）- 某种类型的锁将是必要的。 - amit

7

无锁通常指使用比较并交换硬件操作。 - brian beuning

在稍微更广泛的定义中，锁不仅指互斥体，还指可能“锁住”其他线程的潜力。最明显的例子是不释放互斥体，然而这是一个不使用互斥体的非无锁代码示例：while (X == 0) { X = 1 - X; } 给定正确的调度，两个线程可以一直停留在这个循环中。http://preshing.com/20120612/an-introduction-to-lock-free-programming/ - Bas Smit

4个回答

30

对于锁来说，它的意义在于你获取了一个锁之后就可以进行工作，而不会被其他人干扰，然后释放锁。

对于“无锁（lock-free）”来说，其意义在于你在其他地方完成工作，然后尝试将这些工作原子地提交到“可见状态”，如果失败则重试。

“无锁”的问题在于：

很难为非平凡问题设计无锁算法。这是因为只有很少的方法可以用于执行“原子提交”部分（通常依赖于将指针替换为另一个指针的原子“比较并交换”操作）。
如果存在争用情况，则性能不如锁，因为您不断执行被丢弃/重试的工作。
几乎不可能设计一个既正确又“公平”的无锁算法。这意味着（在争用情况下），某些任务可以很幸运（并且反复提交他们的工作并取得进展），而某些任务可以非常不幸（并且反复失败和重试）。

这些问题的组合意味着它只适用于低争用率下的相对简单的事物。

研究人员设计了像无锁链表（以及FIFO / FILO队列）和一些无锁树之类的东西。我认为没有比这些更复杂的东西了。对于这些东西的工作原理，因为它很难，所以也很复杂。最明智的方法是确定您感兴趣的数据结构类型，然后搜索网络以查找相关研究的无锁算法。

此外，请注意还有一种叫做“无阻塞（block-free）”的东西，它类似于无锁，但你知道你总是可以提交工作而不需要重试。它甚至更难设计出一个无阻塞算法，但争用并不重要，因此无锁的其他2个问题就消失了。 注意：Kerrek SB答案中的“并发计数器”示例根本不是无锁的，而实际上是无阻塞的。

- Brendan

@Nik-Lz：在80x86上，我期望++counter会被编译成一个单独的lock inc dword [counter]汇编指令，在这里CPU使用其缓存一致性协议确保它以原子方式发生，而且没有任何东西（甚至不是原始8086的古老的“总线锁定”行为）阻止其他线程或CPU。 - Brendan

9

"无锁"的概念并非完全没有任何锁，而是通过使用一些技术来最小化锁和/或关键部分的数量，从而使我们在大多数操作中不需要使用锁。

可以通过采用乐观设计或事务性内存来实现，其中你不需要为所有操作锁定数据，而只需在某些特定点上进行锁定（在事务性内存中进行交易时，或者在乐观设计中需要回滚时）。

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

然而，要实现其中一种机制，很可能会使用一些锁定，但如果正确使用这些技术，数据被锁定的时间应该尽量减少。

- amit

3

有些锁的参与让事情更有意义！ - user997112

请注意，如果您的硬件允许原子CAS操作，您应该能够在不使用任何锁的情况下实现乐观设计。(交换操作将是引用交换整个数据，并且没有线程实际上会在公共数据上工作) - amit

7

“无锁”与“lock free”没有涉及到任何锁定机制。 - Brendan

难道没有长期以来的证明表明，使用CAS可以完全不使用锁来编写任何算法吗？ - Tim Seguine

6

新的 C 和 C++ 标准(C11 和 C++11) 引入了线程，以及线程共享的原子数据类型和操作。原子操作为两个线程之间发生竞争的操作提供了保证。一旦一个线程从这样的操作返回，它可以确信该操作已经完全执行。

现代处理器上通常支持此类原子操作，例如比较并交换（CAS）或原子增量。

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

多个原子类型可以（也可以不）是无锁的，有宏来测试该属性。总有一种类型是保证无锁的，那就是atomic_flag。

- Jens Gustedt

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Kerrek SB · Accepted Answer

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

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

然而，锁定和无锁编程之间的区别在于，锁-free程序永远不会被单个线程完全阻塞。相比之下，在锁定程序中，如果一个线程获取锁然后无限期地挂起，整个程序就会被阻塞，无法取得进展。相比之下，无锁程序即使单个线程被无限期地挂起，也可以取得进展。

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

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_*函数。在加锁版本中，除非持有锁的线程释放互斥量，否则没有任何线程能够进展。相比之下，在无锁版本中，所有线程都可以取得进展。如果某个线程被阻塞，那么它就不能完成其工作，但其他所有线程仍然可以继续执行它们的工作。

值得注意的是，通常情况下，无锁编程会通过可预测的延迟来换取吞吐量和平均延迟。也就是说，如果竞争不是太激烈（因为原子操作很慢并且会影响系统的大部分其他部分），无锁程序通常会做得比相应的锁定程序少，但它保证永远不会产生不可预测的大延迟。