我在某处（再也找不到该页面）读到无锁数据结构“对于某些工作负载”更有效，这似乎意味着有时它们实际上速度较慢，或者在某些情况下它们的收益可能为零。对我来说，使用锁定指令的约 100 个周期来执行原子操作听起来比进入睡眠状态并等待调度程序唤醒进程备份要快得多，所以在什么情况下无锁数据结构对我来说并不明显不如老式的互斥锁更可取。如果锁在 99% 的时间内都可用并且进程不必进入睡眠状态，那么互斥锁会更快吗？假设有合适的无锁数据结构可用，是否有一个好的经验法则可以知道该走哪条路？
问问题
8014 次
6 回答
54
实现无锁数据结构的常用方法是对不可变对象进行可变引用，并让任何想要更改结构的内容获取引用，生成应用适当更改的对象的新版本，然后进行比较交换指向新对象的引用。如果 CompareExchange 有效，那就太好了。如果没有，放弃新对象，重新获取引用，然后重新开始。
如果生成新对象的成本很低并且争用级别足够低，CompareExchange 通常可以正常工作，则此方法可以很好地工作。如果存在相当大的争用，并且如果生成新对象的速度很慢，则 N 个线程同时尝试更新可能需要 N^2 时间才能完成。举个极端的例子，假设有 100 个线程在 CPU 上运行，更新需要 100 毫秒的 CPU 时间（刚好超过一个时间片），并且所有 100 个线程都尝试一次更新一个对象。在最初的十秒内，每个线程将根据原始对象生成一个新对象。其中一个线程将成功执行 CompareExchange，而其他线程都将失败。然后在接下来的 9.9 秒内，99 个线程将生成对象的新版本，之后一个将成功发布其更新，而 98 个将失败。
于 2010-10-28T15:48:12.367 回答
7
无锁数据结构将以一种或另一种方式使用架构中的原子语义来执行其核心操作。当您这样做时，您可以使用机器的整个内部排除机制来确保数据的正确排序或隔离。互斥锁或临界区也这样做，但它只对单个标志执行一次。互斥锁或临界区速度慢的地方是锁获取失败（存在争用）。在这种情况下，操作系统还会调用调度程序来挂起线程，直到排除对象被释放。
因此，每当您的无锁数据结构对每个核心方法使用多个原子操作时，当单个锁屏蔽关键部分可以提供相同的语义时，这似乎是合乎逻辑的，那么实际上，使用操作系统提供的锁定机制确实比尝试构建自己的锁定机制更有意义。
于 2009-10-18T21:41:27.930 回答
6
我不知道如何让它变慢，但它肯定会让正确变得更难。在许多情况下，这两种方法在性能上几乎相同（或者当它需要 500 皮秒而不是 100 皮秒根本无关紧要时），然后选择最简单的方法 - 通常lock。
在极少数情况下，额外的性能是关键。如果是，我怀疑您最好使用已建立库中的预滚动模式实现。让无锁代码正常工作（并证明它在所有条件下都能正常工作）通常非常困难。
另请注意，某些环境提供了高于操作系统提供的互斥锁的锁定级别；mutex 行为，但没有一些开销（例如，Monitor在 .NET 中）。
于 2009-10-18T19:43:25.390 回答
1
我想在这部分答案中补充一点：“互斥锁或临界区速度慢的地方是锁获取失败（存在争用）。在这种情况下，操作系统还调用调度程序来暂停线程直到排除对象被释放。”
似乎不同的操作系统在锁定获取失败时可以采取不同的方法。我使用 HP-UX，例如它有一种更复杂的方法来锁定互斥锁。这是它的描述：
...另一方面，更改上下文是一个昂贵的过程。如果等待时间很短，我们宁愿不进行上下文切换。为了平衡这些要求，当我们尝试获取信号量并发现它被锁定时，我们要做的第一件事就是短暂的旋转等待。调用例程 psema_spin_1() 以旋转最多 50,000 个时钟周期以尝试获得锁定。如果我们在 50,000 次循环后未能获得锁，那么我们调用 psema_switch_1() 以放弃处理器并让另一个进程接管。
于 2009-10-19T13:23:04.337 回答
1
请记住，互斥锁可以很好地实现为无锁数据结构，因为它使用一个或几个原子对象来表示其状态。这是一个错误的二分法。
更好的是考虑是否需要允许多个线程等待访问某些操作集或阻塞直到发出信号。每个都需要一个等待线程队列。前者将等待访问同步区域的线程排队，而后者将等待信号的线程排队。Java 类AbstractQueuedSynchronizer并AbstractQueuedLongSynchronizer提供了这样一个队列——特别是CLH 队列——可以在其上构建互斥体、条件和其他基于队列的原语。
如果您的要求倾向于只让一个线程承担一组独占的工作，而其他线程仍然可以自由地继续其他工作，而不是等到它们自己也可以完成相同的工作，那么使用无锁技术是可能的。这样做是否会获得更快的运行时间取决于基准测试，取决于线程竞争这些同步控制的频率和数量，以及线程是否有其他工作可以独立执行。
于 2009-11-07T22:49:33.363 回答
0
效率取决于指标。无锁或无等待算法在抢占可能引入死锁或影响调度期限的系统中很重要。在这些情况下，处理不如正确性重要。
OP 将锁定视为互斥锁的替代方案。一些算法不需要访问共享数据结构。在这些情况下，生产者和消费者都可以同时访问相同的数据结构，而无需考虑对方。共享队列的示例允许单个读取器和单个写入器同时作用于共享实例。这满足了设备驱动程序写入消费者进程可以按需访问的数据的常见需求。
在不同级别的硬件支持下，可以允许进程之间更复杂的关系（参见 Herlihy (1991) 的分析） 。他总结说，无等待同步代表了与实现并发对象的传统基于锁定技术的质的突破。
这意味着仍然需要权衡取舍，但这不仅仅是在互斥锁和自旋锁之间进行选择。
一个经验法则仍然是关注正确性而不是性能。性能通常可以通过在问题上砸钱来实现，而满足要求通常更难。
于 2016-07-26T00:19:23.913 回答