《程序员的自我修养》中关于加锁不能保证线程安全的一个错误

在《程序员的自我修养 — 链接装载与库》一书第28页“过度优化”这一节中,作者提到了编译器优化可能造成多线程bug的情况。但是《程》中所给出的例子其实是错误的。Pthreads线程库帮程序员保证了pthread mutex(spin lock也一样)所保护的临界区内共享变量的可见性:即Thread 1一执行完unlock(),x的最新值1一定能被Thread 2看见。(为了实现这一点,Pthreads线程库在实现的时候都会根据相应的硬件平台调用相应的memory barrier来保证内存可见性,感兴趣的同学可以看看nptl的实现)所以,只要正确的用锁保护好你的共享变量,你的程序就会是线程安全的。

阅读全文>>

在《程序员的自我修养 — 链接装载与库》一书第28页“过度优化”这一节中,作者提到了编译器优化可能造成多线程bug的情况(我手中的是09年6月第二次印刷那版)。原文如下:

线程安全是一个非常烫手的山芋,因为即使合理的使用了锁,也不一定能保证线程安全,这是源于落后的编译器技术已经无法满足日益增长的并发需求。很多看似无错的代码在优化和并发前又产生了麻烦。最简单的例子,让我们看看如下代码:

x = 0;
Thread 1 Thread 2
lock(); lock();
x++; x++;
unlock(); unlock();

由于有lock和unlock的保护,x++的行为不会被并发所破坏,那么x的值似乎必然是2了。然后,如果编译器为了提高x的访问速度,把x放到了某个寄存器里,那么我们知道不同线程的寄存器是各自独立的,因此如果Thread 1先获得锁,则程序的执行可能会呈现如下的执行情况:

*1 Thread 1:读取x的值到某个寄存器R[1] (R[1]=0)
*2 Thread 1:R[1]++
*3 Thread 2:读取x的值到某个寄存器R[2] (R[2]=0)
*4 Thread 2:R[2]++
*5 Thread 2:将R[2]写回至x(x=1)
*6 Thread 1:(很久以后)将R[1]写回至x(x=1)

可见在这样的情况下即使正确的加锁,也不能保证多线程安全。

这个“加锁后仍不能保证线程安全”的结论其实是错误的。在对一段代码进行加锁操作之后,被锁保护起来的代码就形成了一个临界区,在任何时刻最多只能有一个线程运行这个临界区中的代码,而其他的线程必须等待(例如pthread_mutex_lock是阻塞型等待,pthread_spin_lock是忙等待)。给临界区加锁之后相当于给临界区内的代码添加了原子性的语义。

既然加锁之后临界区内的代码是原子操作的,那么就不可能出现《程》中描述的那种执行顺序,因为Thread 2必须要等到Thread 1执行完x++和unlock()之后才能获得锁并随即进行x++操作。即如下所述的执行顺序:

*1 Thread 1:lock()
*2 Thread 1:读取x的值到某个寄存器R[1] (R[1]=0)
*3 Thread 1:R[1]++
*4 Thread 1:将R[1]写回至x(x=1)
*5 Thread 1:unlock()
*6 Thread 2:lock() //得到锁
*7 Thread 2:读取x的值到某个寄存器R[2] (R[2]=1)
*8 Thread 2:R[2]++
*9 Thread 2:将R[2]写回至x(x=2)
*10 Thread 2:unlock()

其实,这里更值得讨论的一个问题是memory visibility(内存可见性)。例如,在Thread 1将R[1]的值写回至x的这一步中,如果Thread 1只是将值放到了这个CPU核的write buffer(write buffer是多核CPU中为于优化写性能的一种硬件)里,而未将最新值直接更新至内存,那么处在另一个CPU核上的Thread 2真的有可能在第7步时读到的是x的旧值0,这下该怎么办?这个问题其实就是共享变量的值何时能被其他线程可见的问题。

好在正是因为内存可见性在共享内存的并行编程中如此的重要,所以以pthread为代表的线程库早就规定好了自己的内存模型,其中就包括了memory visibility的定义:

Memory Visibility
– When will changes of shared data be visible to other threads?
– Pthreads standard guarantees basic memory visibility rules
» thread creation
• memory state before calling pthread_create(…) is visible to created thread
» mutex unlocking (also combined with condition variables)
• memory state before unlocking a mutex is visible to thread which locks same mutex
» thread termination (i.e. entering state “terminated”)
• memory state before termination is visible to thread which joins with terminated thread
» condition variables
• memory state before notifying waiting threads is visible to woke up threads

说简单点,Pthreads线程库帮程序员保证了pthread mutex(spin lock也一样)所保护的临界区内共享变量的可见性:即Thread 1一执行完unlock(),x的最新值1一定能被Thread 2看见。(为了实现这一点,Pthreads线程库在实现的时候都会根据相应的硬件平台调用相应的memory barrier来保证内存可见性,感兴趣的同学可以看看nptl的实现)

所以,只要正确的用锁保护好你的共享变量,你的程序就会是线程安全的。《程》中所给出的上述例子其实是错误的。

PS.《程》确实是本好书,作者作为我的同龄人功力还是令人钦佩的。但是这个例子也反映了一个现实:写书最怕的就是出现重大的原则性错误,而博客作为互联网上的公开资源,能更容易的吸收大家的修改意见,保证文章的正确性。

参考文献:
[1] Programming with POSIX Threads
[2] Mutex and Memory Visibility

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

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

主要内容有:
1. C/C++中的volatile关键字
2. Visual Studio对C/C++中volatile关键字的扩展
3. Java/.NET中的volatile关键字
4. Memory Model(内存模型)
5. 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关键字

多线程队列的算法优化

多线程队列(Concurrent Queue)的使用场合非常多,高性能服务器中的消息队列,并行算法中的Work Stealing等都离不开它。对于一个队列来说有两个最主要的动作:添加(enqueue)和删除(dequeue)节点。在一个(或多个)线程在对一个队列进行enqueue操作的同时可能会有一个(或多个)线程对这个队列进行dequeue操作。因为enqueue和dequeue都是对同一个队列里的节点进行操作,为了保证线程安全,一般在实现中都会在队列的结构体中加入一个队列锁(典型的如pthread_mutex_t q_lock),在进行enqueue和dequeue时都会先锁住这个锁以锁住整个队列然后再进行相关的操作。这样的设计如果实现的好的话一般性能就会很不错了。但是它其实有一个潜在的性能瓶颈,导致在线程数增多时极大的影响多线程程序的性能。

阅读全文>>

多线程队列(Concurrent Queue)的使用场合非常多,高性能服务器中的消息队列,并行算法中的Work Stealing等都离不开它。对于一个队列来说有两个最主要的动作:添加(enqueue)和删除(dequeue)节点。在一个(或多个)线程在对一个队列进行enqueue操作的同时可能会有一个(或多个)线程对这个队列进行dequeue操作。因为enqueue和dequeue都是对同一个队列里的节点进行操作,为了保证线程安全,一般在实现中都会在队列的结构体中加入一个队列锁(典型的如pthread_mutex_t q_lock),在进行enqueue和dequeue时都会先锁住这个锁以锁住整个队列然后再进行相关的操作。这样的设计如果实现的好的话一般性能就会很不错了。以链表实现的队列的结构体一般是这样的:

struct queue_t {
    node_t *head;
    node_t *tail;
    pthread_mutex_t q_lock;
};

但是,这其中其实有一个潜在的性能瓶颈:enqueue和dequeue操作都要锁住整个队列,这在线程少的时候可能没什么问题,但是只要线程数一多,这个锁竞争所产生的性能瓶颈就会越来越严重。那么我们可不可以想办法优化一下这个算法呢?当然可以!如果我们仔细想一想enqueue和dequeue的具体操作就会发现他们的操作其实不一定是冲突的。例如:如果所有的enqueue操作都是往队列的尾部插入新节点,而所有的dequeue操作都是从队列的头部删除节点,那么enqueue和dequeue大部分时候都是相互独立的,我们大部分时候根本不需要锁住整个队列,白白损失性能!那么一个很自然就能想到的算法优化方案就呼之欲出了:我们可以把那个队列锁拆成两个:一个队列头部锁(head lock)和一个队列尾部锁(tail lock)。这样这样的设计思路是对了,但是如果再仔细思考一下它的实现的话我们会发现其实不太容易,因为有两个特殊情况非常的tricky(难搞):第一种就是往空队列里插入第一个节点的时候,第二种就是从只剩最后一个节点的队列中删除那个“最后的果实”的时候。

为什么难搞呢?当我们向空队列中插入第一个节点的时候,我们需要同时修改队列的head和tail指针,使他们同时指向这个新插入的节点,换句话说,我们此时即需要拿到head lock又需要拿到tail lock。而另一种情况是对只剩一个节点的队列进行dequeue的时候,我们也是需要同时修改head和tail指针使他们指向NULL,亦即我们需要同时获得head和tail lock。有经验的同学会立刻发现我们进入危险区了!是什么危险呢?死锁!多线程编程中最臭名昭著的一种bug就是死锁了。例如,如果线程A在锁住了资源1后还想要获取资源2,而线程B在锁住了资源2后还想要获取资源1,这时两个线程谁都不能获得自己想要的那个资源,两个线程就死锁了。所以我们要小心奕奕的设计这个算法以避免死锁,例如保证enqueue和dequeue对head lock和tail lock的请求顺序(lock ordering)是一致的等等。但是这样设计出来的算法很容易就会包含多次的加锁/解锁操作,这些都会造成不必要的开销,尤其是在线程数很多的情况下反而可能导致性能的下降。我的亲身经历就是在32线程时这个思路设计出来的算法性能反而下降了10%左右,原因就是加锁/解锁的开销增加了。

好在有聪明人早在96年就想到了一个更妙的算法。这个算法也是用了head和tail两个锁,但是它有一个关键的地方是它在队列初始化的时候head和tail指针不为空,而是指向一个空节点。在enqueue的时候只要向队列尾部添加新节点就好了。而dequeue的情况稍微复杂点,它要返回的不是头节点,而是head->next,即头节点的下一个节点。先来看伪代码:

typedef struct node_t {
    TYPE value; 
    node_t *next
} NODE;

typedef struct queue_t {
    NODE *head; 
    NODE *tail;
    LOCK q_h_lock;
    LOCK q_t_lock;
} Q;

initialize(Q *q) {
   node = new_node()   // Allocate a free node
   node->next = NULL   // Make it the only node in the linked list
   q->head = q->tail = node	// Both head and tail point to it
   q->q_h_lock = q->q_t_lock = FREE   // Locks are initially free
}

enqueue(Q *q, TYPE value) {
   node = new_node()       // Allocate a new node from the free list
   node->value = value	  // Copy enqueued value into node
   node->next = NULL       // Set next pointer of node to NULL
   lock(&q->q_t_lock)	  // Acquire t_lock in order to access Tail
      q->tail->next = node // Link node at the end of the queue
      q->tail = node       // Swing Tail to node
   unlock(&q->q_t_lock)    // Release t_lock
}

dequeue(Q *q, TYPE *pvalue) {
   lock(&q->q_h_lock)   // Acquire h_lock in order to access Head
      node = q->head    // Read Head
      new_head = node->next	     // Read next pointer
      if new_head == NULL         // Is queue empty?
         unlock(&q->q_h_lock)     // Release h_lock before return
         return FALSE             // Queue was empty
      endif
      *pvalue = new_head->value   // Queue not empty, read value
      q->head = new_head  // Swing Head to next node
   unlock(&q->q_h_lock)   // Release h_lock
   free(node)			  // Free node
   return TRUE			  // Queue was not empty, dequeue succeeded
}

发现玄机了么?是的,这个算法中队列总会包含至少一个节点。dequeue每次返回的不是头节点,而是头节点的下一个节点中的数据:如果head->next不为空的话就把这个节点的数据取出来作为返回值,同时再把head指针指向这个节点,此时旧的头节点就可以被free掉了。这个在队列初始化时插入空节点的技巧使得enqueue和dequeue彻底相互独立了。但是,还有一个小地方在实现的时候需要注意:对第一个空节点的next指针的读写。想象一下,当一个线程对一个空队列进行第一次enqueue操作时刚刚运行完第25行的代码(对该空节点的next指针进行写操作);而此时另一个线程对这个队列进行第一次dequeue操作时恰好运行到第33行(对该空节点的next指针进行读操作),它们其实还是有冲突!不过,好在一般来讲next指针是32位数据,而现代的CPU已经能保证多线程程序中内存对齐了的32位数据读写操作的原子性,而一般来讲编译器会自动帮你对齐32位数据,所以这个不是问题。唯一需要注意的是我们要确保enqueue线程是先让要添加的新节点包含好数据再把新节点插入链表(也就是不能先插入空节点,再往节点中填入数据),那么dequeue线程就不会拿到空的节点。其实我们也可以把q_t_lock理解成生产者的锁,q_h_lock理解成消费者的锁,这样生产者(们)和消费者(们)的操作就相互独立了,只有在多个生产者对同一队列进行添加操作时,以及多个消费者对同一队列进行删除操作时才需要加锁以使访问互斥。

通过使用这个算法,我成功的把一个32线程程序的性能提升了11%!可见多线程中的锁竞争对性能影响之大!此算法出自一篇著名的论文:M. Michael and M. Scott. Simple, Fast, and Practical Non-Blocking and Blocking Concurren Queue Algorithms. 如果还想做更多优化的话可以参考这篇论文实现相应的Non Blocking版本的算法,性能还能有更多提升。当然了,这个算法早已被集成到java.util.concurrent里了(即LinkedBlockingQueue),其他的并行库例如Intel的TBB多半也有类似的算法,如果大家能用上现成的库的话就不要再重复造轮子了。为什么别造并行算法的轮子呢?因为高性能的并行算法实在太难正确地实现了,尤其是Non Blocking,Lock Free之类的“火箭工程”。有多难呢?Doug Lea提到java.util.concurrent中一个Non Blocking的算法的实现大概需要1年的时间,总共约500行代码。所以,对最广大的程序员来说,别去写Non Blocking, Lock Free的代码,只管用就行了,我看见网上很多的Non Blocking阿,无锁编程的算法实现啊什么的都非常地害怕,谁敢去用他们贴出来的这些代码啊?我之所以推荐这个two lock的算法是因为它的实现相对Non Blocking之类的来说容易多了,非常具备实用价值。虽然这篇论文出现的很早,但是我在看了几个开源软件中多线程队列的实现之后发现他们很多还是用的本文最开始提到的那种一个锁的算法。如果你想要实现更高性能的多线程队列的话,试试这个算法吧!

Update: 多线程队列算法有很多种,大家应根据不同的应用场合选取最优算法(例如是CPU密集型还是IO密集型)。本文所列的算法应用在这样一个多线程程序中:每个线程都拥有一个队列,每个队列可能被本线程进行dequeue操作,也可以被其他线程进行dequeue(即work stealing),线程数不超过CPU核心数,是一个典型的CPU/MEM密集型客户端单写者多读者场景。

多线程程序中操作的原子性

原子操作就是不可再分的操作。在多线程程序中原子操作是一个非常重要的概念,它常常用来实现一些同步机制,同时也是一些常见的多线程Bug的源头。本文主要讨论了三个问题:1. 多线程程序中对变量的读写操作是否是原子的?2. 多线程程序中对Bit field(位域)的读写操作是否是线程安全的?3. 程序员该如何使用原子操作?

阅读全文>>

0. 背景

原子操作就是不可再分的操作。在多线程程序中原子操作是一个非常重要的概念,它常常用来实现一些同步机制,同时也是一些常见的多线程Bug的源头。本文主要讨论了三个问题:1. 多线程程序中对变量的读写操作是否是原子的?2. 多线程程序中对Bit field(位域)的读写操作是否是线程安全的?3. 程序员该如何使用原子操作?

1. 多线程环境下对变量的读写操作是否是原子的?

我们先从一道很热门的百度笔试题讲起。很多人讲不清楚其背后的原理,下面我们就来对它进行一下剖析(其实这个题目有点歧义,后面我们会讲到):

以下多线程对int型变量x的操作,哪几个需要进行同步:( )
A. x=y; B. x++; C. ++x; D. x=1;

要彻底理解这个问题,我们首先需要从硬件讲起。以常见的X86 CPU来说,根据Intel的参考手册,它基于以下三种机制保证了多核中加锁的原子操作(8.1节):
(1)Guaranteed atomic operations (注:8.1.1节有详细介绍)
(2)Bus locking, using the LOCK# signal and the LOCK instruction prefix
(3)Cache coherency protocols that ensure that atomic operations can be carried out on cached data structures (cache lock); this mechanism is present in the Pentium 4, Intel Xeon, and P6 family processors

这三个机制相互独立,相辅相承。简单的理解起来就是
(1)一些基本的内存读写操作是本身已经被硬件提供了原子性保证(例如读写单个字节的操作);
(2)一些需要保证原子性但是没有被第(1)条机制提供支持的操作(例如read-modify-write)可以通过使用”LOCK#”来锁定总线,从而保证操作的原子性
(3)因为很多内存数据是已经存放在L1/L2 cache中了,对这些数据的原子操作只需要与本地的cache打交道,而不需要与总线打交道,所以CPU就提供了cache coherency机制来保证其它的那些也cache了这些数据的processor能读到最新的值(关于cache coherency可以参加我的一篇博文)。

那么CPU对哪些(1)中的基本的操作提供了原子性支持呢?根据Intel手册8.1.1节的介绍:

从Intel486 processor开始,以下的基本内存操作是原子的:
• Reading or writing a byte(一个字节的读写)
• Reading or writing a word aligned on a 16-bit boundary(对齐到16位边界的字的读写)
• Reading or writing a doubleword aligned on a 32-bit boundary(对齐到32位边界的双字的读写)

从Pentium processor开始,除了之前支持的原子操作外又新增了以下原子操作:
• Reading or writing a quadword aligned on a 64-bit boundary(对齐到64位边界的四字的读写)
• 16-bit accesses to uncached memory locations that fit within a 32-bit data bus(未缓存且在32位数据总线范围之内的内存地址的访问)

从P6 family processors开始,除了之前支持的原子操作又新增了以下原子操作:
• Unaligned 16-, 32-, and 64-bit accesses to cached memory that fit within a cache line(对单个cache line中缓存地址的未对齐的16/32/64位访问)

那么哪些操作是非原子的呢?
Accesses to cacheable memory that are split across bus widths, cache lines, and
page boundaries are not guaranteed to be atomic by the Intel Core 2 Duo, Intel®
Atom™, Intel Core Duo, Pentium M, Pentium 4, Intel Xeon, P6 family, Pentium, and
Intel486 processors.(说点简单点,那些被总线带宽、cache line以及page大小给分隔开了的内存地址的访问不是原子的,你如果想保证这些操作是原子的,你就得求助于机制(2),对总线发出相应的控制信号才行)。

需要注意的是尽管从P6 family开始对一些非对齐的读写操作已经提供了原子性保障,但是非对齐访问是非常影响性能的,需要尽量避免。当然了,对于一般的程序员来说不需要太担心这个,因为大部分编译器会自动帮你完成内存对齐。

回到最开始那个笔试题。我们先反汇编一下看看它们到底执行了什么操作:

x = y;
mov eax,dword ptr [y]
mov dword ptr [x],eax

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

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

x = 1;
mov dword ptr [x],1

(1)很显然,x=1是原子操作。
因为x是int类型,32位CPU上int占32位,在X86上由硬件直接提供了原子性支持。实际上不管有多少个线程同时执行类似x=1这样的赋值语句,x的值最终还是被赋的值(而不会出现例如某个线程只更新了x的低16位然后被阻塞,另一个线程紧接着又更新了x的低24位然后又被阻塞,从而出现x的值被损坏了的情况)。

(2)再来看x++和++x。
其实类似x++, x+=2, ++x这样的操作在多线程环境下是需要同步的。因为X86会按三条指令的形式来处理这种语句:从内存中读x的值到寄存器中,对寄存器加1,再把新值写回x所处的内存地址(见上面的反汇编代码)。

例如有两个线程,它们按照如下顺序执行(注意读x和写回x是原子操作,两个线程不能同时执行):

time    Thread 1         Thread 2
0      load eax, x
1                            load eax, x
2      add eax, 1        add eax, 1
3      store x, eax
4                            store x, eax

我们会发现最终x的值会是1而不是2,因为Thread 1的结果被覆盖掉了。这种情况下我们就需要对x++这样的操作加锁(例如Pthread中的mutex)以保证同步,或者使用一些提供了atomic operations的库(例如Windows API中的atomic库,Linux内核中的atomic.h,Java concurrent库中的Atomic Integer,C++0x中即将支持的atomic_int等等,这些库会利用CPU提供的硬件机制做一层封装,提供一些保证了原子性的API)。

(3)最后来看看x=y。
在X86上它包含两个操作:读取y至寄存器,再把该值写入x。读y的值这个操作本身是原子的,把值写入x也是原子的,但是两者合起来是不是原子操作呢?我个人认为x=y不是原子操作,因为它不是不可再分的操作。但是它需要不需要同步呢?其实问题的关键在于程序的上下文。

例如有两个线程,线程1要执行{y = 1; x = y;},线程2要执行{y = 2; y = 3;},假设它们按如下时间顺序执行:

time    Thread 1        Thread 2
0        store y, 1
1                            store y, 2
2        load eax, y
3                            store y, 3
4        store x, eax

那么最终线程1中x的值为2,而不是它原本想要的1。我们需要加上相应的同步语句确保y = 2不会在线程1的两条语句之间发生。y = 3那条语句尽管在load y和store x之间执行,但是却不影响x=y这条语句本身的语义。所以你可以说x=y需要同步,也可以说x=y不需要同步,看你怎么理解题意了。x=1是否需要同步也是一样的道理,虽然它本身是原子操作,但是如果有另一个线程要读x=1之后的值,那肯定也需要同步,否则另一个线程读到的就是x的旧值而不是1了。

2. 对Bit field(位域)的读写操作是否是线程安全的?

Bit field常用来高效的存储有限位数的变量,多用于内核/底层开发中。一般来说,对同一个结构体内的不同bit成员的多线程访问是无法保证线程安全的。

例如Wikipedia中的如下例子:

struct foo {
    int flag : 1;
    int counter : 15;
};

struct foo my_foo;

/* ... */

/* in thread 1 */

pthread_mutex_lock(&my_mutex_for_flag);
my_foo.flag = !my_foo.flag;
pthread_mutex_unlock(&my_mutex_for_flag);

/* in thread 2 */

pthread_mutex_lock(&my_mutex_for_counter);
++my_foo.counter;
pthread_mutex_unlock(&my_mutex_for_counter);

两个线程分别对my_foo.flag和my_foo.counter进行读写操作,但是即使有上面的加锁方式仍然不能保证它是线程安全的。原因在于不同的成员在内存中的具体排列方式“跟Byte Order、Bit Order、对齐等问题都有关,不同的平台和编译器可能会排列得很不一样,要编写可移植的代码就不能假定Bit-field是按某一种固定方式排列的”[3]。而且一般来讲CPU对内存操作的最小单位是word(X86的word是16bits),而不是1bit。这就是说,如果my_foo.flag和my_foo.counter存储在同一个word里,CPU在读写任何一个bit member的时候会同时把两个值一起读进寄存器,从而造成读写冲突。这个例子正确的处理方式是用一个mutex同时保护my_foo.flag和my_foo.counter,这样才能确保读写是线程安全的。

C++0x草案中对bit field是这样定义的:
连续的多个非0bit的bit fields是属于同一个memory location的;长度为0bit的bit field会把占单独的一个memory location。对同一个memory location的读写不是线程安全的;对不同memory location的读写是线程安全的。
例如在下图的例子中bf1和bf2是同一个memory location,bf3是一个单独的memory location,bf4是一个单独的memory location:
bit field

这里有一个因为Bit field不是线程安全所导致的一个Linux内核中的Bug

引用一下Pongba的总结

所以,如果你的多个bitfields是连续的,同时又想要无冲突的读取它们,有两种做法,一是在中间用0大小bitfield隔开,但这种做法实际上就消除了bitfield的节省内存的初衷,因为为了使它们不冲突,至少被隔开的两个bitfield肯定不可能共享byte了。另一种做法当然就是用锁了。

3. 程序员该怎么用Atomic操作?

一般情况下程序员不需要跟CPU提供的原子操作直接打交道,所以只需要选择语言或者平台提供的atomic API即可。而且使用封装好了的API还有一个好处是它们常常还提供了诸如compare_and_swap,fetch_and_add这样既有读又有写的较复杂操作的封装。

常见的API如下:

Windows上InterlockedXXXX的API
GNU/Linux上linux kernel中atomic_32.h
GCC中的Atomic Builtins (__sync_fetch_and_add()等)
Java中的java.util.concurrent.atomic
C++0x中的atomic operation
Intel TBB中的atomic operation

4. 参考文献:

[1] 关于变量操作的原子性(atomicity)FAQ
[2] http://en.wikipedia.org/wiki/Atomic_operation
[3] 关于内存对齐、bit field等 –《Linux C编程一站式学习》
[4] Do you need mutex to protect an ‘int’?
[5] C++ Concurrency in Action
[6] Multithreaded simple data type access and atomic variables
[6] http://www.newsmth.net/bbscon.php?bid=335&id=236629
[7]
http://www.newsmth.net/bbscon.php?bid=335&id=209239
[8]
http://www.newsmth.net/bbscon.php?bid=335&id=186723
转载请注明来自parallellabs.com