标签： 多线程Bug

剖析为什么在多核多线程程序中要慎用volatile关键字？

这篇文章详细剖析了为什么在多核时代进行多线程编程时需要慎用volatile关键字。

主要内容有：
1. C/C++中的volatile关键字
2. Visual Studio对C/C++中volatile关键字的扩展
3. Java/.NET中的volatile关键字
4. Memory Model（内存模型）
5. Volatile使用建议

1. C/C++中的volatile关键字

1.1 传统用途

C/C++作为系统级语言，它们与硬件的联系是很紧密的。volatile的意思是“易变的”，这个关键字最早就是为了针对那些“异常”的内存操作而准备的。它的效果是让编译器不要对这个变量的读写操作做任何优化，每次读的时候都直接去该变量的内存地址中去读，每次写的时候都直接写到该变量的内存地址中去，即不做任何缓存优化。它经常用在需要处理中断的嵌入式系统中，其典型的应用有下面几种：

a. 避免用通用寄存器对内存读写的优化。编译器常做的一种优化就是：把常用变量的频繁读写弄到通用寄存器中，最后不用的时候再存回内存中。但是如果某个内存地址中的值是由片外决定的（例如另一个线程或是另一个设备可能更改它），那就需要volatile关键字了。（感谢Kenny老师指正）
b. 硬件寄存器可能被其他设备改变的情况。例如一个嵌入式板子上的某个寄存器直接与一个测试仪器连在一起，这样在这个寄存器的值随时可能被那个测试仪器更改。在这种情况下如果把该值设为volatile属性的，那么编译器就会每次都直接从内存中去取这个值的最新值，而不是自作聪明的把这个值保留在缓存中而导致读不到最新的那个被其他设备写入的新值。
c. 同一个物理内存地址M有两个不同的内存地址的情况。例如两个程序同时对同一个物理地址进行读写，那么编译器就不能假设这个地址只会有一个程序访问而做缓存优化，所以程序员在这种情况下也需要把它定义为volatile的。

1.2 多线程程序中的错误用法

看到这里，很多朋友自然会想到：恩，那么如果是两个线程需要同时访问一个共享变量，为了让其中两个线程每次都能读到这个变量的最新值，我们就把它定义为volatile的就好了嘛！我想这个就是多线程程序中volatile之所以引起那么多争议的最大原因。可惜的是，这个想法是错误的。

举例来说，想用volatile变量来做同步（例如一个flag）？错！为什么？很简单，虽然volatile意味着每次读和写都是直接去内存地址中去操作，但是volatile在C/C++现有标准中即不能保证原子性（Atomicity）也不能保证顺序性（Ordering），所以几乎所有试图用volatile来进行多线程同步的方案都是错的。我之前一篇文章介绍了Sequential Consistency模型（后面简称SC），它其实就是我们印象中多线程程序应该有的执行顺序。但是，SC最大的问题是性能太低了，因为CPU/编译器完全没有必要严格按代码规定的顺序（program order）来执行每一条指令。学过体系结构的同学应该知道不管是编译器也好CPU也好，他们最擅长做的事情就是帮你做乱序优化。在串行时代这些乱序优化对程序员来说都是透明的，封装好了的，你不用关心它们到底给你乱序成啥样了，因为它们会保证优化后的程序的运行结果跟你写程序时预期的结果是一模一样的。但是进入多核时代之后，CPU和编译器还会继续做那些串行时代的优化，更重要的是这些优化还会打破你多线程程序的SC模型语义，从而使得多线程程序的实际运行结果与我们所期待的运行结果不一致！

拿X86来说，它的多核内存模型没有严格执行SC，即属于weak ordering（或者叫relax ordering？）。它唯一允许的乱序优化是可以把对不同地址的load操作提到store之前去（即把store x->load y乱序优化成load y -> store x）。而store x -> store y、load x -> load y，以及load y -> store x不允许交换执行顺序。在X86这样的内存模型下，volatile关键字根本就不能保证对不同volatile变量x和y的store x -> load y的操作不会被CPU乱序优化成load y -> store x。

而对多线程读写操作的原子性来说，诸如volatile x=1这样的写操作的原子性其实是由X86硬件保证的，跟volatile没有任何关系。事实上，volatile根本不能保证对没有内存对齐的变量（或者超出机器字长的变量）的读写操作的原子性。

为了有个更直观的理解，我们来看看CPU的乱序优化是如何让volatile在多线程程序中显得如此无力的。下面这个著名的Dekker算法是想用flag1/2和turn来实现两个线程情况下的临界区互斥访问。这个算法关键就在于对flag1/2和turn的读操作（load）是在其写操作（store）之后的，因此这个多线程算法能保证dekker1和dekker2中对gSharedCounter++的操作是互斥的，即等于是把gSharedCounter++放到临界区里去了。但是，多核X86可能会对这个store->load操作做乱序优化，例如dekker1中对flag2的读操作可能会被提到对flag1和turn的写操作之前，这样就会最终导致临界区的互斥访问失效，而gSharedCounter++也会因此产生data race从而出现错误的计算结果。那么为什么多核CPU会对多线程程序做这样的乱序优化呢？因为从单线程的视角来看flag2和flag1、turn是没有依赖关系的，所以CPU当然可以对他们进行乱序优化以便充分利用好CPU里面的流水线（想了解更多细节请参考计算机体系结构相关书籍）。这样的优化虽然从单线程角度来讲没有错，但是它却违反了我们设计这个多线程算法时所期望的那个多线程语义。（想要解决这个bug就需要自己手动添加memory barrier，或者干脆别去实现这样的算法，而是使用类似pthread_mutex_lock这样的库函数，后面我会再讲到这点）

当然，对不同的CPU来说他们的内存模型是不同的。比如说，如果这个程序是在单核上以多线程的方式执行那么它肯定不会出错，因为单核CPU的内存模型是符合SC的。而在例如PowerPC，ARM之类的架构上运行结果到底如何就得去翻它们的硬件手册中内存模型是怎么定义的了。

/*
 * Dekker's algorithm, implemented on pthreads
 *
 * To use as a test to see if/when we can make
 * memory consistency play games with us in 
 * practice. 
 *
 * Compile: gcc -O2 -o dekker dekker.c -lpthread
 * Source: http://jakob.engbloms.se/archives/65
 */ 

#include <assert.h>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

#undef PRINT_PROGRESS 

static volatile int flag1 = 0;
static volatile int flag2 = 0;
static volatile int turn  = 1;
static volatile int gSharedCounter = 0;
int gLoopCount;
int gOnePercent;

void dekker1( ) {
        flag1 = 1;
        turn  = 2;
        while((flag2 ==  1) && (turn == 2)) ;
        // Critical section
        gSharedCounter++;
        // Let the other task run
        flag1 = 0;
}

void dekker2(void) {
        flag2 = 1;
        turn = 1;
        while((flag1 ==  1) && (turn == 1)) ;
        // critical section
        gSharedCounter++;        
        // leave critical section
        flag2 = 0;
}

//
// Tasks, as a level of indirection
//
void *task1(void *arg) {
        int i,j;
        printf("Starting task1\n");
        // Do the dekker very many times
#ifdef PRINT_PROGRESS
	for(i=0;i<100;i++) {
	  printf("[One] at %d%%\n",i);
	  for(j=gOnePercent;j>0;j--) {
	    dekker1();
	  }
	}
#else
	// Simple basic loop
        for(i=gLoopCount;i>0;i--) {
                dekker1();
        }
#endif

}

void *task2(void *arg) {
        int i,j;
        printf("Starting task2\n");
#ifdef PRINT_PROGRESS
	for(i=0;i<100;i++) {
	  printf("[Two] at %d%%\n",i);
	  for(j=gOnePercent;j>0;j--) {
	    dekker2();
	  }
	}
#else
        for(i=gLoopCount;i>0;i--) {
                dekker2();
        }
#endif
}

int
main(int argc, char ** argv)
{
        int            loopCount = 0;
        pthread_t      dekker_thread_1;
        pthread_t      dekker_thread_2;
        void           * returnCode;
        int            result;
        int            expected_sum;

        /* Check arguments to program*/
        if(argc != 2) 
        {
                fprintf(stderr, "USAGE: %s <loopcount>\n", argv[0]);
                exit(1);
        }

        /* Parse argument */
        loopCount   = atoi(argv[1]);	/* Don't bother with format checking */
        gLoopCount  = loopCount;
	gOnePercent = loopCount/100;
        expected_sum = 2*loopCount;
        
        /* Start the threads */
        result = pthread_create(&dekker_thread_1, NULL, task1, NULL);
        result = pthread_create(&dekker_thread_2, NULL, task2, NULL);

        /* Wait for the threads to end */
        result = pthread_join(dekker_thread_1,&returnCode);
        result = pthread_join(dekker_thread_2,&returnCode);
        printf("Both threads terminated\n");

        /* Check result */
        if( gSharedCounter != expected_sum ) {
                printf("[-] Dekker did not work, sum %d rather than %d.\n", gSharedCounter, expected_sum);
                printf("    %d missed updates due to memory consistency races.\n", (expected_sum-gSharedCounter));
                return 1;
        } else {
                printf("[+] Dekker worked.\n");
                return 0;
        }
}

2. Visual Studio对C/C++中volatile关键字的扩展

虽然C/C++中的volatile关键字没有对ordering做任何保证，但是微软从Visual Studio 2005开始就对volatile关键字添加了同步语义（保证ordering），即：对volatile变量的读操作具有acquire语义，对volatile变量的写操作具有release语义。Acquire和Release语义是来自data-race-free模型的概念。为了理解这个acquire语义和release语义有什么作用，我们来看看MSDN中的一个例子。

// volatile.cpp
// compile with: /EHsc /O2
// Output: Critical Data = 1 Success
#include <iostream>
#include <windows.h>
using namespace std;

volatile bool Sentinel = true;
int CriticalData = 0;

unsigned ThreadFunc1( void* pArguments ) {
   while (Sentinel)
      Sleep(0);   // volatile spin lock

   // CriticalData load guaranteed after every load of Sentinel
   cout << "Critical Data = " << CriticalData << endl;
   return 0;
} 

unsigned  ThreadFunc2( void* pArguments ) {
   Sleep(2000);
   CriticalData++;   // guaranteed to occur before write to Sentinel
   Sentinel = false; // exit critical section
   return 0;
}

int main() {
   HANDLE hThread1, hThread2; 
   DWORD retCode;

   hThread1 = CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)&ThreadFunc1,
      NULL, 0, NULL);
   hThread2 = CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)&ThreadFunc2,
      NULL, 0, NULL);

   if (hThread1 == NULL || hThread2 == NULL)       {
      cout << "CreateThread failed." << endl; 
      return 1;
   }

   retCode = WaitForSingleObject(hThread1,3000);

   CloseHandle(hThread1);
   CloseHandle(hThread2);

   if (retCode == WAIT_OBJECT_0 && CriticalData == 1 )
      cout << "Success" << endl;
   else
      cout << "Failure" << endl;
}

例子中的 while (Sentinel) Sleep(0); // volatile spin lock 是对volatile变量的读操作，它具有acquire语义，acquire语义的隐义是当前线程在对sentinel的这个读操作之后的所有的对全局变量的访问都必须在该操作之后执行；同理，例子中的Sentinel = false; // exit critical section 是对volatile变量的写操作，它具有release语义，release语义的隐义是当前线程在对sentinel这个写操作之前的所有对全局变量的访问都必须在该操作之前执行完毕。所以ThreadFunc1（）读CriticalData时必定已经在ThreadFunc2（）执行完CriticalData++之后，即CriticalData最后输出的值必定为1。建议大家用纸画一下acquire/release来加深理解。一个比较形象的解释就是把acquire当成lock，把release当成unlock，它俩组成了一个临界区，所有临界区外面的操作都只能往这个里面移，但是临界区里面的操作都不能往外移，简单吧？

其实这个程序就相当于用volatile变量的acquire和release语义实现了一个临界区，在临界区内部的代码就是 Sleep(2000); CriticalData++; 或者更贴切点也可以看成是一对pthread_cond_wait和pthread_cond_signal。

这个volatile的acquire和release语义是VS自己的扩展，C/C++标准里是没有的，所以同样的代码用gcc编译执行结果就可能是错的，因为编译器/CPU可能做违反正确性的乱序优化。Acquire和release语义本质上就是为了保证程序执行时memory order的正确性。但是，虽然这个VS扩展使得volatile变量能保证ordering，它还是不能保证对volatile变量读写的原子性。事实上，如果我们的程序是跑在X86上面的话，内存对齐了的变量的读写的原子性是由硬件保证的，跟volatile没有任何关系。而像volatile g_nCnt++这样的语句本身就不是原子操作，想要保证这个操作是原子的，就必须使用带LOCK语义的++操作，具体请看我这篇文章。

另外，VS生成的volatile变量的汇编代码是否真的调用了memory barrier也得看具体的硬件平台，例如x86上就不需要使用memory barrier也能保证acquire和release语义，因为X86硬件本身就有比较强的memory模型了，但是Itanium上面VS就会生成带memory barrier的汇编代码。具体可以参考这篇。

但是，虽然VS对volatile关键字加入了acquire/release语义，有一种情况还是会出错，即我们之前看到的dekker算法的例子。这个其实蛮好理解的，因为读操作的acquire语义不允许在其之后的操作往前移，但是允许在其之前的操作往后移；同理，写操作的release语义允许在其之后的操作往前移，但是不允许在其之前的操作往后移；这样的话对一个volatile变量的读操作（acquire）当然可以放到对另一个volatile变量的写操作（release）之前了！Bug就是这样产生的！下面这个程序大家拿Visual Studio跑一下就会发现bug了（我试了VS2008和VS2010，都有这个bug）。多线程编程复杂吧？希望大家还没被弄晕，要是晕了的话也很正常，仔仔细细重新再看一遍吧:)

想解决这个Bug也很简单，直接在dekker1和dekker2中对flag1/flag2/turn赋值操作之后都分别加入full memory barrier就可以了，即保证load一定是在store之后执行即可。具体的我就不详述了。

#include <iostream>
#include <windows.h>
using namespace std;

static volatile int flag1 = 0;
static volatile int flag2 = 0;
static volatile int turn = 1; // must have "turn", otherwise the two threads might introduce deadlock at line 13&23 of "while..."
static int gCount = 0;

void dekker1() {
	flag1 = 1;
	turn = 2;
	while ((flag2 == 1) && (turn == 2));
	// critical section
	gCount++;
	flag1 = 0; 	// leave critical section
}

void dekker2() {
	flag2 = 1;
	turn = 1;
	while ((flag1 == 1) && (turn == 1));
	// critical setion
	gCount++;
	flag2 = 0; 	// leave critical section
}

unsigned ThreadFunc1( void* pArguments ) {
	int i;
	//cout << "Starting Thread 1" << endl;
	for (i=0;i<1000000;i++) {
		dekker1();
	}
	return 0;
} 

unsigned  ThreadFunc2( void* pArguments ) {
	int i;
	//cout << "Starting Thread 2" << endl;
	for (i=0;i<1000000;i++) {
		dekker2();
	}
	return 0;
}

int main() {
	HANDLE hThread1, hThread2;
	//DWORD retCode;

	hThread1 = CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)&ThreadFunc1,
		NULL, 0, NULL);
	hThread2 = CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)&ThreadFunc2,
		NULL, 0, NULL);

	if (hThread1 == NULL || hThread2 == NULL) {
		cout << "CreateThread failed." << endl;
		return 1;
	}

	WaitForSingleObject(hThread1,INFINITE);
	WaitForSingleObject(hThread2,INFINITE);
	cout << gCount << endl;

	if (gCount == 2000000)
		cout << "Success" << endl;
	else
		cout << "Fail" << endl;
}

3. Java/.NET中的volatile关键字

3.1 多线程语义

Java和.NET分别有JVM和CLR这样的虚拟机，保证多线程的语义就容易多了。说简单点，Java和.NET中的volatile关键字也是限制虚拟机做优化，都具有acquire和release语义，而且由虚拟机直接保证了对volatile变量读写操作的原子性。 （volatile只保证可见性，不保证原子性。java中，对volatile修饰的long和double的读写就不是原子的 (http://java.sun.com/docs/books/jvms/second_edition/html /Threads.doc.html#22244)，除此之外的基本类型和引用类型都是原子的。– 多谢liuchangit指正） 这里需要注意的一点是，Java和.NET里面的volatile没有对应于我们最开始提到的C/C++中对“异常操作”用volatile修饰的传统用法。原因很简单，Java和.NET的虚拟机对安全性的要求比C/C++高多了，它们才不允许不安全的“异常”访问存在呢。

而且像JVM/.NET这样的程序可移植性都非常好。虽然现在C++1x正在把多线程模型添加到标准中去，但是因为C++本身的性质导致它的硬件平台依赖性很高，可移植性不是特别好，所以在移植C/C++多线程程序时理解硬件平台的内存模型是非常重要的一件事情，它直接决定你这个程序是否会正确执行。

至于Java和.NET中是否也存在类似VS 2005那样的bug我没时间去测试，道理其实是相同的，真有需要的同学自己应该能测出来。好像这篇InfoQ的文章中显示Java运行这个dekker算法没有问题，因为JVM给它添加了mfence。另一个臭名昭著的例子就应该是Double-Checked Locking了。

3.2 volatile int与AtomicInteger区别

Java和.NET中这两者还是有些区别的，主要就是后者提供了类似incrementAndGet()这样的方法可以直接调用（保证了原子性），而如果是volatile x进行++操作则不是原子的。increaseAndGet()的实现调用了类似CAS这样的原子指令，所以能保证原子性，同时又不会像使用synchronized关键字一样损失很多性能，用来做全局计数器非常合适。

4. Memory Model（内存模型）

说了这么多，还是顺带介绍一下Memory Model吧。就像前面说的，CPU硬件有它自己的内存模型，不同的编程语言也有它自己的内存模型。如果用一句话来介绍什么是内存模型，我会说它就是程序员，编程语言和硬件之间的一个契约，它保证了共享的内存地址里的值在需要的时候是可见的。下次我会专门详细写一篇关于它的内容。它最大的作用是取得可编程性与性能优化之间的一个平衡。

5. volatile使用建议

总的来说，volatile关键字有两种用途：一个是ISO C/C++中用来处理“异常”内存行为（此用途只保证不让编译器做任何优化，对多核CPU是否会进行乱序优化没有任何约束力），另一种是在Java/.NET（包括Visual Studio添加的扩展）中用来实现高性能并行算法（此种用途通过使用memory barrier保证了CPU/编译器的ordering，以及通过JVM或者CLR保证了对该volatile变量读写操作的原子性）。

一句话，volatile对多线程编程是非常危险的，使用的时候千万要小心你的代码在多核上到底是不是按你所想的方式执行的，特别是对现在暂时还没有引入内存模型的C/C++程序更是如此。安全起见，大家还是用Pthreads，Java.util.concurrent，TBB等并行库提供的lock/spinlock，conditional variable, barrier, Atomic Variable之类的同步方法来干活的好，因为它们的内部实现都调用了相应的memory barrier来保证memory ordering，你只要保证你的多线程程序没有data race，那么它们就能帮你保证你的程序是正确的（是的，Pthreads库也是有它自己的内存模型的，只不过它的内存模型还些缺点，所以把多线程内存模型直接集成到C/C++中是更好的办法，也是将来的趋势，但是C++1x中将不会像Java/.NET一样给volatile关键字添加acquire和release语义，而是转而提供另一种具有同步语义的atomic variables，此为后话）。如果你想实现更高性能的lock free算法，或是使用volatile来进行同步，那么你就需要先把CPU和编程语言的memory model搞清楚，然后再时刻注意Atomicity和Ordering是否被保证了。（注意，用没有acquire/release语义的volatile变量来进行同步是错误的，但是你仍然可以在C/C++中用volatile来修饰一个不是用来做同步（例如一个event flag）而只是被不同线程读写的共享变量，只不过它的新值什么时候能被另一个线程读到是没有保证的，需要你自己做相应的处理）

Herb Sutter 在他的那篇volatile vs. volatile中对这两种用法做了很仔细的区分，我把其中两张表格链接贴过来供大家参考：

volatile的两种用途
volatile两种用途的异同

最后附上《Java Concurrency in Practice》3.1.4节中对Java语言的volatile关键字的使用建议（不要被英语吓到，这些内容确实对你有用，而且还能顺便帮练练英语，哈哈）：

So from a memory visibility perspective, writing a volatile variable is like exiting a synchronized block and reading a volatile variable is like entering a synchronized block. However, we do not recommend relying too heavily on volatile variables for visibility; code that relies on volatile variables for visibility of arbitrary state is more fragile and harder to understand than code that uses locking.

Use volatile variables only when they simplify implementing and verifying your synchronization policy; avoid using volatile variables when veryfing correctness would require subtle reasoning about visibility. Good uses of volatile variables include ensuring the visibility of their own state, that of the object they refer to, or indicating that an important lifecycle event (such as initialization or shutdown) has occurred.

Locking can guarantee both visibility and atomicity; volatile variables can only guarantee visibility.

You can use volatile variables only when all the following criteria are met:
(1) Writes to the variable do not depend on its current value, or you can ensure that only a single thread ever updates the value;
(2) The variable does not participate in invariants with other state variables; and
(3) Locking is not required for any other reason while the variable is being accessed.

参考资料

1. 《Java Concurrency in Practice》3.1.4节
2. volatile vs. volatile（Herb Sutter对volatile的阐述，必看）
3. The “Double-Checked Locking is Broken” Declaration
4. Threading in C#
5. Volatile: Almost Useless for Multi-Threaded Programming
6. Memory Ordering in Modern Microprocessors
7. Memory Ordering @ Wikipedia
8. 内存屏障什么的
9. The memory model of x86
10. VC 下 volatile 变量能否建立 Memory Barrier 或并发锁
11. Sayonara volatile（Concurrent Programming on Windows作者的文章 跟我观点几乎一致）
12. Java 理论与实践: 正确使用 Volatile 变量
13. Java中的Volatile关键字

多线程程序常见Bug剖析（下）

上一篇文章我们专门针对违反原子性（Atomicity Violation）的多线程程序Bug做了剖析，现在我们再来看看另一种常见的多线程程序Bug：违反执行顺序（Ordering Violation）。

简单来说，多线程程序各个线程之间交错执行的顺序的不确定性（Non-deterministic）是造成违反执行顺序Bug的根源[注1]。正是因为这个原因，程序员在编写多线程程序时就不能假设程序会按照你设想的某个顺序去执行，而是应该充分考虑到各种可能的顺序组合，从而采取正确的同步措施。

1. 违反执行顺序（Ordering Violation）

举例来说，下面这个来自Mozilla的多线程Bug产生的原因就是程序员错误地假设S1一定会在S2之前执行完毕，即在S2访问mThread之前S1一定已经完成了对mThread的初始化（因为线程2是由线程1创建的）。事实上线程2完全有可能执行的很快，而且S1这个初始化操作又不是原子的（因为需要几个时钟周期才能结束），从而在线程1完成初始化（即S1）之前就已经运行到S2从而导致Bug。

例1：
    Thread 1                                 Thread 2
void init(...)                           void mMain(...)
{ ...                                    { ...
 S1: mThread=                              ...
      PR_CreateThread(mMain, ...);         S2: mState = mThread->State;
  ...                                      ...
}                                        }

上面这个例子是一个线程读一个线程写的情况，除此之外还有违反写-写顺序以及违反一组读写顺序的情况。例如下面这个程序，程序员错误的以为S2（写操作）一定会在S4（也是写操作）之前执行。但是实际上这个程序完全有可能先执行S4后执行S2，从而导致线程1一直hang在S3处：

例2：
    Thread 1                                 Thread 2
int ReadWriteProc(...)                   void DoneWaiting(...)
{                                        {
  ...                                     /*callback func of PBReadAsync*/
 S1: PBReadAsync(&p);
 S2: io_pending = TRUE;                   ...
  ...                                     S4: io_pending = FALSE;
 S3: while (io_pending) {...}             ...
  ...                                    }
}

下面这个是违反一组读写操作顺序的例子：程序员假设S2一定会在S1之前执行，但是事实上可能S1在S2之前执行，从而导致程序crash。

例3：
    Thread 1                                 Thread 2
void js_DestroyContext(...){             void js_DestroyContext(...){
  /* last one entering this func */      /* non-last one entering this func */
  S1: js_UnpinPinnedAtom(&atoms);          S2: js_MarkAtom(&atoms,...);
}                                        }

调试违反执行顺序这种类型的Bug最困难的地方就在只有某几种执行顺序才会引发Bug，这大大降低了Bug重现的几率。最简单的调试手段自然是使用printf了，但是类似printf这样的函数会干扰程序的执行顺序，所以有可能违反执行顺序的Bug更难产生了。我所知道的目前最领先的商业多线程Debugger是Corensic的Jinx，他们的技术核心是用Hypervisor来控制线程的执行顺序以找出可能产生Bug的那些特定的执行顺序（学生、开源项目可以申请免费使用，Windows/Linux版均有）。八卦一下，这个公司是从U of Washington发展出来的，他们现在做的Deterministic Parallelism是最热门的方向之一。

2. Ordering Violation的解决方案

常见的解决方案主要有四种：
（1）加锁进行同步
加锁的目的就在于保证被锁住的操作的原子性，从而这些被锁住的操作就不会被别的线程的操作打断，在一定程度上保证了所需要的执行顺序。例如上面第二个例子可以给{S1,S2}一起加上锁，这样就不会出现S4打断S1,S2的情况了（即S1->S4->S2），因为S4是由S1引发的异步调用，S4肯定会在{S1,S2}这个原子操作执行完之后才能被运行。

（2）进行条件检查
进行条件检查是另一种常见的解决方案，关键就在于通过额外的条件语句来迫使该程序会按照你所想的方式执行。例如下面这个例子就会对n的值进行检查：

例4：
retry:
  n = block->n;
  ...
  ...
  if (n!=block->n)
  {
    goto retry;
  }
  ...

（3）调整代码执行顺序
这个也是很可行的方案，例如上面的例2不需要给{S1,S2}加锁，而是直接调换S2与S1的顺序，这样S2就一定会在S4之前执行了！

（4）重新设计算法/数据结构
还有一些执行顺序的问题可以通过重新设计算法/数据结构来解决。这个就得具体情况具体分析了。例如MySQL的bug #7209中，一个共享变量HASH::current_record的访问有顺序上的冲突，但是实际上这个变量不需要共享，所以最后的解决办法就是线程私有化这个变量。

3. 总结

多线程Bug确实是个非常让人头痛的问题。写多线程程序不难，难的在于写正确的多线程程序。多线程的debug现在仍然可以作为CS Top10学校的博士论文题目。在看过这两篇分析多线程常见Bug的文章之后，不知道各位同学有没有什么关于多线程Bug的经历与大家分享呢？欢迎大家留言:)

需要注意的是，违反执行顺序和违反原子性这两种Bug虽然是相互独立的，但是两者又有着潜在的联系。例如，上一篇文章中我所讲到的第一个违反原子性的例子其实是因为执行顺序的不确定性造成的，而本文的第二个例子就可以通过把{S1,S2}加锁保证原子性来保证想要的执行顺序。

参考

[1] Learning from Mistakes – A Comprehensive Study on Real World Concurrency Bug Characteristics
[2] Understanding, Detecting and Exposing Concurrency Bugs
[3] Practical Parallel and Concurrent Programming
[4] Java concurrency bug patterns for multicore systems

注1：严格来讲，多线程交错执行顺序的不确定性只是违反执行顺序Bug的原因之一。另一个可能造成违反执行顺序Bug的原因是编译器/CPU对代码做出的违反多线程程序语义的乱序优化，这种“错误的优化”直接引出了编程语言的内存模型（memory model）这个关键概念。后面我会专门分析下C++与Java的内存模型，敬请期待。

多线程程序常见Bug剖析（上）

编写多线程程序的第一准则是先保证正确性，再考虑优化性能。本文重点分析多线程编程中除死锁之外的另两种常见Bug：违反原子性（Atomicity Violation）和违反执行顺序（Ordering Violation）。现在已经有很多检测多线程Bug的工具，但是这两种Bug还没有工具能完美地帮你检测出来，所以到目前为止最好的办法还是程序员自己有意识的避免这两种Bug。本文的目的就是帮助程序员了解这两种Bug的常见形式和常见解决办法。

1. 多线程程序执行模型

在剖析Bug之前，我们先来简单回顾一下多线程程序是怎么执行的。从程序员的角度来看，一个多线程程序的执行可以看成是每个子线程的指令交错在一起共同执行的，即Sequential Consistency模型。它有两个属性：每个线程内部的指令是按照代码指定的顺序执行的（Program Order），但是线程之间的交错顺序是任意的、不确定的（Non deterministic）。

我原来举过一个形象的例子。伸出你的双手，掌心面向你，两个手分别代表两个线程，从食指到小拇指的四根手指头分别代表每个线程要依次执行的四条指令。
（1）对每个手来说，它的四条指令的执行顺序必须是从食指执行到小拇指
（2）你两个手的八条指令（八个手指头）可以在满足（1）的条件下任意交错执行（例如可以是左1，左2，右1，右2，右3，左3，左4，右4，也可以是左1，左2，左3，左4，右1，右2，右3，右4，也可以是右1，右2，右3，左1，左2，右4，左3，左4等等等等）

好了，现在让我们来看看程序员在写多线程程序时是怎么犯错的。

2. 违反原子性（Atomicity Violation）

何谓原子性？简单的说就是不可被其他线程分割的操作。大部分程序员在编写多线程程序员时仍然是按照串行思维来思考，他们习惯性的认为一些简单的代码肯定是原子的。

例如：

	Thread 1						Thread 2
S1: if (thd->proc_info)				...
{							S3: thd->proc_info=NULL;
  S2: fputs(thd->proc_info,...)
}

这个来自MySQL的Bug的根源就在于程序员误认为，线程1在执行S1时如果从thd->proc_info读到的是一个非空的值的话，在执行S2时thd->proc_info的值肯定也还是非空的，所以可以调用fputs()进行操作。事实上，{S1,S2}组合到一起之后并不是原子操作，所以它们可能被线程2的S3打断，即按S1->S3->S2的顺序执行，从而导致线程1运行到S2时出错（注意，虽然这个Bug是因为多线程程序执行顺序的不确定性造成的，可是它违反的是程序员对这段代码是原子的期望，所以这个Bug不属于违反顺序性的Bug）。

这个例子的对象是两条语句，所以很容易看出来它们的组合不是原子的。事实上，有些看起来像是原子操作的代码其实也不是原子的。最著名的莫过于多个线程执行类似“x++”这样的操作了。这条语句本身不是原子的，因为它在大部分硬件平台上其实是由三条语句实现的：

mov eax,dword ptr [x]
add eax,1
mov dword ptr [x],eax

同样，下面这个“r.Location = p”也不是原子的，因为事实上它是两个操作：“r.Location.X = p.X”和“r.Location.Y = p.Y”组成的。

struct RoomPoint {
   public int X;
   public int Y;
}

RoomPoint p = new RoomPoint(2,3);
r.Location = p;

从根源上来讲，如果你想让这段代码真正按照你的心意来执行，你就得在脑子里仔细考虑是否会出现违反你本意的执行顺序，特别是涉及的变量（例如thd->proc_info）在其他线程中有可能被修改的情况，也就是数据竞争（Data Race）[注1]。如果有两个线程同时对同一个内存地址进行操作，而且它们之中至少有一个是写操作，数据竞争就发生了。

有时候数据竞争可是隐藏的很深的，例如下面的Parallel.For看似很正常：

Parallel.For(0, 10000, 
    i => {a[i] = new Foo();})

实际上，如果我们去看看Foo的实现：

class Foo {
	private static int counter;
	private int unique_id;
	public Foo()
       {
		unique_id = counter++;
       }
}

同志们，看出来哪里有数据竞争了么？是的，counter是静态变量，Foo()这个构造函数里面的counter++产生数据竞争了！想避免Atomicity Violation，其实根本上就是要保证没有数据竞争（Data Race Free）。

3. Atomicity Violation的解决方案

解决方案大致有三（可结合使用）：
（1）把变量隔离起来：只有一个线程可以访问它（isolation）
（2）把变量的属性定义为immutable的：这样它就是只读的了（immutability）
（3）同步对这个变量的读写：比如用锁把它锁起来（synchronization）

例如下面这个例子里面x是immutable的；而a[]则通过index i隔离起来了，即不同线程处理a[]中不同的元素；

Parallel.For(1,1000, 
i => {
    a[i] = x;
});

例如下面这个例子在构造函数中给x和y赋值（此时别的线程不能访问它们），保证了isolation；一旦构造完毕x和y就是只读的了，保证了immutability。

public class Coordinate
{
   private double x, y;

   public Coordinate(double a,
                     double b)
   {
      x = a;
      y = b;
   }
   public void GetX() {
      return x; 
   }
   public void GetY() {
      return y; 
   }
}

而我最开始提到的关于thd->proc_info的Bug可以通过把S1和S2两条语句用锁包起来解决（同志们，千万别忘了给S3加同一把锁，要不然还是有Bug！）。被锁保护起来的临界区在别的线程看来就是“原子”的，不可以被打断的。

	Thread 1						Thread 2
LOCK(&lock)
S1: if (thd->proc_info)				LOCK(&lock);
{							S3: thd->proc_info=NULL;
  S2: fputs(thd->proc_info,...)		UNLOCK(&lock);
}
UNLOCK(&lock)

还有另一个用锁来同步的例子，即通过使用锁（Java中的synchronized关键字）来保证没有数据竞争：

“Java 5 中提供了 ConcurrentLinkedQueue 来简化并发操作。但是有一个问题：使用了这个类之后是否意味着我们不需要自己进行任何同步或加锁操作了呢？
也就是说，如果直接使用它提供的函数，比如：queue.add(obj); 或者 queue.poll(obj);，这样我们自己不需要做任何同步。”但是，两个原子操作合起来可就不一定是原子操作了（Atomic + Atomic != Atomic），例如：

if(!queue.isEmpty()) {  
   queue.poll(obj);  
}

事实情况就是在调用isEmpty()之后，poll()之前，这个queue没有被其他线程修改是不确定的，所以对于这种情况，我们还是需要自己同步，用加锁的方式来保证原子性（虽然这样很损害性能）：

synchronized(queue) {  
    if(!queue.isEmpty()) {  
       queue.poll(obj);  
    }  
}

但是注意了，使用锁也会造成一堆Bug，死锁就先不说了，先看看初学者容易犯的一个错误（是的，我曾经也犯过这个错误），x在两个不同的临界区中被修改，加了锁跟没加一样，因为还是有数据竞争：

int x = 0;
pthread_mutex_t lock1;
pthread_mutex_t lock2;

pthread_mutex_lock(&lock1);
x++;
pthread_mutex_unlock(&lock1);
...
...
pthread_mutex_lock(&lock2);
x++;
pthread_mutex_unlock(&lock2);

事实上，类似x++这样的操作最好的解决办法就是使用类似java.util.concurrent.atomic，Intel TBB中的atomic operation之类的方法完成，具体的例子可以参考这篇文章。

总结一下，不管是多条语句之间的原子性也好，单个语句（例如x++）的原子性也好都需要大家格外小心，有这种意识之后很多跟Atomicity Violation相关的Bug就可以被避免了。其实归根结底，我们最终是想让多线程程序按照你的意愿正确的执行，所以在清楚什么样的情形可能让你的多线程程序不能按你所想的那样执行之后我们就能有意识的避免它们了（或者更加容易的修复它们）。下一篇文章我们再来仔细分析下Ordering Violation。

[注1] 严格意义上来讲，Data Race只是Atomicity Violation的一个特例，Data Race Free不能保证一定不会出现Atomicity Violation。例如文中Java实现的那个Concurrent Queue的例子，严格意义上来讲它并没有data race，因为isEmpty()和poll()都是线程安全的调用，只不过它们组合起来之后会出现违反程序员本意的Atomicity Violation，所以要用锁保护起来。

P.S. 参考文献中的前两篇是YuanYuan Zhou教授的得意门生Dr. Shan Lu的论文，后者现在已经是Wisconsin–Madison的教授了。