无锁数据结构在什么情况下比有锁的更快?

10
我目前正在阅读Anthony WilliamsC++ Concurrency in Action一书,其中包括几个无锁数据结构实现。在关于无锁数据结构的章节中,Anthony写道:

这带来了另一个无锁和无等待代码的缺点:虽然它可以增加对数据结构上操作的并发潜力并减少单个线程等待的时间,但它可能会降低整体性能。

确实,我测试了书中描述的所有无锁堆栈实现,并将其与前几章中的基于锁的实现进行了比较。似乎无锁代码的性能总是低于基于锁的堆栈。

在什么情况下无锁数据结构更优且必须被优先选择?


1
多少数据?锁定版本花费了多长时间被锁定? - doctorlove
"必须被优先考虑吗?" 必须是一个非常强烈的词。 - UKMonkey
我喜欢无锁数据结构,因为它们有助于避免互斥死锁。当存在大量竞争时,它们会变得较慢,就像自旋锁一样。 - brian beuning
简而言之:只要没有线程失败地获取锁,基于锁的方式是很好的。但一旦发生这种情况,几乎肯定会发生上下文切换,非常糟糕。 如果有多个线程很可能同时访问同一个关键部分(竞争情况很多),无锁方式将表现更好。 - sbabbi
1
除了其他用例,它们可以非常适合只读数据。使用类似RCU的东西,读者永远不必等待,甚至根本不必执行原子操作。同步的负担可以完全放在编写者身上。 - Peter Cordes
6个回答

10

无锁结构的一个好处是不需要上下文切换。然而,在现代系统中,无竞争锁也可以避免上下文切换。为了从无锁算法中获得性能优势,需要满足以下几个条件:

  • 竞争必须很高
  • 应该有足够的CPU核心,以便旋转线程可以连续运行(理想情况下,应该固定在自己的核心上)

我认为这两个条件互相抵消了。如果我们有足够的CPU核心,就会减少争用。 - Ankush G
1
@AnkushG 不是很明白,为什么? - SergeyA
3
争用并不是由于缺乏 CPU 核心引起的;相反,当多个核心需要同时独占访问相同的数据时,才会出现争用。 - Jeremy Friesner

10

我曾经进行过性能研究。当线程数较少时,无锁数据结构和锁定数据结构的表现相当。但随着线程数的增加,在某一点上,锁定数据结构的性能会急剧下降,而无锁数据结构可以扩展到数千个线程。


@Donghui Zhang,你说得对,这在很大程度上取决于线程数量和每个节点存储的数据大小。我测试了1000个读写线程,这种无锁设计的情况看起来更有利。 - bobeff

4

这取决于碰撞的概率。

如果碰撞很可能发生,那么互斥锁是最优解。例如:两个线程不断向容器末尾推送数据。仅使用无锁技术只有1个线程会成功,另一个则需要重试。在此情况下,阻塞和等待更好。

但如果您有一个大容器,而且这2个线程将访问容器的不同区域,那么很可能不会有碰撞。例如:一个线程修改容器的第一个元素,而另一个线程修改最后一个元素。在这种情况下,重试的概率非常小,因此此处使用无锁技术更好。

无锁技术的另一个问题是自旋锁(内存占用量大),以及原子变量的整体性能和某些变量的约束条件。

例如,如果您有约束条件x == y,必须为真,则不能对x和y使用原子变量,因为您无法同时更改两个变量,而lock()则可以满足约束条件。


4
了解哪种更好的唯一方法是对每种情况进行性能分析。结果将因使用情况而异,不同 CPU、不同架构和年份也会有巨大差别。今天最好的可能明天就不是。因此,始终测量并保持测量。
如果没有争用,你所做的事情应该无关紧要。无冲突情况下应始终很快。如果不是这样,则需要调整到无争议情况的不同实现。一个实现可能比另一个实现使用更少或更快的机器指令,但差异应该很小。测试,但我预计结果几乎相同。
接下来看看具有(高)争用的情况:
同样可能需要调整为针对争议情况的实现。一个锁定机制与其他锁定机制不同,类似于无锁方法。
线程<=核心
可以合理地假设所有线程都将运行并执行工作。可能会有短暂的暂停,其中线程被中断,但这确实是例外。这当然只适用于只有一个应用程序执行此操作的情况。所有 CPU 密集型应用程序的线程都加起来在这种情况下。
现在,带锁定的线程将获取锁定并开始工作。其他线程可以等待锁定变为可用并在锁定空闲时立即进行反应。它们可以忙等待或睡眠较长的时间,没有太大关系。锁定限制您只能使用 1 个线程进行工作,并且在切换锁定时几乎不浪费任何 CPU 周期。
另一方面,无锁数据结构都会落入某些尝试和重复循环中。它们将执行工作,并在某些关键点上尝试提交该工作,如果存在争用,则会失败并再次尝试。通常会重复许多昂贵的操作。争用越多,浪费的工作就越多。更糟糕的是,所有对缓存和内存的访问都会减慢最终成功提交工作的线程。因此,您不仅无法更快地前进,而且还会拖慢进度。
对于需要比锁定指令更多 CPU 周期的任何工作负载,我始终会选择锁定方法而非无锁定方法。那里确实不需要太多工作,只留下了锁定自己使用这样一个指令的微不足道情况。内置的原子类型就是这种情况,通常 CPU 具有在硬件中以单个指令无锁定方式执行这些原子操作的操作码,速度相对较快。最终锁将使用这样的指令本身,永远无法比如此微不足道的情况更快。
线程>>核心
如果线程数远远超过核心数,则任何时候只有一小部分线程可以运行。休眠的线程很可能会保持锁定。所有需要锁定的其他线程都必须进入休眠状态,直到保持锁定的线程再次唤醒它们。这可能是锁定数据结构的最坏情况。没有人能做任何工作。
现在有锁的实现(借助操作系统的帮助),其中一个线程试图获取锁会使持有锁的线程接管,直到它释放锁。在这种系统中,浪费仅减少到线程之间的上下文切换。
锁还存在一个问题叫做“雷鸣般的兽群”问题。如果有100个线程在等待一个锁并且该锁被释放,那么根据您的锁实现和操作系统支持,100个线程将会被唤醒。其中一个线程将获得锁,而99个线程则会浪费时间尝试获取锁、失败并回去休眠。你真的不想要一种实现锁受到“雷鸣般的兽群”问题的困扰。
无锁数据结构在这里开始发挥作用。如果一个线程取消调度了,则另一个线程将继续他们的工作并成功地提交结果。该线程在某个时候会再次唤醒并无法提交它的工作并重试。浪费在于被取消调度的线程所做的工作。
3.核心数 < 线程数 < 2 * 核心数
当线程数接近核心数时,存在一个灰色区域。阻塞线程正在运行的机会仍然很高。但这是一个非常混乱的区域。哪种方法更好的结果是相当随机的。我的结论是:如果你没有大量的线程,那么就尽力保持 <= 核心数。
还有一些想法:
有时候,一旦开始工作,需要按特定顺序完成工作。如果一个线程被取消调度,您不能跳过它。您会在某些数据结构中看到这种情况,其中代码将检测到冲突,一个线程实际上完成了不同线程开始的工作,而它自己无法提交结果。现在,如果另一个线程被取消调度,这真的很好。但如果它正在运行,做两次工作就是浪费的。因此,具有此方案的数据结构真正面向方案2。
随着今天进行的移动计算越来越多,考虑您的代码的功率使用变得越来越重要。有许多方法可以优化代码来改变功率使用。但真正使代码使用更少功率的唯一方法是休眠。你会听到更多的是“竞赛休眠”。如果您可以使代码运行得更快,以便它可以更早地睡眠,那么您可以节省电力。但重点在于“更早地睡眠”,或者我应该说“更多地睡眠”。如果有2个线程运行了75%的时间,它们可能会在75秒内解决您的问题。但是,如果您可以通过交替锁定来使用2个线程每次运行50%的时间来解决相同的问题,那么它们需要100秒。但第一个也使用了150%的cpu功率。时间较短,确实如此,但75 * 150%= 112.5 > 100 * 100%。从电源角度来看,较慢的解决方案胜出。锁允许您在无锁状态下交换速度和功率。请记住这一点,并平衡您对速度的需求与充电手机或笔记本电脑的需求。

1
互斥锁的设计很少会比无锁设计表现得更好。那么随之而来的问题是,为什么有人会使用互斥锁而不是无锁设计呢?
问题在于,无锁设计可能很难实现,并需要大量设计才能保证可靠性;而互斥锁相对简单(比较而言),而且在调试时甚至更加困难。因此,人们通常首选使用互斥锁,一旦争用已被证明是瓶颈,就会迁移到无锁设计。

7
“互斥锁的设计很少会像无锁设计那样表现出色。” 我认为这并不完全正确。看起来这基于“理论”而非经验。首先,“无锁”并非真正意义上的无锁,锁是在硬件层面上完成的。其次,“无锁”并不意味着“无延迟”。 - Slava
3
如果将一个数据结构设计成无锁,意味着通常简单的操作现在需要一系列的原子操作。而对于轻度争用的数据结构来说,使用锁可能会带来好处。 - Peter Cordes
1
我经常看到学术论文中使用无锁数据结构(例如优先队列)的做法,但与基于轻量级细粒度用户级锁的实现相比,这种做法只是浪费时间。 - Anton

0
我认为这些答案中缺少的一件事是锁定期。如果您的锁定期非常短,即在获取锁之后执行一个非常短的任务(例如增加一个变量),那么使用基于锁的数据结构会带来不必要的上下文切换、CPU调度等。在这种情况下,无锁是一个很好的选择,因为线程只会旋转很短的时间。

1
一个好的互斥锁在非竞争情况下不涉及任何上下文切换或系统调用。(https://preshing.com/20111124/always-use-a-lightweight-mutex/) 当然,如果你只是想增加一个单一的标量计数器,那么无锁原子肯定是显而易见的选择。在某些机器上,这意味着根本没有自旋。但在更常见的情况下,CAS重试循环可能需要在极少数情况下重试几次。 - Peter Cordes

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接