何时无锁数据结构的性能低于互斥(互斥)？

Question

我读到某处(无法找到页面)锁定免费数据结构对于"某些工作负载"更有效,这似乎意味着有时它们实际上更慢或者在某些情况下它们的增益可能为零.对锁定指令进行大约100次循环命中来执行原子操作听起来要快得多,而不是等待调度程序将进程重新唤醒,所以对于我来说,在什么情况下无锁数据结构不是很明显比旧式的互斥体更不可取.如果锁定在99%的时间内可用且进程无需进入休眠状态,那么互斥锁会更快吗？假设有合适的无锁数据结构,是否有一个很好的经验法则可以知道哪条路可用？

Answer 1

实现无锁数据结构的常用方法是对不可变对象进行可变引用,并且有任何想要更改结构的东西获取引用,生成应用了适当更改的对象的新版本,然后是CompareExchange指向新对象的引用.如果CompareExchange有效,那很好.如果没有,抛弃新对象,重新获取参考,然后重新开始.

如果生成新对象的价格便宜且争用程度足够低以至于CompareExchange通常可以正常工作,那么这可以很好地工作.如果存在相当大的争用,并且如果生成新对象很慢,则N个线程同时尝试更新可能需要N ^ 2时间才能完成.作为一个极端的例子,假设在CPU上运行100个线程,更新需要100ms的CPU时间(仅在时间片上),并且所有100个线程都尝试一次更新对象.在前十秒内,每个线程将根据原始对象生成一个新对象.其中一个线程将成功执行CompareExchange,而其他线程将全部失败.然后在接下来的9.9秒内,99个线程将生成该对象的新版本,之后一个将成功发布其更新,98将失败.

Answer 2

无锁数据结构将以这种或那种方式使用来自您的体系结构的原子语义来执行其核心操作.执行此操作时,您可以使用计算机的整个内部排除机制来确保正确的数据排序或隔离.互斥或临界区也可以这样做,但它只对一个标志执行一次.互斥锁或关键部分缓慢的情况,即锁定获取失败(存在争用).在这种情况下,操作系统还会调用调度程序暂停线程,直到释放排除对象为止.

因此,它似乎是合乎逻辑,只要你锁定更少的数据结构,每个核心的方法是使用多个原子操作时,一个锁屏蔽关键部分可以提供相同的语义和存在往往是非常小的争论,在实践中,对于有问题的数据结构,事实上,使用操作系统提供的锁定机制比尝试构建自己的锁定机制更有意义.

Answer 3

我不知道让它变慢,但它肯定会让它变得更难.在许多情况下,这两种方法的性能几乎完全相同(或者如果它只需要500皮秒而不是100皮秒,那就无所谓),那么选择最简单的方法 - 通常lock.

当额外的性能是关键时,极少数情况下; 如果是的话,我怀疑你最好使用已建立的库中的预卷模式实现.让无锁代码正常工作(并证明它在所有条件下都能正常工作)通常非常困难.

另请注意,某些环境提供的锁定级别高于OS提供的互斥锁; 互斥行为,但没有一些开销(例如,Monitor在.NET中).