无锁算法的性能真的比全锁算法好吗？

| 雷蒙德·陈（Raymond Chen）在无锁算法方面进行了大量研究。除了简单的“ 0”功能外，似乎所有这些的通用模式是它们实现自己的锁。当然，没有处理器锁，但是在每个CPU上不断循环以确保一致性的概念非常像自旋锁。作为自旋锁，它们将比操作系统附带的常规锁效率更低，因为它们在等待其他线程时不会产生对量子的控制。因此，每当有人来找我说“但是我的算法是无锁的”时，我的一般回答是“那么”？我很好奇-是否有基准可以显示无锁算法比全锁算法有优势？

已邀请:

10 个回复

谦响局豢报

通常，无锁算法对每个线程的效率较低-正如您提到的，与简单锁相比，要实现无锁算法，您需要做更多的工作。但是，面对竞争，它们确实确实可以显着提高整个算法的整体吞吐量。线程切换延迟和上下文切换在许多线程上速度很快，从而极大地降低了应用程序的吞吐量。无锁算法有效地实现了自己的“锁”，但是它们这样做的方式是防止或减少上下文切换的数量，这就是为什么它们倾向于不执行其对应的锁的原因。话虽这么说-大多数取决于所讨论的算法（和实现）。例如，我有一些例程可以设法切换到.NET 4的新并发集合，而不是使用以前的锁定机制，并且在我的总算法速度上测得的改进超过30％。话虽如此，与基本锁相比，您可以找到许多基准测试，这些测试使用某些相同的集合显示性能降低。与所有性能优化一样，您真的不知道，直到您进行测量。

良阑纠苫

除了InterlockedXxx函数的简单情况之外，似乎所有这些的普遍模式是它们实施自己的锁。这里的任何答案似乎都没有真正引起“无锁” CAS循环与互斥锁或自旋锁之间区别的核心。重要的区别在于，无需其他线程的帮助，就可以保证无锁算法能够自己取得进步。使用锁或自旋锁，任何无法获取锁的不良线程将完全由拥有该锁的线程决定。不能获取锁的不良线程只能等待（通过繁忙的等待或操作系统辅助的睡眠），而不能做任何事情。使用在CAS上循环的无锁算法，无论其他竞争线程在做什么，都可以确保每个线程都取得进展。每个线程本质上都在控制自己的命运。是的，它可能仍然必须循环很多次，但是循环的次数受竞争线程数的限制。在大多数情况下，它不能无限循环。（实际上，由于例如LL / SC循环由于错误共享而不断失败），可能会发生实时锁定-但线程本身也可以采取措施来解决此问题-并非如此受到另一个拿着锁的线的摆布。至于性能，这取决于。我已经看到，即使在高线程争用情况下，无锁算法的公然示例也完全比其无锁算法优越。在运行Debian 7的x86-64机器上，我比较了C ++ Boost.Lockfree队列（基于Michael / Scott算法）与纯旧的ѭ1包围by2的性能。在高线程争用的情况下，无锁版本的运行速度几乎是后者的两倍。那为什么呢？好吧，无锁算法的性能最终取决于实现细节。该算法如何避免ABA？它如何完成安全的内存回收？有很多变体...标记指针，基于时期的回收，RCU /静态，危险指针，整个过程范围内的垃圾回收等。所有这些策略都对性能产生影响，并且某些策略还对应用程序的总体设置产生了限制。可以设计。一般来说，根据我的经验，引用计数方法（或标记指针方法）的性能往往较差。但是替代方案的实现可能要复杂得多，并且需要基于线程本地存储或广义垃圾收集的更多内存回收基础结构。

渴翅吮斡撤

无锁不一定会更快，但是它可以消除死锁或活锁的可能性，因此您可以保证程序始终会在完成过程中取得进展。使用锁，很难做出任何保证-错过可能导致死锁的某些执行序列太容易了。除此之外，这一切都取决于。至少根据我的经验，速度差异往往更多地取决于实现中部署的技能水平，而不是是否使用锁。

钾涎净介

在x64上的Windows下，一个简单的（不包含在自由列表前面的合并数组）无锁定的自由列表大约比基于互斥锁的自由列表快一个数量级。在我的笔记本电脑（Core i5）上，对于单线程，无锁，我每秒可获得约3100万个freelist操作，而对于互斥锁，则约为每秒230万操作。对于两个线程（在单独的物理内核上），使用无锁功能时，每个线程获得约1,240万个自由列表操作。使用互斥锁，我每秒可获得约80千次操作。

抹持奠糙驰

无锁算法绝对可以比阻塞算法更快。但是当然反之亦然。假设实现比锁定计数器部分更好，则唯一的限制因素是竞争。采取两个Java类ConcurrentLinkedQueue和LinkedBlockingQueue。在适度的实际竞争中，CLQ的性能要比LBQ高很多。在争用激烈的情况下，使用挂起线程将使LBQ表现更好。我不同意user237815。同步关键字不需要像以前那样多的开销，但是相对于无锁算法，与单个CAS相比，它确实具有大量的开销。

骚瓤

真正的无锁算法的主要优点是，即使任务被搁置，它们也很健壮（请注意，与“不使用锁”（*）相比，无锁是更严格的条件）。尽管避免不必要的锁定具有性能优势，但性能最佳的数据结构通常是那些在许多情况下都可以进行锁定但可以使用锁定来最大程度地减少抖动的数据结构。（*）我已经看到过一些尝试“多锁”多生产者队列的方法，在这种情况下，错误时间安排生产者的行为将阻止消费者在完成工作之前看不到任何新物品。这样的数据结构不应该真正被称为“无锁”。一个被阻止的生产者不会阻止其他生产者取得进步，而是可以任意地阻止消费者。

捻盒愧杯

至少在Java中，锁定本身非常快。 synced关键字不会增加很多开销。您可以通过在循环中调用同步方法自己对它进行基准测试。只有在发生争用时，锁定才会变慢，并且被锁定的过程不是瞬时的。

长拳

最近在JavaOne上，俄罗斯Oracle员工（专门研究Java性能和基准）显示了一些有关使用CAS（实际上是无锁，高级自旋锁）和经典锁（java）对简单int计数器进行并行访问时每秒操作的度量。 .util.concurrent.locks.ReentrantLock） http://dl.dropbox.com/u/19116634/pics/lock-free-vs-locks.png //对不起，我无法粘贴图像据此，自旋锁只有在少数线程尝试访问监视器之前才具有更好的性能。

荒劫娇噬

无锁还具有不睡觉的优点。内核中有一些地方不允许您进入睡眠状态-Windows内核中有很多地方-痛苦地限制了您使用数据结构的能力。

淑灯

是的，无锁可确保进度，但是除非您手动中止某些平台上可能发生的线程或在关键部分分配内存，并退出内存异常或类似的愚蠢行为，否则不需要。如果执行效果不佳，则正确实施的自旋锁几乎总是会击败无锁方法，因为通常您是第一次或在尝试不成功后会做更多的工作。如果您使用比较交换指令使旋转时间短并且使cpus不堪重负和/或在给线程时间片分配给其他线程一段时间后不退缩（这给了计划外线程唤醒和释放锁的机会），那么无锁代码会更好地执行。除此之外，我认为这是不可能的。我既不感兴趣，也没有兴趣使用自旋锁不适合的复杂数据类型，但我仍然觉得设计合理的基于锁的算法几乎总是会更好。我可能是错的。

要回复问题请先登录或注册

无锁算法的性能真的比全锁算法好吗？

10 个回复

发起人

synchronization

multithreading

lock_free

问题状态

无锁算法的性能真的比全锁算法好吗？

与内容相关的链接

10 个回复

发起人

synchronization

multithreading

lock_free

问题状态