无锁同步 [英] Lock free synchronization

问题描述

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

My question is related to multithreading lock-free synchronization. I wanted to know the following:

1. 实现这一目标的一般方法是什么?我在某处阅读了有关 LockFreePrimitives 的内容，例如 CompareAndExchange (CAS) 或 DoubleCompareAndExchange (DCA)，但没有给出任何解释?有什么方法可以尽量减少锁的使用?

1. What are general approaches to achieve this? I read somewhere about LockFreePrimitives like CompareAndExchange (CAS) or DoubleCompareAndExchange (DCA) but no explanation for those were given? Any approaches to MINIMIZE use of locks?

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

How does Java/.NET achieve their concurrent containers? Do they use locks or lock-free synch?

提前致谢.

推荐答案

假设您的算法具有一些特定的可利用特性，这里有一些可以最大限度减少锁使用的通用方法:

Here are some general approaches that can minimize the use of locks, assuming your algorithm has some particular exploitable features:

1. 更新单个数值变量时，您可以使用非阻塞原语，例如 CAS、atomic_increment 等.它们通常比经典的阻塞临界区(锁、互斥锁)快得多.

1. When updating a single numeric variable, you can use non-blocking primitives such as CAS, atomic_increment, etc. They are usually much faster that a classic blocking critical section (lock, mutex).

当一个数据结构被多个线程读取，但只被一个或几个线程写入时，一个明显的解决方案是读写锁，而不是全锁.

When a data structure is read by multiple threads, but only written by one or few threads, an obvious solution would be a read-write lock, instead of a full lock.

尝试利用细粒度锁定.例如，与其使用单个锁锁定整个数据结构，不如看看您是否可以使用多个不同的锁来保护数据结构的不同部分.

Try to exploit fine grain locking. For example, instead of locking an entire data structure with a single lock, see if you can use multiple different locks to protect distinct sections of the data structure.

如果您依靠锁的隐式内存栅栏效应来确保跨线程的单个变量的可见性，只需使用 volatile¹(如果可用).

If you're relying on the implicit memory fence effect of locks to ensure visibility of a single variable across threads, just use volatile¹, if available.

有时，在实践中使用条件变量(和关联的锁)太慢了.在这种情况下，volatile 忙自旋会更有效率.

Sometimes, using a conditional variable (and associated lock) is too slow in practice. In this case, a volatile busy spin is much more efficient.

这里有关于这个主题的更多好建议:http://software.intel.com/en-us/articles/intel-guide-for-developing-multithreaded-applications/

More good advice on this topic here: http://software.intel.com/en-us/articles/intel-guide-for-developing-multithreaded-applications/

在另一个 SO 问题中读得很好:无锁多线程适合真正的线程专家(不要被标题吓到).

A nice read in another SO question: Lock-free multi-threading is for real threading experts (don't be scared by the title).

以及最近讨论的 atomic_decrement 的无锁 Java 实现:饥饿在非-阻塞方法

And a recently discussed lock-free Java implementation of atomic_decrement: Starvation in non-blocking approaches

¹ 这里的volatile适用于Java等语言，其中volatile在内存模型中定义了语义，但不适用于C或 C++，其中 volatile 在引入跨线程内存模型之前并且没有与之集成.类似的结构在这些语言中可用，例如各种 std::memory_order C++ 中的说明符.

¹ The use of volatile here applies to languages such as Java where volatile has defined semantics in the memory model, but not to C or C++ where volatile preceded the introduction of the cross-thread memory model and doesn't integrate with it. Similar constructs are available in those languages, such as the various std::memory_order specifiers in C++.

这篇关于无锁同步的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！