多线程上的无锁编程与memory barrier

多线程下的无锁编程与memory barrier

今天看twitter的EarlyBird论文，提到了用volatile关键字，还有single-writer+multi-reader实现了无锁的更新查询机制，其中提到了JVM的内存模型和Memory Barrier概念。想到去年做Ksearch的时候，也用c++的volatile关键字做了无锁的更新查询，但c++的volatile语义很明显比java的volatile弱，不包含memory barrier概念，理论上说我当时的做法是有问题的。最近花了不少时间，把相关的概念整理了一下，有些理解可能还不是很透彻，需要以后实践中加深学习。

为了搞清楚无锁编程（lock-free），涉及到的主要概念：编译器优化（比如代码调整，register优化），volatile关键字，memory-barrier（mfence），CPU cache。

先说编译器优化，比如register优化，如果register有空闲，一些函数内部的局部变量，不用在内存中分配，而直接使用register；代码调整，比如for-loop的展开等；这些都是在编译阶段做的。volatile关键字的语义是告诉编译器，这个变量不能优化到register，每次读写直接走内存；volatile经常会用在device驱动中，因为线程之间不知道什么时候会修改，所以编译器不能做register优化。还有一个volatile的用法例子，经常用到，如下所示。

volatile bool globalstop = false;

main_thread_signal_handler {
    globalstop = true
}

work_thread_model {
    while(!globalstop) {
         do_something();
    }
}

说到memory-barrier，得先介绍下CPU-cache和store-buffer，其中storebuffer位于cpu和cpu-cache之间。做内存写操作时，如果发生cache-miss，这个写操作会放到storebuffer中，然后直接执行下一条指令，这里就会产生问题，比如：

a=b=0;

thread1{
    a=1
    b=1
}

thread2{
    while(b==0)continue;
    assert(a==1)
}

这段代码，逻辑上是没问题的；但是如果a=1时对a的访问出现cache-miss，a的赋值放到storebuffer中，而b=1是ok的，可能导致b比a先赋值，这时在thread2中就会出现问题。这种memory reference reorder的做法是动态的，与编译器的代码优化一定要分开。为了让上面的代码执行正确，可以在a=1的赋值后，加一个memory barrier指令，确保storebuffer中的操作都完成。

一个操作一旦到cpu-cache或者内存层面，就可以认为是对全部线程可见的。在cpu和cpu-cache之间加了层storebuffer，是为了让速度更快，但带来的坏处就是软件执行的逻辑顺序被破坏了，software还需要考虑硬件层面的东西。linux的锁系统函数，比如thread_mutex, spin_lock等，除了提供critical section的语义，还包含了memory-barrier语义，lock和unlock时做memory barrier动作，这个经常会被大家忽略。

多线程上的无锁编程与memory barrier

这个例子是一个多更新多查询的例子，而且更新查询之间无锁，很能说明问题，摘自：Memory Barriers: a Hardware View for Software Hackers。

总结：

对我自己来说，原来做多线程编程，如果涉及到共享数据，我一般使用mutex等原语来实现；而且以为mutex只提供了共享数据的互斥访问，对于其额外提供的memory barrier完全不知道。当去年做ksearch时，我就实现了一个lock-free的查询更新结构，以为是正确的，其实完全没考虑memory-barrier，有一定出错几率，现在每天支撑几亿的请求量，真是奇迹啊。

顺便说下，java中的volatile关键字包含了memory barrier概念，与c/c++中的不一样，所以earlybird可以这么用。

参考资料：

http://www.domaigne.com/blog/computing/mutex-and-memory-visibility/

http://www.oaklib.org/docs/oak/singleton.html

http://www.parallellabs.com/2010/12/04/why-should-we-be-care-of-volatile-keyword-in-multithreaded-applications/

http://software.intel.com/en-us/blogs/2007/11/30/volatile-almost-useless-for-multi-threaded-programming/

Memory Barriers: a Hardware View for Software Hackers

In what situations might I need to insert memory barrier instructions

How do I Understand Read Memory Barriers and Volatile

多线程上的无锁编程与memory barrier

总结：

相关推荐