Bil*_*eal 45 multithreading synchronization lock-free
Raymond Chen一直在做一个关于无锁算法的大型 系列 .除了函数的简单情况之外,似乎所有这些的主流模式是它们实现自己的锁.当然,没有处理器锁,但是在每个CPU上反复循环以确保一致性的概念非常类似于自旋锁.作为一个自旋锁,它们的效率将低于操作系统附带的一般锁,因为它们在等待其他线程时不会控制其量子.因此,每当有人来找我并说"但我的算法是无锁的"时,我的一般反应是"如此"？ InterlockedXxx
我很好奇 - 是否有可用的基准测试显示无锁算法比其完全锁定的算法有优势？
Ree*_*sey 27
通常,无锁算法每个线程的效率较低 - 正如您所提到的,您正在做更多工作,以实现无锁算法而不是简单锁.
但是,它们确实倾向于在面对争用时显着提高算法的整体吞吐量. 线程切换延迟和上下文切换,在很多线程上快速,大大降低了应用程序的吞吐量.有效锁定算法正在实现它们自己的"锁定",但它们以防止或减少上下文切换次数的方式这样做,这就是为什么它们倾向于执行锁定对应的原因.
话虽如此 - 大部分都取决于所讨论的算法(和实现).例如,我有一些例程,我设法切换到.NET 4的新并发集合,而不是使用以前的锁定机制,并测量了我的总算法速度超过30%的改进.话虽这么说,但与基本锁相比,您可以找到许多使用这些相同集合的性能降低的基准测试.与所有性能优化一样 - 在测量之前,您真的不知道.
Cha*_*via 19
除了InterlockedXxx函数的简单情况之外,似乎所有这些的主流模式是它们实现自己的锁.
这里的答案似乎都没有达到"无锁" CAS循环和互斥锁或自旋锁之间差异的核心.
最重要的区别是无锁的算法保证取得进展对自己 -没有其他线程的帮助.使用锁定或旋转锁定,任何无法获取锁定的可怜线程完全受拥有锁定的线程的支配.除了等待(通过忙碌等待或OS辅助睡眠)之外,无法获取锁定的可怜线程无能为力.
使用在CAS上循环的无锁算法,无论其他竞争线程正在做什么,每个线程都可以保证取得进展.每个线程基本上都控制着自己的命运.是的,它仍然可能需要多次循环,但它循环的次数受竞争线程数量的限制.在大多数情况下,它无法无限循环.(实际上,由于例如由于错误共享而导致失败的LL/SC循环,可能会发生实时锁定) - 但是线程本身可以再次采取措施来解决这个问题 - 它不是由于另一个持有锁的线程.
至于性能,取决于.我已经看到了无锁算法的公然例子,即使在高线程争用下,它们的锁定对应物完全超出了它们.在运行Debian 7的x86-64机器上,我比较了C++ Boost.Lockfree队列(基于Michael/Scott算法)和普通旧std::queue环绕队列之间的性能std::mutex.在高线程争用下,无锁版本几乎是两倍慢.
那为什么呢？那么,无锁算法的性能最终归结为实现细节.算法如何避免ABA？它如何实现安全的内存回收？有很多变种......标记指针,基于纪元的回收,RCU /静止状态,危险指针,一般流程范围的垃圾收集等等.所有这些策略都有性能影响,有些还限制了你的应用程序的一般性可以设计.一般来说,根据我的经验,引用计数方法(或标记指针方法)往往表现不佳.但是实现替代方案可能要复杂得多,并且需要基于线程本地存储或通用垃圾收集的更多内存回收基础结构.
Jer*_*fin 11
无锁不一定更快,但它可以消除死锁或活锁的可能性,因此您可以保证您的程序将始终在完成方面取得进展.有了锁,很难做出任何这样的保证 - 很容易错过导致死锁的一些可能的执行序列.
过去,这完全取决于.至少根据我的经验,速度差异往往更多地取决于实施中部署的技能水平,而不是它是否使用锁定.
小智 5
在x64上的Windows下,直接(在空闲列表前面没有组合数组)无锁空闲列表比基于互斥锁的空闲列表快一个数量级.
在我的笔记本电脑(Core i5)上,对于单个线程,无锁定,我每秒可获得约3100万个空闲列表操作,而互斥锁每秒约有230万个操作.
对于两个线程(在单独的物理内核上),无锁,我每个线程获得大约1240万个空闲列表操作.用互斥锁,我得到约80 千每秒操作.
至少在 Java 中，锁定本身可以非常快。同步关键字不会增加很多开销。您只需在循环中调用同步方法即可自行对其进行基准测试。
仅当存在争用时锁定才会变慢，并且被锁定的进程不是瞬时的。