33

在互斥体上使用原子的主要原因是互斥体很昂贵，但是使用默认的内存模型，这atomics不是memory_order_seq_cst一样昂贵吗？

问题：使用锁的并发程序能否与并发无锁程序一样快？

如果是这样，除非我想用于原子，否则可能不值得付出努力memory_order_acq_rel。

编辑：我可能遗漏了一些东西，但基于锁的不能比无锁更快，因为每个锁也必须是一个完整的内存屏障。但是对于无锁，可以使用比内存屏障限制更少的技术。

所以回到我的问题，无锁是否比基于新 C++11 标准的默认锁更快memory_model？

“以性能衡量时，无锁 >= 基于锁”是真的吗？假设有 2 个硬件线程。

编辑2：我的问题不是关于进度保证，也许我在上下文之外使用“无锁”。

基本上，当您有 2 个线程共享内存时，您需要的唯一保证是，如果一个线程正在写入，则另一个线程无法读取或写入，我的假设是简单的原子compare_and_swap操作比锁定互斥锁快得多.

因为如果一个线程甚至从未接触过共享内存，您最终将无缘无故地一遍又一遍地锁定和解锁，但使用原子操作您每次只使用 1 个 CPU 周期。

关于评论，当争用很少时，自旋锁与互斥锁是非常不同的。

4

3 回答 3

55

无锁编程是关于进度保证：从最强到最弱，它们是无等待、无锁、无阻塞和阻塞。

保证是昂贵的，而且是有代价的。您想要的保证越多，您支付的费用就越多。通常，阻塞算法或数据结构（例如，带有互斥锁）具有最大的自由度，因此可能是最快的。另一个极端的无等待算法必须在每一步都使用原子操作，这可能会慢得多。

获得锁实际上是相当便宜的，所以如果没有对这个主题有深入的了解，你永远不要担心这一点。此外，使用互斥锁的阻塞算法更容易阅读、编写和推理。相比之下，即使是最简单的无锁数据结构也是长期专注研究的结果，每个结构都值得一个或多个博士学位。

简而言之，无锁或无等待算法以最差延迟换取平均延迟和吞吐量。一切都变慢了，但没有什么是非常慢的。这是一个非常特殊的特性，仅在非常特定的情况下（如实时系统）才有用。

于 2013-04-30T20:32:13.257 回答
1

锁往往需要比简单的原子操作更多的操作。在最简单的情况下，memory_order_seq_cst 的速度大约是锁定的两倍，因为锁定在其实现中往往需要至少两个原子操作（一个锁定，一个解锁）。在许多情况下，它需要的甚至更多。但是，一旦您开始利用内存订单，它会更快，因为您愿意接受更少的同步。

此外，您经常会看到“锁定算法总是与无锁定算法一样快”。这有点真实。基本思想是，如果最快的算法恰好是无锁的，那么没有无锁保证的最快算法也是相同的算法！但是，如果最快的算法需要锁，那么那些要求无锁保证的人必须去寻找更慢的算法。

通常，您会在一些低级算法中看到无锁算法，其中利用专用操作码的性能会有所帮助。在几乎所有其他代码中，锁定的性能不仅令人满意，而且更易于阅读。

于 2013-09-03T06:00:48.870 回答
1

问题：使用锁的并发程序能否与并发无锁程序一样快？

它可以更快：无锁算法必须始终保持全局状态处于一致状态，并且在不知道它们是否有效的情况下进行计算，因为在计算完成时状态可能已经改变，使其无关紧要，失去 CPU循环。

无锁策略使序列化发生在进程结束时，即计算完成时。在一个病态的情况下，许多线程可以做一个努力，只有一个努力会是有效的，其他的会重试。

无锁可能导致某些线程的饥饿，无论它们的优先级是什么，并且没有办法避免这种情况。（尽管除非存在疯狂的争用，否则线程不太可能长时间饿死重试。）

另一方面，“基于序列化计算和一系列副作用”（又名基于锁）算法不会在他们知道其他参与者不会阻止他们对特定锁定资源进行操作之前启动（保证由使用提供互斥体）。请注意，如果使用多个锁，它们可能会因需要访问另一个资源而无法完成，从而导致在设计不良的程序中需要多个锁时可能出现死锁。

请注意，这个死锁问题不在无锁代码的范围内，它甚至不能作用于多个实体：它通常不能基于两个不相关的对象进行原子提交 (1)。

因此，无锁代码没有死锁的机会是无锁代码弱点的标志：无法死锁是您工具的限制。一次只能持有锁的系统也无法死锁。

与基于锁的算法的范围相比，无锁算法的范围是微不足道的。对于很多问题，无锁甚至没有意义。

基于锁的算法是礼貌的，线程在做他们需要做的事情之前必须排队等待：这在每个线程的计算步骤方面是最有效的。但是必须在等待列表中排队线程是低效的：他们通常不能使用他们的时间片的结尾，所以它可能非常低效，因为有人试图做严肃的工作而一直被电话打断：他的注意力消失了，他永远无法达到最高效率，因为他的工作时间被切成小块。

(1) 您至少需要能够为此执行双重 CAS，即对两个任意地址的原子操作（不是双字 CAS，它只是更多位上的 CAS，可以轻松实现直到作为缓存线的自然 CPU 内存访问仲裁单元）。

于 2019-12-08T21:27:20.530 回答