Background

先来看一段程序。

线程1
ready = false;
init(p);
ready = true;

线程2
if (ready) {
  p.bar();
}

线程2当ready为true时才会访问p，而在线程1里如果ready为true的话表示p已经初始化好了，看起来肯定没问题的，可是对于cpu来说这段代码几乎是不能正确执行的，这里的关键在于内存可见性(visibility)和指令重排(reordering)。在SMP架构下，每一个核都有自己的cache(一般是L1和L2)，当不同的核修改同一段内存时，cpu会同步不同核的cache，但同步是有延时的，即在一个时间内，这个内存变更对其他核来说是不可见的；而指令重排是说cpu工程师为了追求更高的性能，把不相关的指令尽可能并发执行，比如当cpu需要从内存里copy数据过来，这个时间相对是比较久的，cpu不会等copy完成后才去执行下一条无相关指令。针对这段代码，read=true这条指令可能重排到init完成之前，线程2在看到ready=true后对p访问导致出错，假如即使并没有重排，当线程2看到ready变为true之后，也很有可能因为visibility没有看到p的变化，继而导致访问出错。

Pthreads

实现POSIX 线程标准的库常被称作Pthreads，为了解决各线程同时访问一段内存，库提供了原子访问和内存可见性保证，这里只说一个可见性原则：线程A修改变量后调用pthread_unlock mutex，线程B成功pthread_lock mutex后对之前的变量修改是立即可见的。

但mutex往往也会造成性能过低，当临界区过大会限制线程的并发，而临界区过小会造成上下文的频繁切换(此时应考虑adaptive mutex)。随着硬件的发展，并行编程越来越重要。

Atomic Instructions

原子指令是并行编程的基石，c++11正式引入了原子指令。

原子指令不是mutex，为了解决重排问题，stl封装了memory order。

更重要的是，原子指令赋予了我们无锁数据结构(Non-Blocking Data Structures)：lock-free和wait-free。

Non-Blocking Data Structures

boost1.53版本提供了几个lock-free数据结构

boost::lockfree::queue

boost::lockfree::stack

boost::lockfree::spsc_queue

详见这篇翻译。

值得说的是，使用lock-free或wait-free相比mutex过于复杂，有时效果反而会慢，因为

• lock-free和wait-free需要处理复杂的race condition和ABA problem，完成相同目的的代码比用mutex更复杂。
• 出现竞争时mutex会使调用者睡眠，在高度竞争时避免了频繁的cache bouncing，使拿到锁的那个线程可以很快地完成一系列流程，总体吞吐可能反而高了。

Final

多线程程序设计似乎没有一个统一的答案，pthreads，原子指令，无锁结构，但有一个可以值得肯定的就是你的设计：如何规避竞争。也可能是最重要的法则。比方说，一个依赖全局多生产者多消费者队列(MPMC)的程序不可能有很好的多核适应性，因为这个队列的极限吞吐取决于CPU的同步cache延时，lock-free或wait-free也解决不了。更好的解决方法是规避全局竞争，比如用多个SPMC或多个MPSC队列，甚至多个SPSC队列代替，在源头就规避掉竞争。