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

在《程序员的自我修养 — 链接装载与库》一书第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关键字

Pthreads并行编程之spin lock与mutex性能对比分析

POSIX threads(简称Pthreads)是在多核平台上进行并行编程的一套常用的API。线程同步(Thread Synchronization)是并行编程中非常重要的通讯手段,其中最典型的应用就是用Pthreads提供的锁机制(lock)来对多个线程之间共 享的临界区(Critical Section)进行保护(另一种常用的同步机制是barrier)。

Pthreads提供了多种锁机制:
(1) Mutex(互斥量):pthread_mutex_***
(2) Spin lock(自旋锁):pthread_spin_***
(3) Condition Variable(条件变量):pthread_con_***
(4) Read/Write lock(读写锁):pthread_rwlock_***

Pthreads提供的Mutex锁操作相关的API主要有:
pthread_mutex_lock (pthread_mutex_t *mutex);
pthread_mutex_trylock (pthread_mutex_t *mutex);
pthread_mutex_unlock (pthread_mutex_t *mutex);

Pthreads提供的与Spin Lock锁操作相关的API主要有:
pthread_spin_lock (pthread_spinlock_t *lock);
pthread_spin_trylock (pthread_spinlock_t *lock);
pthread_spin_unlock (pthread_spinlock_t *lock);

从实现原理上来讲,Mutex是属于sleep-waiting类型 的锁。例如在一个双核的机器上有两个线程(线程A和线程B),它们分别运行在Core0和Core1上。当线程A想要 pthread_mutex_lock操作去得到一个临界区的锁时,如果这个锁正被线程B所持有,那么线程A就会被阻塞(bolcking),Core0 会在此时进行上下文切换(Context Switch),这样Core0就可以运行其他的任务(例如另一个线程C)而不必进行忙等待。而Spin lock则不然,它是属于busy-waiting类型的锁,如果线程A是使用pthread_spin_lock操作去请求锁,那么线程A就会一直在 Core0上进行忙等待并不停的进行锁请求,直到得到这个锁为止。

阅读全文>>

POSIX threads(简称Pthreads)是在多核平台上进行并行编程的一套常用的API。线程同步(Thread Synchronization)是并行编程中非常重要的通讯手段,其中最典型的应用就是用Pthreads提供的锁机制(lock)来对多个线程之间共 享的临界区(Critical Section)进行保护(另一种常用的同步机制是barrier)。

Pthreads提供了多种锁机制:
(1) Mutex(互斥量):pthread_mutex_***
(2) Spin lock(自旋锁):pthread_spin_***
(3) Condition Variable(条件变量):pthread_con_***
(4) Read/Write lock(读写锁):pthread_rwlock_***

Pthreads提供的Mutex锁操作相关的API主要有:
pthread_mutex_lock (pthread_mutex_t *mutex);
pthread_mutex_trylock (pthread_mutex_t *mutex);
pthread_mutex_unlock (pthread_mutex_t *mutex);

Pthreads提供的与Spin Lock锁操作相关的API主要有:
pthread_spin_lock (pthread_spinlock_t *lock);
pthread_spin_trylock (pthread_spinlock_t *lock);
pthread_spin_unlock (pthread_spinlock_t *lock);

从实现原理上来讲,Mutex属于sleep-waiting类型的锁。例如在一个双核的机器上有两个线程(线程A和线程B),它们分别运行在Core0和Core1上。假设线程A想要通过pthread_mutex_lock操作去得到一个临界区的锁,而此时这个锁正被线程B所持有,那么线程A就会被阻塞(blocking),Core0 会在此时进行上下文切换(Context Switch)将线程A置于等待队列中,此时Core0就可以运行其他的任务(例如另一个线程C)而不必进行忙等待。而Spin lock则不然,它属于busy-waiting类型的锁,如果线程A是使用pthread_spin_lock操作去请求锁,那么线程A就会一直在 Core0上进行忙等待并不停的进行锁请求,直到得到这个锁为止。

如果大家去查阅Linux glibc中对pthreads API的实现NPTL(Native POSIX Thread Library) 的源码的话(使用”getconf GNU_LIBPTHREAD_VERSION”命令可以得到我们系统中NPTL的版本号),就会发现pthread_mutex_lock()操作如果没有锁成功的话就会调用system_wait()的系统调用(现在NPTL的实现采用了用户空间的futex,不需要频繁进行系统调用,性能已经大有改善),并将当前线程加入该mutex的等待队列里。而spin lock则可以理解为在一个while(1)循环中用内嵌的汇编代码实现的锁操作(印象中看过一篇论文介绍说在linux内核中spin lock操作只需要两条CPU指令,解锁操作只用一条指令就可以完成)。有兴趣的朋友可以参考另一个名为sanos的微内核中pthreds API的实现:mutex.c spinlock.c,尽管与NPTL中的代码实现不尽相同,但是因为它的实现非常简单易懂,对我们理解spin lock和mutex的特性还是很有帮助的。

那么在实际编程中mutex和spin lcok哪个的性能更好呢?我们知道spin lock在Linux内核中有非常广泛的利用,那么这是不是说明spin lock的性能更好呢?下面让我们来用实际的代码测试一下(请确保你的系统中已经安装了最近的g++)。

// Name: spinlockvsmutex1.cc
// Source: http://www.alexonlinux.com/pthread-mutex-vs-pthread-spinlock
// Compiler(spin lock version): g++ -o spin_version -DUSE_SPINLOCK spinlockvsmutex1.cc -lpthread
// Compiler(mutex version): g++ -o mutex_version spinlockvsmutex1.cc -lpthread
#include <stdio.h>
#include <unistd.h>
#include <sys/syscall.h>
#include <errno.h>
#include <sys/time.h>
#include <list>
#include <pthread.h>

#define LOOPS 50000000

using namespace std;

list<int> the_list;

#ifdef USE_SPINLOCK
pthread_spinlock_t spinlock;
#else
pthread_mutex_t mutex;
#endif

//Get the thread id
pid_t gettid() { return syscall( __NR_gettid ); }

void *consumer(void *ptr)
{
    int i;

    printf("Consumer TID %lun", (unsigned long)gettid());

    while (1)
    {
#ifdef USE_SPINLOCK
        pthread_spin_lock(&spinlock);
#else
        pthread_mutex_lock(&mutex);
#endif

        if (the_list.empty())
        {
#ifdef USE_SPINLOCK
            pthread_spin_unlock(&spinlock);
#else
            pthread_mutex_unlock(&mutex);
#endif
            break;
        }

        i = the_list.front();
        the_list.pop_front();

#ifdef USE_SPINLOCK
        pthread_spin_unlock(&spinlock);
#else
        pthread_mutex_unlock(&mutex);
#endif
    }

    return NULL;
}

int main()
{
    int i;
    pthread_t thr1, thr2;
    struct timeval tv1, tv2;

#ifdef USE_SPINLOCK
    pthread_spin_init(&spinlock, 0);
#else
    pthread_mutex_init(&mutex, NULL);
#endif

    // Creating the list content...
    for (i = 0; i < LOOPS; i++)
        the_list.push_back(i);

    // Measuring time before starting the threads...
    gettimeofday(&tv1, NULL);

    pthread_create(&thr1, NULL, consumer, NULL);
    pthread_create(&thr2, NULL, consumer, NULL);

    pthread_join(thr1, NULL);
    pthread_join(thr2, NULL);

    // Measuring time after threads finished...
    gettimeofday(&tv2, NULL);

    if (tv1.tv_usec > tv2.tv_usec)
    {
        tv2.tv_sec--;
        tv2.tv_usec += 1000000;
    }

    printf("Result - %ld.%ldn", tv2.tv_sec - tv1.tv_sec,
        tv2.tv_usec - tv1.tv_usec);

#ifdef USE_SPINLOCK
    pthread_spin_destroy(&spinlock);
#else
    pthread_mutex_destroy(&mutex);
#endif

    return 0;
}

该程序运行过程如下:主线程先初始化一个list结构,并根据LOOPS的值将对应数量的entry插入该list,之后创建两个新线程,它们都执行consumer()这个任务。两个被创建的新线程同时对这个list进行pop操作。主线程会计算从创建两个新线程到两个新线程结束之间所用的时间,输出为下文中的”Result “。

测试机器参数:
Ubuntu 9.04 X86_64
Intel(R) Core(TM)2 Duo CPU E8400 @ 3.00GHz
4.0 GB Memory

从下面是测试结果:

gchen@gchen-desktop:~/Workspace/mutex$ g++ -o spin_version -DUSE_SPINLOCK spinvsmutex1.cc -lpthread
gchen@gchen-desktop:~/Workspace/mutex$ g++ -o mutex_version spinvsmutex1.cc -lpthread
gchen@gchen-desktop:~/Workspace/mutex$ time ./spin_version
Consumer TID 5520
Consumer TID 5521
Result - 5.888750

real    0m10.918s
user    0m15.601s
sys    0m0.804s

gchen@gchen-desktop:~/Workspace/mutex$ time ./mutex_version
Consumer TID 5691
Consumer TID 5692
Result - 9.116376

real    0m14.031s
user    0m12.245s
sys    0m4.368s

可以看见spin lock的版本在该程序中表现出来的性能更好。另外值得注意的是sys时间,mutex版本花费了更多的系统调用时间,这就是因为mutex会在锁冲突时调用system wait造成的。

但是,是不是说spin lock就一定更好了呢?让我们再来看一个锁冲突程度非常剧烈的实例程序:

//Name: svm2.c
//Source: http://www.solarisinternals.com/wiki/index.php/DTrace_Topics_Locks
//Compile(spin lock version): gcc -o spin -DUSE_SPINLOCK svm2.c -lpthread
//Compile(mutex version): gcc -o mutex svm2.c -lpthread
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <sys/syscall.h>

#define        THREAD_NUM     2

pthread_t g_thread[THREAD_NUM];
#ifdef USE_SPINLOCK
pthread_spinlock_t g_spin;
#else
pthread_mutex_t g_mutex;
#endif
__uint64_t g_count;

pid_t gettid()
{
    return syscall(SYS_gettid);
}

void *run_amuck(void *arg)
{
       int i, j;

       printf("Thread %lu started.n", (unsigned long)gettid());

       for (i = 0; i < 10000; i++) {
#ifdef USE_SPINLOCK
           pthread_spin_lock(&g_spin);
#else
               pthread_mutex_lock(&g_mutex);
#endif
               for (j = 0; j < 100000; j++) {
                       if (g_count++ == 123456789)
                               printf("Thread %lu wins!n", (unsigned long)gettid());
               }
#ifdef USE_SPINLOCK
           pthread_spin_unlock(&g_spin);
#else
               pthread_mutex_unlock(&g_mutex);
#endif
       }
       
       printf("Thread %lu finished!n", (unsigned long)gettid());

       return (NULL);
}

int main(int argc, char *argv[])
{
       int i, threads = THREAD_NUM;

       printf("Creating %d threads...n", threads);
#ifdef USE_SPINLOCK
       pthread_spin_init(&g_spin, 0);
#else
       pthread_mutex_init(&g_mutex, NULL);
#endif
       for (i = 0; i < threads; i++)
               pthread_create(&g_thread[i], NULL, run_amuck, (void *) i);

       for (i = 0; i < threads; i++)
               pthread_join(g_thread[i], NULL);

       printf("Done.n");

       return (0);
}

这个程序的特征就是临界区非常大,这样两个线程的锁竞争会非常的剧烈。当然这个是一个极端情况,实际应用程序中临界区不会如此大,锁竞争也不会如此激烈。测试结果显示mutex版本性能更好:

gchen@gchen-desktop:~/Workspace/mutex$ time ./spin
Creating 2 threads...
Thread 31796 started.
Thread 31797 started.
Thread 31797 wins!
Thread 31797 finished!
Thread 31796 finished!
Done.

real    0m5.748s
user    0m10.257s
sys    0m0.004s

gchen@gchen-desktop:~/Workspace/mutex$ time ./mutex
Creating 2 threads...
Thread 31801 started.
Thread 31802 started.
Thread 31802 wins!
Thread 31802 finished!
Thread 31801 finished!
Done.

real    0m4.823s
user    0m4.772s
sys    0m0.032s

另外一个值得注意的细节是spin lock耗费了更多的user time。这就是因为两个线程分别运行在两个核上,大部分时间只有一个线程能拿到锁,所以另一个线程就一直在它运行的core上进行忙等待,CPU占用率一直是100%;而mutex则不同,当对锁的请求失败后上下文切换就会发生,这样就能空出一个核来进行别的运算任务了。(其实这种上下文切换对已经拿着锁的那个线程性能也是有影响的,因为当该线程释放该锁时它需要通知操作系统去唤醒那些被阻塞的线程,这也是额外的开销)

总结
(1)Mutex适合对锁操作非常频繁的场景,并且具有更好的适应性。尽管相比spin lock它会花费更多的开销(主要是上下文切换),但是它能适合实际开发中复杂的应用场景,在保证一定性能的前提下提供更大的灵活度。

(2)spin lock的lock/unlock性能更好(花费更少的cpu指令),但是它只适应用于临界区运行时间很短的场景。而在实际软件开发中,除非程序员对自己的程序的锁操作行为非常的了解,否则使用spin lock不是一个好主意(通常一个多线程程序中对锁的操作有数以万次,如果失败的锁操作(contended lock requests)过多的话就会浪费很多的时间进行空等待)。

(3)更保险的方法或许是先(保守的)使用 Mutex,然后如果对性能还有进一步的需求,可以尝试使用spin lock进行调优。毕竟我们的程序不像Linux kernel那样对性能需求那么高(Linux Kernel最常用的锁操作是spin lock和rw lock)。

2010年3月3日补记:这个观点在Oracle的文档中得到了支持:

During configuration, Berkeley DB selects a mutex implementation for the architecture. Berkeley DB normally prefers blocking-mutex implementations over non-blocking ones. For example, Berkeley DB will select POSIX pthread mutex interfaces rather than assembly-code test-and-set spin mutexes because pthread mutexes are usually more efficient and less likely to waste CPU cycles spinning without getting any work accomplished.

p.s.调用syscall(SYS_gettid)和syscall( __NR_gettid )都可以得到当前线程的id:)

转载请注明来自: www.parallellabs.com