无锁同步

Question

我的问题与多线程无锁同步有关。我想知道以下内容：

1. 实现无锁同步的通用方法有哪些？我在某处读到过LockFreePrimitives，例如CompareAndExchange（CAS）或DoubleCompareAndExchange（DCA），但没有给出解释。有什么方法可以最小化锁的使用？

2. Java/.NET如何实现并发容器？他们使用锁还是无锁同步？

谢谢。

- Bober02

Answer 1

以下是一些通用的方法，可以最小化锁的使用，假设您的算法具有某些可利用的特征：

1. 当更新单个数值变量时，可以使用非阻塞原语（例如CAS、atomic_increment等）。它们通常比经典的阻塞临界区域（锁、互斥）快得多。 2. 当数据结构由多个线程读取，但只由一个或少数几个线程写入时，明显的解决方案是使用读写锁，而不是完全锁定。 3. 尝试利用细粒度锁定。例如，不要使用单个锁锁定整个数据结构，而是看看是否可以使用多个不同的锁来保护数据结构的不同部分。 4. 如果您依靠锁的隐式内存栅效果来确保跨线程可见性的单个变量，只需使用volatile（如果可用）。 5. 有时，在实践中使用条件变量（及其关联的锁）会太慢。在这种情况下，volatile忙旋转更有效率。

在这个主题上的更多好的建议请参见这里：http://software.intel.com/en-us/articles/intel-guide-for-developing-multithreaded-applications/ 在另一个SO问题中也有一篇不错的文章：无锁多线程是专家级别的（不要被标题吓到）。

还有一个最近讨论的无锁Java实现atomic_decrement：非阻塞方法中的饥饿

---

¹ 这里使用的 volatile 是指像 Java 这样的语言，在内存模型中定义了 volatile 的语义，但不适用于 C 或 C++，因为在跨线程内存模型引入之前，volatile 已经存在，并且不与之集成。这些语言中提供了类似的构造，例如 C++ 中的各种 std::memory_order 指定符。

- Tudor

---

你提出了一些好的观点，但第四点是错误的。volatile并不会像你期望的那样起作用。它可能会防止编译器进行某些优化，但不能防止处理器重新排序读取操作，因此无法替代屏障。 - ugoren

@PeterCordes 在Java中，volatile和C++中的atomic<T>之间的类比并不是非常精确。从语法上讲，C/C++和Java中的volatile基本相同：它们都是限定符，不会改变访问底层值的语法。从语义上讲（内存模型方面），volatile有点像一种受限制的atomic形式，其中您唯一能做的就是使用memory_order::acquire进行加载和使用memory_order::release进行存储。Java中的各种Atomic*类基本上是atomic<T>的直接等价物（通常情况下，Java是基于引用的）。 - BeeOnRope

我认为与C++相比，Java在内存模型方面并不容易受到批评。他们至少努力从一开始就拥有了（非正式的）内存模型，并且在Java 5（或4？）中将其形式化得很好 - 这比C和C ++要领先得多。他们赋予volatile的语义在表面上是相当合理的 - 实际上，人们在C / C ++中“自古以来”就使用volatile进行跨线程通信（因为这是唯一半可移植的方法），至少MSVC使用与Java相同的发布/获取语义来形式化此过程。 - BeeOnRope

当然，C/C++最初没有内存模型的原因也很明显：它们的引入（至少在C的情况下）先于进程内线程的广泛使用 - 但是从1990年到C++03或C++11（意见不一）期间仍然存在长时间的停滞期，自从线程爆发以来，它就被遗忘了。最后注意：即使是我对Java中“volatile”的描述也不完整：volatile中有一个“总访问顺序”组件，这在基本的获取/释放语义中不存在（这使得存储变得昂贵）。 - BeeOnRope

@BeeOnRope：已提交 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=83285 - Peter Cordes

Answer 2

有一些有用的方法可以使用无锁同步（就像@Tudor提到的那些）。但是我想警告大家一件事 - 无锁同步不能组合使用。

例如，你可能有一个通过compare&swap来维护的整数，这是可以的。你也可以通过无锁算法来维护一个队列（这有点棘手，但有好的算法可用），并且这个队列也是可行的。但是，如果你尝试使用计数器来计算队列中的元素数量，你会得到错误的答案。有时候，一个元素已经被添加了，但计数器还没有反映出来（或者相反），如果你信任它的话，就会出现错误（例如，你可能会尝试向一个已满的队列中添加元素）。

简而言之 - 每个元素可以自己保持一致，但彼此之间不一定保持一致。

- ugoren

Answer 3

比较和交换是有用的，但在某些生产者/消费者用例中，有一种更简单的（所谓的“无锁”）技术也很有用，因此我会提到它。

想象一下你有一个写入缓冲区的函数doWork()。

1. 线程A初始化一个易失性布尔变量（标志），并创建一个易失性缓冲区对象，doWork将输出到线程B（全局等）。
2. 线程A创建线程B，线程B调用doWork()。
3. 线程B的doWork()开始创建/写入缓冲区。完成后，它将布尔值设置为true。
4. 线程A可以轮询一个全局布尔标志，该标志最初为false。当它变为true（非false）时，它可以访问缓冲区对象中的数据，确保已完成。在轮询之间，线程A可以执行其他工作。（例如，在更新调用中仅轮询一次，而不等待真实值）。这没有考虑错误处理，但这也可以在缓冲区内处理。

这仅适用于A仅读取且B仅写入的情况，但这种用例对于“后台工作人员”线程而言相当常见。这只能在Java或C#上确保可行，因为易失性带有保证。

- Michael Chinen

---

你不能使用简单的布尔值进行同步。编译器和/或处理器可能会重新排序你的读取操作，导致错误。你可能认为首先读取了布尔值（并且看到它是真的），然后才读取缓冲区。但实际上（你得到了“半熟”的数据），读取操作可能会被颠倒。你需要一个信号量。 - ugoren

我相信永远不会出现线程A先读取并使用缓冲区的情况，因为它是在依赖于布尔值read的条件语句中读取的，而编译器不会改变这些内容。这就是为什么你可以写一个检查空指针的条件语句，然后在之后使用指针的原因。 - Michael Chinen

编译器重新排序遵循一定的规则，而这个技术也遵守了这些规则。除了我已经解释了编译器所遵守的条件情况。 - Michael Chinen

你正在忽略乱序执行。假设编译器按照你的期望完成了所有操作，你得到了如下机器码：mov var1,%eax; test %eax,%eax; jz somewhere; mov var2,%eax。读取 var2 是在读取并验证 var1 不为零之后进行的。但是 CPU 仍然可以重新排序，先读取 var2，再读取 var1（可能是因为 var2 在更近的缓存中）。如果 var1 最终为 0，则 var2 的值将被丢弃。但如果它最终不为零，则将使用旧值。 - ugoren

我现在明白你的观点了，非常感谢你详细地阐述了它。但是，由于volatile关键字的存在（这一点我应该提到），在某些语言中（如Java > 1.5和C#，但不包括C）实际上保证不会进行此类重排序，因此仍然可能。 在C中，您需要一些内存屏障。 - Michael Chinen