无锁algorithm是否真的比locking对象更好？

Raymond Chen 在无 锁 algorithm 方面 做了大量的工作 。 除了InterlockedXxx函数的简单情况之外，似乎所有这些模式都是他们实现自己的锁 。 当然，没有处理器锁，但是为了确保一致性，在每个CPU上循环重复的概念非常像自旋锁。 作为自旋锁，它们将比操作系统附带的通用锁效率低，因为它们在等待其他线程时不会控制其量子块。 因此，当有人来找我说“但是我的algorithm是无锁的”时，我的总体回答是“如此”？

我很好奇 – 是否有基准显示locking自由algorithm有优势locking全面的对手？

Answer 1

一般来说，无锁algorithm在每个线程中效率较低 – 正如你所提到的，你正在做更多的工作来实现一个无锁algorithm，而不是一个简单的锁。

然而，他们确实倾向于在竞争面前大大提高algorithm的整体吞吐量。 线程切换延迟和上下文切换 （在很multithreading中快速切换 ）会显着减慢应用程序的吞吐量。 locking自由algorithm有效地实现了自己的“locking”，但是它们以阻止或减less上下文切换次数的方式这样做，这就是为什么他们倾向于执行locking对应的原因。

这就是说 – 这大部分取决于问题的algorithm（和实现）。 例如，我已经有了一些例程，可以切换到.NET 4的新并发集合，而不是使用以前的locking机制，并且在总algorithm速度方面已经testing了近30％的改进。 这就是说，有很多基准你可以发现，与基本的锁相比，使用这些相同的集合中的一些显示性能下降。 和所有的性能优化一样 – 直到你测量，你真的不知道。

Answer 2

除了InterlockedXxx函数的简单情况之外，似乎所有这些模式都是他们实现自己的锁。

这里没有一个答案似乎真正成为“无锁” CAS循环与互斥锁或自旋锁之间差异的核心。

最重要的区别是，无锁algorithm保证自己取得进步 – 没有其他线程的帮助。 使用锁或自旋锁，任何不能获得锁的可怜线程完全由拥有该锁的线程支配。 可怜的线程无法获得锁，除了等待 （通过繁忙的等待或OS辅助的睡眠）之外，什么都不能做。

通过在CAS上循环的无锁algorithm，无论其他竞争线程在做什么，每个线程都能保证取得进展。 每个线程本质上都是在控制自己的命运。 是的，它仍然可能需要循环很多次，但循环的次数受到竞争线程数量的限制。 它绝大部分不能无限循环。 （实际上，由于例如由于错误共享而保持失败的LL / SC循环，可能发生实时locking），但是线程本身可以采取措施来处理这个问题 – 这不是在摆布另一个线程持有一个锁。

至于performance，这取决于。 我已经看到了无锁algorithm的明显例子，即使在高线程争用的情况下，它们的lockingalgorithm也完全失败了。 在运行Debian 7的x86-64机器上，我比较了C ++ Boost.Lockfree队列（基于Michael / Scottalgorithm）和std::mutex的普通旧std::queue环境之间的性能。 在高线程争用下，无锁版本几乎是慢一倍。

那么为什么呢？ 那么，无锁algorithm的性能最终归结为实现细节。 algorithm如何避免ABA？ 它如何完成安全的内存回收？ 有很多变体…标记的指针，基于时代的回收，RCU /静态状态，危险指针，一般的进程垃圾收集等等。所有这些策略都有性能影响，有些还限制了你的应用程序可以devise。 一般来说，根据我的经验，引用计数方法（或标记指针方法）往往performance不佳。 但是替代scheme可能要复杂得多，需要更多的基于线程本地存储或广义垃圾收集的内存回收基础设施。

Answer 3

无锁不一定更快，但它可以消除死锁或活锁的可能性，所以你可以保证你的程序将总是进展到完成。 有了锁，就很难做出这样的保证 – 错过一些可能导致死锁的执行顺序太容易了。

过去这一切都取决于 至less在我的经验中，速度上的差异往往取决于实施中部署的技能水平，而不是它是否使用locking。

Answer 4

在64位的Windows下，一个简单的（freelist前没有组合数组）无锁freelist比基于mutex的freelist快一个数量级。

在我的笔记本电脑（酷睿i5）上，对于一个单线程，无锁的情况下，我每秒获得大约3,100万次freelist操作，而互斥量大约为每秒230万次操作。

对于两个线程（在不同的物理内核上），无锁的情况下，每个线程可以获得大约1240万次freelist操作。 有了互斥量，我每秒可以完成大约80 万次的操作。

Answer 5

无锁algorithm可以绝对比它们的阻塞对应更快。 当然，反过来也是如此。 假设执行性能比locking计数器部分更好，唯一的限制因素是争用。

以两个Java类，即ConcurrentLinkedQueue和LinkedBlockingQueue。 在中度现实世界的争夺下，CLQ的performance优于LBQ。 争议较大的情况下，挂起线程的使用将使LBQ的性能更好。

我不同意user237815。 synchronized关键字不需要像以前那样花费太多的开销，但是相对于无锁algorithm，与单个CAS相比，它有相当多的开销。

Answer 6

真正的无锁algorithm的主要优点在于，即使任务被取消，它们也是健壮的（请注意，无锁是比“不使用锁”（*）更难的条件）。 尽pipe避免不必要的locking具有性能优势，但是性能最好的数据结构通常是那些可以在多种情况下操作locking的数据结构，但是可以使用锁来最小化抖动。

（*）我看到一些企图在“无锁”的多生产者队列中，一个制造商在错误的时间得到了制止，这将阻止消费者在完成其工作之前看到任何新的项目）。 这样的数据结构不应该被称为“无锁”。 一个被封锁的生产者不会阻止其他生产者进步，但可能会任意地阻止消费者。

Answer 7

在Java中，至less，自己locking可以很快。 synchronized关键字不会增加大量开销。 你可以通过在一个循环中调用一个synchronized方法来自己进行基准testing。

当争用时，locking只会变慢，并且locking的过程不是即时的。

Answer 8

最近在JavaOne俄罗斯甲骨文员工（专门从事Java性能和基准testing）已经展示了一些关于并行访问简单的int计数器每秒操作的测量结果，使用CAS（实际上是无锁的，高级别的自旋锁）和经典的锁.util.concurrent.locks.ReentrantLock）

http://dl.dropbox.com/u/19116634/pics/lock-free-vs-locks.png //抱歉，我无法粘贴图片

据此，只有less数线程试图访问监视器，自旋锁才具有更好的性能。

Answer 9

无锁也有它不睡觉的好处。 在内核中有些地方你不能入睡 – Windows内核有一大堆 – 而且这很难限制你使用数据结构的能力。