移动设备进入多核时代!

Nvidia最近发布了代号为Tegra 2的新一代双核移动处理器,移动设备即将进入多核时代。该款处理器由两个基于ARM Cortex A9的核心及其它视频音频图形专用核心(可看成Accelerator)组成,是一个典型的异构(Heterogeneous)平台。这个平台的关键特征有两个:低功耗(比高频单核的处理器耗电小),高性能(异构平台的性能优势)。

我之前也讲过为什么我们要迁移到多核平台,简单来说,继续提升核心频率及电压的办法会让处理器的功耗呈指数级增加,此时的功耗会难以让人接受;而在晶体管数目持续增加的前提下,工业界自然就(被迫)选择了更加容易实现的多核方案来继续提升硬件的性能。这个趋势也即将体现在移动处理器上。

Nvidia的白皮书《The Benefits of Multiple CPU Cores in Mobile Devices》中提到了几个多核对移动应用带来的好处:

1. 更快的网页加载速度

现在的网页内容越来越丰富,也越来越复杂。HTML5,Flash,Javascript,视频等内容的呈现都需要强大的处理能力。Nvidia提供的测试数据表明Tegra 2的Javascript性能提升了1.5~2倍,网页平均加载速度提升了46%。事实上Firefox,Chrome等桌面浏览器都已经采用了多线程,而Android浏览器,Safari等采用的Webkit内核也已经实现了多线程。在浏览器已经并行化的前提下,多核移动处理器自然能提供更快更丰富的网页渲染体验。

2. 更低的功耗及更高的性能瓦特比

对多核来讲,任务调度及电源管理算法是提升性能瓦特比的关键。Tegra 2能通过如下几点降低功耗:
1)把任务平均分配到两个核心上,这样每个核心都不必跑在最高频率/电压上,而只需要以较低的频率/电压就能完成任务,从而节省功耗
2)如果要执行的任务是高度并行化的,Tegra 2就能更快的完成这个任务,从而更快的进入超低功耗待机模式,节省更多电量
3)如果任务只需要一个核心的话,其他计算单元可以被关闭从而节省电量

续航能力一直是手机、Tablet等移动设备的关键问题之一,在电池技术没有突破性进展的今天,我们只能寄希望于硬件/软件上的优化手段来降低功耗了。

3. 提升游戏体验

Tegra 2的图形处理单元叫做Ultra Low Power (ULP) GeForce GPU,性能应该很不错。现在的一些主流游戏引擎早已经完成了并行化(多线程分别用来完成渲染,音频,网络,解码,碰撞检测,透明等任务)。白皮书中提供的测试数据表明虚幻3引擎在Tegra 2双核心上快了将近70%。一个值得注意的地方时很多游戏引擎是通过task parallelism的方式以适应不同的处理器核心数目,这说明基于这些引擎的游戏可以在几乎不修改程序的情况下在以后的4核乃至8核移动平台上取得更好的游戏体验。游戏在最受欢迎的移动应用中还是占了大头的,所以多核对移动游戏应用的影响会非常大。

下面是一些主流游戏引擎使用的线程数:
Game/Engine(Number of Threads)
Unreal Engine 3(4+)
Id Tech 5(6+)
Frostbite(14)
Civilization 5(12)
Mafia 2(4)
Crysis(8)
Uncharted 2(8)
Killzone 2(8+)

4. 更平滑的用户体验及更快的多任务处理能力

多任务处理在手机/Tablet上都非常常见。当你一边听着歌,一边下载电影,一边上网冲浪时,多核处理器就能帮你把这些任务分配到不同的核心上进行处理,从而给你提供更好的更平滑的用户体验。我记得iPad上的一些电子杂志的界面响应速度是个很大的问题,因为渲染速度太慢了,性能更高的多核平台就能提供更快的处理速度,提升用户体验,当然,这个前提是该程序能充分利用好多核。

想到这我还要插一句题外话。iOS一开始不支持对第三方程序的多任务处理功能其实主要是因为iPhone/iPad上内存有限(256MB)且没有硬盘(即没有swap),具体可参考Robert Love(该大牛现在在做Android)这篇《Why the iPad and iPhone don’t Support Multitasking》;至于Android怎么解决多任务处理的可以参考这篇《Multitasking Android Way》(想看这两篇都要会功夫,你懂的)

移动设备的多核时代已经到来,移动开发者们,你们准备好了么?

剖析为什么在多核多线程程序中要慎用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关键字

Jeff Dean关于Google系统架构的讲座

上个月Jeff Dean在Standford的Computer Systems Colloquium (EE380)这门讨论课上详细讲了讲Google的系统架构发展过程,因为这是份很新的资料,所以特意把它的Slide下下来与大家分享一下。这门课是Standford的讲座课程,每一节课都由不同的顶级工程师/科学家/投资人前来讲授IT行业的最新动向,非常非常有料,绝对值得深挖。这门课的每节课都是带视频的,Jeff Dean的这个讲座的录像在这里。想要下载该视频的同学可以去这里(要会功夫,你懂的)。

这个讲座的主要内容包括:
• Evolution of various systems at Google
– computing hardware
– core search systems
– infrastructure software

• Techniques for building large-scale systems
– decomposition into services
– design patterns for performance & reliability

个人的一点小感想:Jeff Dean在Google的这几年能面临这么多有意思的挑战,编程模型,可靠性,伸缩性,运行时环境等等等等,真是羡煞旁人。随着Google业务的扩展,整个系统的设计也面临各种各样新的挑战。只有有了扎实的基本功,在面对没有现成解决方案的新问题时才能游刃有余,做工程是如此,做研究更是如此。

可能有些同学会因为这是个英语的讲座而头疼。我觉得大家可以坚持看,哪个单词看不懂的就查字典,刚开始可能痛苦点,但是只要坚持下去,积少成多,你就会发现自己的英语慢慢就上来了,至少看这些英文slides是没问题了。

Building Software Systems at Google and Lessons Learned

另外还有几个关于Jeff Dean的Google架构的博文:
Jeff Dean 在WSDM 2009上面的演讲 Keynote 和视频终于出来了
来自Jeff Dean的分布式系统设计模式(更新版)
Jeff Dean的Stanford演讲

我还发现了Jeff另外一个在09年做的类似主题的讲座,内容稍有重复,但是可以算是一个补充,例如这个里面包括了BigTable等内容。

Enjoy!

Erlang User Conference 2010见闻(兼谈程序员职业生涯)

1. Erlang User Confernece 2010

这是我第一次参加关于Erlang的技术大会,总来的说收获非常大,不管是技术上的还是非技术上的都是如此。首先不得不说的是会议举行的地点。我从别人那得知之前的会议一直都是在Ericsson的总部大楼举行的,但是因为参会人数越来越多,好像是从去年开始就转移到市中心一个很有历史的电影院ASTORIA举行了。由于这个举办地是电影院的缘故,从去年开始EUC就开始有电影海报了!去年海报是由哈利波特改的,今年的是星球大战。去年那张如下,有意思吧?

Erlang-the-Movie

海报上面的四个人是Erlang最早的设计者们:Joe Armstrong, Mike Williams, Robert Virding还有当时的团队经理Bjarne Däcker。有了海报没有电影怎么能行?点这里观看Erlang – The Movie

因为我赶早乘火车去的斯德,所以我到的时候已经快9点了,大会即将开始。在去之前我就很期待能见到Joe Armstrong本人,结果意外的是在签到处我就见到Joe本人了!不知道为什么,他出现在我面前时的形象与我之前想象的一模一样,后来我想明白了,根本原因在于他穿的就是他那件非常眼熟的紫黑线衫!哈哈!Joe爷爷人非常开朗,时不时从他坐的地方传出爽朗的笑声,此为后话。因为会议即将开始所以我就赶紧进去找座位坐下,正好赶上Bjarne Däcker在致开幕辞,这是每年的传统了。仔细看了下我的签到卡,这已经是第16届Erlang大会了!

Klarna无疑是这届大会最吸引眼球的公司。开幕第一个Talk就是关于他们怎么使用Erlang相关的工具来解决他们的CodeManagement,Translation,Testing等问题的。Klarna有两个中国程序员,我见到其中之一的Wang Jia。Klarna是由三位瑞典银行家在05年创立的公司,提供第三方电子支付解决方案。他们最早的开发者就是从当时提供Erlang咨询的公司(其实也是Ericsson前员工)跳出来的。传闻说当时创始人提出业务需求后,他们说这个太简单了,用Erlang几天就开发出来了,虽然最后花了大概一个礼拜,但是可见Erlang开发效率之高。现在他们应该是Erlang程序员最多的公司,而且随着业务的增长他们的开发团队也在快速扩张。一年前他们只有20个左右,现在已经解决60人了,听说还要继续招人。Good for them! 我还见到另一个在Mobile Art做Erlang开发的中国人张浩,他已经用Erlang做开发3年多了。我们聊了很多关于职业发展的问题,非常有收获。

此次大会的slides和talk都可以在这里下载

2. 关于职业生涯

除技术之外我最大的感触就是看见一群爷爷级的人物仍然热衷于参加这样的技术盛会,让我很有编程编到老的冲动。Joe Armstrong老爷子是1950年生的,早年在英国念物理PhD,后来自己钱花光了,就跑去了爱丁堡做人工智能了。他的导师Donald Michie在二战时跟图灵一起工作过,所以收藏有图灵所有的论文。Joe就在满是图灵的论文的办公室里工作了整整一年多,难怪如此之牛。做研究讲究家谱,大师之所以成为大师还是需要一些机缘在里面的(当然,独力开创一片新天地的神牛除外)。关于Joe的更多趣闻可以看《Coders at Works》,中文版应该快出版了,但是如果有条件的话还是推荐大家读英文版,边学大师的经验边学英语,一举两得,岂不快哉?如果大家好奇Joe是怎么修炼到大师级的,他自己一句话很有代表性:“So I would characterize that period, which took 20 years, as learning how to program”。这句话的上下文我就不详述了,简单地说你可以理解成他花了20年学会了如何编程(注意,这个“如何编程”可不是指精通C++之类的)。这说明要想成为大师,没有十几二十年的功力肯定是不行的。十年学会编程不是空谈,而是实实在在的。说到程序员的基本功,我必须要站出来批评一下《Coders at Works》此书在豆瓣的一个不负责任的书评,这位同学说“去他的算法内功基础,对于程序员实用主义才是王道”,这完全是误人子弟,而且可悲的是这个观点竟然有很多人支持。表面上这句话好像抓住了“实用主义”的大旗,但是这位同学却借此抨击算法基本功的重要性,实在是荒谬。(Update:该同学已经把标题改掉了)就拿Google Fellow Jeff Dean来说,他绝对算得上是实用主义的大师了吧?可是如果你去看看他关于Google整个系统架构演变过程的讲座,你就会发现把Google的那些诸如MapReduce、GFS之类的看家法宝化繁为简之后都可以还原成最基本的算法、数据结构之类的问题。Google整个架构的发展是根据需求的变化而发展而来的,MapReduce之类的不就是在遇到需要解决大规模并行编程这个问题时产生的实用的解决方案吗?可是,如果没有扎实的基本功它能被设计出来么?哪一个大师不是编程十几二十年以上?他们的基本功可能差么?想真正成为杰出的程序员,没有扎实的基本功是绝对不可能的,因为你会发现当你需要面对一个没有现成的解决方案的问题时,你的基本功就是最可信赖的法宝。

我在国内念书时确实也不知道天有多高,国内IT界有多浮躁,到了瑞典之后我有机会在Nema Labs(创业公司),Ericsson(大公司)实习,跟我的导师Per Stenström学习,与John Hughes这样的大师交流,眼界真的开阔了很多。浮躁在中国是很普遍的社会性现象,就拿程序员职业生涯发展来说,中国现在很难找到有十几二十年经验的超级程序员,为什么?因为他们都转到管理方向去了,当CEO,CTO去了。我觉得这是由中国“官本位”的社会思想导致的。大家都觉得管人的比被管的等级高,要拿更高的工资,这实在是大错特错。实际上在外国公司里终身从事技术工作的超级工程师大有人在,而且这些超级工程师的工资往往比他们的Manager高得多。在瑞典,做基站的超级工程师时薪4K多克朗的都有(克朗跟人民币几乎等值,绝对真实),50W年薪的比比皆是,这样的待遇还会让你觉得当一辈子工程师没前(钱)途吗?我觉得走管理路线本身没有错,前提是你确实喜欢管理,善于交流,适合你的性格,而不是为了职业发展“被迫”往管理方向转。在现代企业中,管理者与被管理者本身没有高低贵贱之分,只是职能不同罢了。最顶级的程序员不仅受人尊重,更可以拿高薪。可惜国内社会风气普遍浮躁,这样的状况想要改变还需要很长时间。从供需的角度来讲,超级程序员的身价是由市场需求决定的。就拿华为来说,我上次跟他们在瑞典这边的一位技术负责人聊天时了解到他们在Kista最喜欢有十几年以上经验的超级工程师,因为这样的人才国内根本招不到。为什么他们需要招这样的人?因为华为的竞争对手也是世界级的企业(例如Ericsson),这个时候科技创新就是企业最重要的核心竞争力,自然就需要最顶级的工程师才能在竞争中胜出。我们看到的Google花250W美金挽留一位女工程师的例子(未经证实,可能是Facebook负责招聘的人炒作)不也刚刚发生么?国内不也出现了年薪200W的工程师牛新庄么?我觉得随着中国IT行业的发展,科技创新将会变得越来越重要,而超级程序员也会越来越成为香饽饽,如果各位同学确实热爱编程,愿意一辈子编程,我希望你坚持下去,因为只要你成为超级程序员肯定会有赏识你的公司。现在的盛大创新院好像做的不错,他们给高级研究员年薪能有30W+,可以算是一个招聘高端人才的例子。而一个反例就是不依靠科技创新的公司(例如团购网站),它们确实是不怎么需要高端人才的,这样的公司不怎么靠技术取胜。

当然,技术不是最重要的,哪怕对Google,对Facebook也是一样。再高端的技术也必须找到市场,满足消费者的需求才能创造财富。我现在相信的是市场>管理>技术。是走管理路线还是走技术路线最好是按照你自己的性格特点来,喜欢干哪个就做哪个,而不是跟风去做管理。只要你努力,做什么都会有回报。

3. 关于英语

关于程序员个人发展,我不得不提及英语能力。我个人感觉,英语是阻碍中国程序员提升眼界的一道非常重要的关卡。关于英语于程序员之重要性,Joe在此书里面说了一句“If you are not good at English you’ll never be a very good programmer.”在欧美IT企业引领科技潮流的今天我们不去学习他们的技术怎么可能追上甚至超越他们?我建议所有有追求的程序员一定要把英语当做最基本的一门编程语言来学习!我自己的亲身经历是:英语帮我打开了另一个更广阔的世界的大门,从此直接阅读原版书酣畅淋漓的学习新知识,从此随意阅读最新的论文了解新动态,从此直接与最厉害的程序员毫无障碍的交流!

4. 创新+创业

我在最近一次Ericsson Research Day上有幸与John Hughes在Demo Session成为邻居,所以才出现了我在推上征求推友关于Erlang问题的一幕。John是从Basic开始学习编程的,在牛津念博士时就做的就是函数式编程的研究,他也是Haskell的创始人之一,95年他来到Chalmers任教至今。他学术上最有影响力的论文之一“QuickCheck: A lightweight Tool for Random Testing of Haskell Programs”成为了他后来创办的Quviq的技术核心。这个公司目前只有四名员工,当然四个人各个都是教授(我知道另一个专做编译器前端的传奇公司EDG也只有5个人)。John为人非常亲切,我跟他聊的非常开心。他追求的编程之美(好吧,我本也不想再用XX之美,但是实在没更合适的词了)是make programming easier — I like my programs to be short, beautiful, and elegant, and I hate drudgery。我还问他你编程是不是有快40年了?他老人家(其实他跟Joe都是精气神特好,非常年轻的那种)想了半天说还真有四十年了。我最羡慕他一点是,他跟我导师Per Stenström一样横跨学术界与工业界,创新与创业双管齐下,互利互惠,既是学识渊博的教授,又是能给社会创造价值的企业家,人生如此,夫复何求?我跟他说真羡慕你真能享受双倍乐趣啊,他说是啊,真是太有趣了!其实中国教授也有在工业界与学术界都取得成功的例子,例如普林斯顿的Li Kai教授和UCSD的Zhou Yuanyuan教授,所以说主要还是环境问题导致的。我个人是龙芯的坚决拥护者,很多人说怎么用MIPS的授权,怎么浪费国家的钱什么什么的,我觉得这些都是扯淡。从我知道的情况来看,龙芯他们组最近把Micro, HPCA, ISCA, ISSCC这些最顶级的会议全发了一个遍,学术水平毫无疑问!胡伟武老师用毛泽东思想来带领团队是有效的(不管是否有失偏薄),而且也有Chen Yunji这样的青年才俊,我相信至少龙芯团队培养出来的这批人才已经足以对社会做出贡献。现在龙芯商业化还处在初期阶段,任重而道远,我祝福他们,看好他们!

中国的发展需要创新!需要最高端的科技人才!需要最顶尖的程序员!

多线程程序常见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的教授了。

史蒂夫乔布斯(Steve Jobs)在Stanford2005年毕业典礼上的演讲

我觉得这是我看过的最好的演讲之一。三个故事每一个都让我深受触动。

这句话让我忍不住留下眼泪:
“And most important, have the courage to follow your heart and intuition. They somehow already know what you truly want to become. Everything else is secondary.”
“还有最重要的是, 你要有勇气去听从你直觉和心灵的指示——它们在某种程度上知道你想要成为什么样子,所有其他的事情都是次要的。 ”

今天我老板Prof. Per Stenström也跟我说:
“Keep the focus on what you believe in and keep delivering what you promised yourself to deliver. Your contributions will not only be rewarding for yourself; it will likely make a significant contribution to our society.”

博士与工业界之间我选择了后者,在即将毕业之时,我热切期待着下一个让我成长的机会,每个人都应该寻找并追寻自己内心最深切的渴望,Stay hungry, Stay foolish!

多线程队列的算法优化

多线程队列(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密集型客户端单写者多读者场景。

多核的未来

UT Austin的Yale Patt教授上个月来Chalmers交流,做了题为《Future Microprocessors: Multi-core, Mega-nonsense, and What We Must Do Differently Moving Forward》的讲座。Yale Patt是计算机体系结构学术圈的巨擘,他最有名的研究成果是和Branch Predictor和HPS microarchitecture,他的学生们也巨牛无比,学术界有名的有UIUC的Wen-Mei Hwu,CMU的Onur Mutlu等等,工业界Intel不少核心工程师也出自他的门下。这个讲座主要谈了他对未来的多核处理器的发展的看法,有趣的是他二十年前也预测过现在的处理器,我还专门问了他当时的预测是否靠谱,他说“那我得回去查查看才行”,人非常的Nice。

简单介绍一下关键的几点:

1. 为什么要多核?
It is easier than designing a much better uni-core
It is cheaper than designing a much better uni-core
It was embarrassing to continue making L2 bigger
It was the next obvious step

2. Asymmetric Chip Multiprocessor才是未来
一个chip上既有Large Core,又有Small Core,前者专门用来加速那些诸如Critical Section之类的串行代码。

3. ILP未死
其实还有ILP的性能很多可挖掘的空间,只是多核设计上更经济更简单,所以大家都慢慢转到多核上来了

4. Parallel Programming is NOT Hard
如果从新生就开始进行并行编程的教育,从一开始就thinking in parallel,并行编程就不难,关键是打破Abstraction。

UIUC的Distinguished Lecture Series也有他今年4月在UIUC的讲座,甚至还有video。

Enjoy!

多核编程的难题(二)

刚刚过去的一个月一直都在忙着赶实验赶论文,直到前几天完成一篇短论文的写作才得以抽身来补上这一篇关于多核的曙光的文章。我将分几个方面来阐述一下我对多核上并行编程持乐观态度的原因。

1. 较易并行化的应用

如果一个应用的子任务之间依赖关系比较小,相互独立性强,那么它就具有很好的可并行性。很容易我们就会想到服务端的应用。服务端应用的特征就是为多用户提供相似的服务,因为它本身具有内在的并行性,所以相比那些子任务之间依赖性很强的应用来说,它们是比较适合多核的。这些应用常见的例子有大型数据库、飞机票预订系统、银行交易系统、网络搜索、游戏服务器以及云计算所提供的软件即服务(SaaS)等等。

另一种大量采用并行化的成功案例就是图像处理了。举个简单的例子,渲染一幅图像这个任务就充满了大量的数据级并行(data-level parallelism):一幅图像是由许许多多的像素组成的,而现在的GPU都有成百个核心,我们可以比较容易的做到让每个GPU核心分别负责渲染图像的一部分,从而快速的完成整个计算任务。虽然现在来讲GPU上面的编程很难,但是它所能提供的性能提升确实非常可观。

还有很火的GPGPU应用(General-purpost computing on GPU),它们在Scientific Computing领域也有不少成功案例,虽然John Carmack就在Twitter上对GPGPU编程的困难性这样评价过:“Hundreds of GPGPU research papers valiantly struggling with graphic API limitations are painfully obsolete with CUDA / OpenCL available.”其实Scientific Computing可以算是多核上的杀手级应用了,典型的例如天气预测、气候模拟等运用,为了得到更精确的结果肯定就需要处理更多的数据,而且是必须在短时间内出结果,要不然你预测后天的天气但是一个礼拜才给你出结果怎么行?这些大数据量的计算任务对性能的需求永远都是非常大的。而且这些应用本身有很多数据级的并行性,再加上这个领域一般都是行业专家和软件工程师的组合,大规模的应用并行计算是很自然的事情。

2. 我们有持乐观态度的理由

为什么我们可以对多核发展持乐观态度?因为第一点,现在整个工业界、学术界都在研究多核,研究怎样简化并行编程、怎样降低功耗、怎样持续提升性能。Intel和Microsoft资助UIUC和UC Berkeley建立了两个重点实验室,其他顶级研究机构对多核的研究也如火如荼,大量最顶尖的人才都在帮助普及并行计算。第二点,Motivation,即“动机”。免费午餐都结束了,想继续提升性能?你只能进行并行编程。不管是客户端应用也好服务器端应用也好,用户对性能的需求肯定是不会停止的。当并行编程成为持续提升性能的唯一选择时,再困难你也得去做对不对?不过大家不用特别担心,对广大的程序员来讲,一项新技术的普及本身就是需要时间的,现在来讲大量帮助程序员进行并行编程的软硬件工具都在处在发展阶段,我们有理由相信并行编程会更容易更大众。

3. 多核的发展趋势

9月初我去参加斯德哥尔摩举办的Multicore Day时听了一位在Intel负责Nehalem的首席工程师的演讲,里面有几点我记忆深刻:
(1)单核的性能仍在提升
虽然整个工业界主题是往多核发展,但是处理器的单线程性能仍然在持续提升,这是由需求决定的。例如Nehalem架构的i7的单线程性能是奔4的5倍,这一需求也在Google在Micro 2010的论文”Brawny cores still beat wimpy cores, most of the time“中得到印证。这篇文章的核心观点就是性能较弱但是功耗较低的”小号“处理器只有在它们的单核性能接近中档的”大号“处理器时才具有足够的竞争力,否则它们羸弱的单核性能会成为Google现有应用中的性能瓶颈。虽然当初整个业界因为单核性能提升太困难而被迫转向更易实施的多核
(2)CPU和GPU的融合趋势
现在业界已经认同GPU比CPU更适合做数据级并行,而且这类应用需求量很大,这种需求就催生了Intel的Larrabee项目。虽然Larrabee流产了,但是它的技术还在,以后迟早会出现在Intel的产品线上。为了追求更高的性能,GPU和CPU结合的方案会是最好的选择,当然,怎样在这样的硬件上编程又是一个很大的难题。
(3)性能与功耗都重要
Intel的工程师一直在努力确保处理器的性能提升的同时它的功耗也一直在稳步下降。为什么说功耗很重要?我们可以举个很简单的例子,笔记本电脑上运行PowerPoint的速度已经很快了,让PowerPoint运行速度快个一两倍其实并不那么重要,但是如果在保证它运行速度的同时还能让笔记本的续航时间提升一些,这就很有意义了。服务器端更不用说了,现在哪个数据中心不把功耗当做头等大事来考虑?

4. 并行编程的普及教育

虽然说传统的应用一直都以串行计算为背景,所以现在来讲大家普遍觉得并行编程很困难。但是我们换个思路看看:如果从大一开始我们就教新生《并行算法》《并行编程导论》呢?如果程序员一开始就接受的是并行编程的教育,并行编程还是困难的吗?其实我们整个世界本身就充满了并行,人可以同时听课和做笔记,同时吃饭和交流,而计算机硬件更是可以并行工作,为什么软件就不可以?算法导论最新的第三版专门添加了一章《多线程算法》,(该书其中一位作者Prof. Charles Leiserson创办的并行编程的公司Cilk Art也已被Intel收购)让我大胆想象一下,整本算法导论通篇都是“并行”的时代还会远吗?

多核编程的难题(一)

最近David Patterson老爷子(就是计算机体系结构–量化方法的作者之一)发表了一篇文章《The trouble with multicore》,文章高屋建瓴的分析了一下多核发展的当前形势,文章开篇就说了一句话“造芯片的家伙们正忙着生产那些大多数程序员不知道如何编程的多核CPU”。这不由的让我想起我跟我导师Per Stenstrom的一次对话,我问他说“现在多核出来了,有一大堆新的难题等着我们去解决,作为研究人员您是否觉得很兴奋呢?”结果他说“其实我还是有点沮丧的,因为我们是被迫转到多核上来的。”

其实这就道出了多核发展中的一个关键:造硬件的没办法在单核上继续像以前那样容易地提升性能了(有兴趣的朋友可以查下“Power Wall”),为了利用更多的晶体管提高性能,只好走多核这条路,但是在他们选择走这条路的时候,所有人都不知道该如何在多核平台上有效的进行编程,David Patterson管这个叫“Hail Mary”,简单翻译过来就是“让我们多核吧,但是该咋进行多核编程就祈祷奇迹的发生吧!”

好吧,为什么多核编程很困难?一个形象的例子就是把编程比作写书,理论上10个作者同时写一本书应该会比一个人写快10倍。但是他们首先要把任务均匀的分成10份,否则任务最多的那个作者会拖后腿肯定就快不了10倍了。但是呢光这个还不够,如果这个故事中的某一部分必须要在其他部分写完之后才能写,这种顺序上的依赖关系也会拖慢速度;而且10个作者的故事情节还得一致,那么他们肯定少不了沟通啊,这又慢了一点。这就是三个多核编程的最大挑战:“load balancing(负载均衡)”、“sequential dependency(顺序依赖关系)”和“synchronization(同步)”。

难道就没有人尝试着解决这个问题吗?有啊!从60年代开始,一堆一堆的天才们尝试着创造新的编程语言好让并行编程更加美好:APL,Id,Linda,Occam,SISAL等等,他们中有的确实让并行编程更加容易了,但是没有一个人能成功的让他们向传统的串行编程语言一样兼具性能、效率和灵活性,更没有像C/C++、Java这样主要为串行编程设计的语言一样流行。我记得有人问过“Java的并发包挺好用的啊,是不是足够解决多核编程的问题了呢?”,我觉得不然。在语言上进行并行编程的扩展确实是有效的办法,但是它却不能从根本上解决并行编程困难的问题。最根本的原因是这些语言并不是天生为并发而设计的,这就决定了所有的库都只能给你提供并行编程最原始的工具,但是对程序员来说并行编程却并没有因为有了这些库就变得更容易了,你还是得面临死锁dead lock、数据竞跑data race、伪共享false sharing、锁竞争lock contention等种种问题。

讲到这我就想起Erlang了,它就是一种天生为并发设计的语言。它的并发模型核心是基于消息传递机制的轻量级进程,进程之间不共享内存。这样的模型好处就在于每个进程是相互独立的,要通信就发消息好了,最大程度上减少了进程间的依赖关系,从而能提高整体性能,而且核越多跑的越快。但是我们要考虑到Erlang最初是Ericsson为电信系统设计的语言,由它编写的程序的目标就是为了提高系统的throughput以便为更多的用户提供服务,这也是大部分服务器端程序的目标。它们的共同特征是每个用户的请求大部分情况下都是彼此独立的,所以多核对这样的高并发应用来讲其实是有点天生一对的感觉。但是对于传统的客户端程序来讲,latency才是它们的首要目标。例如大型的商业软件,它所希望的是完成一个任务的速度能够更快,或者单位时间内能处理更多的数据。

另一个解决并行编程难的思路就是设计更易进行并行编程的硬件,现在最火的Transactional Memory(事务性内存)就是其中的典范。但是现在它们还只处于研究阶段,里面有一大堆的问题尚待解决,最主要的就是性能还不足以到商用阶段。

还有的人尝试过用编译器自动并行化,但是多年的研究表明纯粹让编译器来给你进行自动并行化是完全走不通了。它能在一定程度上提升程序的性能,但是非常有限,而且随着核数的增加它对性能的提升会更加有限。

那么多核时代的曙光在哪里呢?请看我下一篇文章