Lock free synchronization (无锁同步)

14 浏览
0 Comments

Lock free synchronization (无锁同步)

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

  1. 实现这一目标的一般方法有哪些?我在某个地方读到过LockFreePrimitives(如CompareAndExchange(CAS)或DoubleCompareAndExchange(DCA)),但没有给出对它们的解释。有没有任何方法可以最小化对锁的使用?
  2. Java/.NET如何实现并发容器?它们使用锁还是无锁同步?

提前感谢。

0
0 Comments

锁无法同步问题的出现是因为在多线程环境下,使用锁会带来性能的开销和复杂性。为了解决这个问题,可以采用以下方法:

1. 当只更新一个数字变量时,可以使用非阻塞的原子操作,比如CAS(比较并交换)、atomic_increment等,它们通常比经典的阻塞临界区(锁、互斥锁)快得多。

2. 当数据结构被多个线程读取,但只由一个或少数线程写入时,可以使用读写锁来替代完全锁。

3. 尝试利用细粒度锁。例如,不要使用单个锁来保护整个数据结构,而是使用多个不同的锁来保护数据结构的不同部分。

4. 如果依赖锁的隐式内存屏障效果来确保跨线程的单个变量的可见性,可以使用volatile(如果支持的话)。

5. 有时,在实践中,使用条件变量(和相关的锁)太慢。在这种情况下,使用volatile的自旋锁更高效。

以上这些方法可以最小化对锁的使用,提高并发性能。更多关于这个话题的建议可以参考链接:[http://software.intel.com/en-us/articles/intel-guide-for-developing-multithreaded-applications/](http://software.intel.com/en-us/articles/intel-guide-for-developing-multithreaded-applications/)。另外,可以阅读Stack Overflow上关于无锁多线程编程的问题:[Lock-free multi-threading is for real threading experts](https://stackoverflow.com/questions/2528969),以及关于无锁Java实现的讨论:[Starvation in non-blocking approaches](https://stackoverflow.com/questions/9044023)。

需要注意的是,关于volatile的使用在Java等语言中有定义明确的语义,但在C或C++等语言中,volatile的语义不同,不能用于解决多线程同步问题。在C++中可以使用std::atomic来替代volatile。

0
0 Comments

锁无关的同步是一种有用的方式,可以通过比较和交换来维护整数,也可以通过无锁算法来维护队列。但是需要提醒的是,锁无关的同步无法组合使用。例如,如果尝试使用计数器来计算队列中的元素数量,将会得到错误的答案。在某些情况下,元素已经被添加,但是计数器还没有反映出来(或者反之),如果依赖于计数器可能会导致错误(例如,尝试向一个满队列添加元素)。

简而言之,可以使每个元素保持一致,但无法使它们相互保持一致。

解决这个问题的方法是使用一些其他的同步机制,例如互斥锁或读写锁,来确保操作的原子性。这样可以避免在计数器和队列之间出现不一致的情况。

以下是一个示例代码,展示了如何使用互斥锁来保证计数器和队列之间的一致性:

#include 
#include 
#include 
std::mutex mtx;
int counter = 0;
void addToQueue() {
    // 假设这里是添加元素到队列的操作
    std::lock_guard lock(mtx);
    counter++;
}
void removeFromQueue() {
    // 假设这里是从队列中移除元素的操作
    std::lock_guard lock(mtx);
    counter--;
}
int main() {
    std::thread t1(addToQueue);
    std::thread t2(removeFromQueue);
    
    t1.join();
    t2.join();
    
    std::cout << "Counter: " << counter << std::endl;
    
    return 0;
}

在上面的代码中,使用了互斥锁`std::mutex`来保护计数器的操作,确保每次对计数器的修改都是原子的。这样就可以避免计数器和队列之间的不一致情况。

,锁无关的同步在某些情况下是有用的,但需要注意无法组合使用的问题。为了解决这个问题,可以使用其他的同步机制来保证操作的原子性,例如互斥锁。

0
0 Comments

无锁同步是一种简单的技术,适用于某些生产者/消费者的使用情况。下面是一个使用无锁同步的示例:

1. 线程A初始化一个volatile布尔变量flag,并创建一个volatile缓冲区对象,doWork函数将向其输出。

2. 线程A创建线程B,并调用doWork函数。

3. 线程B的doWork函数开始创建/写入缓冲区。完成后,它将布尔变量设置为true。

4. 线程A可以轮询一个全局布尔标志,初始值为false。当它变为true时,线程A可以访问缓冲区对象,并确保写入操作已完成。在轮询之间,线程A可以执行其他工作。

这种方法之所以有效,是因为线程A只读取数据,线程B只写入数据。这种使用场景在后台工作线程中非常常见。这种方法只能在Java或C#中使用,因为volatile关键字在这两种语言中有相应的保证。

然而,简单的布尔值不能用于这种同步。编译器和/或处理器可能会重新排序读取操作,导致错误。为了解决这个问题,需要使用信号量。

你可能认为线程A会首先读取缓冲区再使用它,因为它是在依赖于布尔变量读取的条件下进行的。编译器不会更改这些操作的顺序。这就是为什么可以编写一个条件语句来检查空指针,然后在之后使用指针。

然而,在多线程编程中,这是一个大错误。编译器可能会根据不同的地址进行重新排序,导致令人惊讶的错误。因此,编译器的重新排序遵循一定的规则,而这种技术也符合这些规则。

你忽略了乱序执行。假设编译器按照你的预期进行了所有操作,产生了类似于mov var1,%eax; test %eax,%eax; jz somewhere; mov var2,%eax的机器代码。读取var2是在读取并验证var1为非零之后进行的。但是CPU仍然可以重新排序,先读取var2,再读取var1(可能是因为var2在更近的缓存中)。如果var1最终为0,则var2的值将被丢弃。但如果var1最终为非零,则将使用旧值。

我现在明白你的观点了,并感谢你很好地说明了这一点。但是,在某些语言(如Java > 1.5和C#)中,由于volatile关键字的存在,实际上可以保证不进行这种重新排序。在C中,你需要一些内存屏障。

在C11中,可以使用_Atomic int。在C++11中,可以使用atomic。这将为加载/存储操作提供与Java / C#中的volatile相同的功能,并支持原子RMW操作。

0