并行编程中的“锁”难题

注:本文发表于《程序员》2011年第8期并行编程专栏,略有删改。

在并行程序中,锁的使用会主要会引发两类难题:一类是诸如死锁、活锁等引起的多线程Bug;另一类是由锁竞争引起的性能瓶颈。本文将介绍并行编程中因为锁引发的这两类难题及其解决方案。

阅读全文>>

注:本文发表于《程序员》2011年第8期并行编程专栏,略有删改。

在并行程序中,锁的使用会主要会引发两类难题:一类是诸如死锁、活锁等引起的多线程Bug;另一类是由锁竞争引起的性能瓶颈。本文将介绍并行编程中因为锁引发的这两类难题及其解决方案。

1. 用锁来防止数据竞跑

在进行并行编程时,我们常常需要使用锁来保护共享变量,以防止多个线程同时对该变量进行更新时产生数据竞跑(Data Race)。所谓数据竞跑,是指当两个(或多个)线程同时对某个共享变量进行操作,且这些操作中至少有一个是写操作时所造成的程序错误。例1中的两个线程可能同时执行“counter++”从而产生数据竞跑,造成counter最终值为1(而不是正确值2)。
例1:

#include <pthread.h>
int counter = 0;
void *func(void *params)
{
    counter++; //数据竞跑
}
void main()
{
    pthread_t thread1, thread2;
    pthread_create(&thread1, 0, func, 0);
    pthread_create(&thread2, 0, func, 0);
    pthread_join(thread1, 0 );
    pthread_join(thread2, 0 );
}

这是因为counter++本身是由三条汇编指令构成的(从主存中将counter的值读到寄存器中;对寄存器进行加1操作;将寄存器中的新值写回主存),所以例1中的两个线程可能按如下交错顺序执行,导致counter的最终值为1:
例2:

load [%counter], rax; // 线程1从counter读取0到寄存器rax
add rax, 1; // 线程1对寄存器rax进行加1
load [%counter], rbx; // 线程2从counter读取0到寄存器rbx
store rax [%counter]; // 线程1把1写入counter的主存地址
add rbx, 1; // 线程2对寄存器rbx进行加1
store rbx, [%counter]; // 线程2把1写入counter的主存地址

为了防止例1中的数据竞跑现象,我们可以使用锁来保证每个线程对counter++操作的独占访问(即保证该操作是原子的)。在例3的程序中,我们使用mutex锁将counter++操作放入临界区中,这样同一时刻只有获取锁的线程能访问该临界区,保证了counter++的原子性:即只有在线程1执行完counter++的三条指令之后线程2才能执行counter++操作,保证了counter的最终值必定为2。
例3:

#include <pthread.h>
int counter = 0;
pthread_mutex_t mutex;
void *func(void *params)
{
    pthread_mutex_lock(&mutex);
    counter++; //处于临界区,不会产生数据竞跑
    pthread_mutex_unlock(&mutex);
}
void main()
{
    pthread_t thread1, thread2;
    pthread_mutex_init(&mutex);
    pthread_create(&thread1, 0, func, 0);
    pthread_create(&thread2, 0, func, 0);
    pthread_join(thread1, 0 );
    pthread_join(thread2, 0 );
    pthread_mutex_destroy(&mutex);
}

2. 死锁和活锁

然而,锁的使用非常容易导致多线程Bug,最常见的莫过于死锁和活锁。从原理上讲,死锁的产生是由于两个(或多个)线程在试图获取正被其他线程占有的资源时造成的线程停滞。在下例中,假设线程1在获取mutex_a锁之后正在尝试获取mutex_b锁,而线程2此时已经获取了mutex_b锁并正在尝试获取mutex_a锁,两个线程就会因为获取不到自己想要的资源、且自己正占有着对方想要的资源而停滞,从而产生死锁。
例4:

// 线程 1 					
void func1() 					
{ 						
    LOCK(&mutex_a); 	    	 		 
    LOCK(&mutex_b);//线程1停滞在此 		 
    counter++; 				    	 
    UNLOCK(&mutex_b); 	    	 		  
    UNLOCK(&mutex_a); 	    	 		 
} 						

// 线程 2
void func2()
{
    LOCK(&mutex_b);
    LOCK(&mutex_a);//线程2停滞在此
    counter++;
    UNLOCK(&mutex_a);
    UNLOCK(&mutex_b);
}

例4中的死锁其实是最简单的情形,在实际的程序中,死锁往往发生在复杂的函数调用过程中。在下面这个例子中,线程1在func1()中获取了mutex_a锁,之后调用func_call1()并在其函数体中尝试获取mutex_b锁;与此同时线程2在func2()中获取了mutex_b锁之后再在func_call2()中尝试获取mutex_a锁从而造成死锁。可以想象,随着程序复杂度的增加,想要正确的检测出死锁会变得越来越困难。
例5:

// 线程 1 					
void func1() 					
{ 						
LOCK(&mutex_a); 	    	 		 
...						
func_call1();			 	 
UNLOCK(&mutex_a); 	 		   	 
}						

func_call1()					
{						
   LOCK(&mutex_b);		 		 
   ...						 
   UNLOCK(&mutex_b);				 
   ...						 
}						

// 线程 2
void func2()
{
    LOCK(&mutex_b);
    ...
    func_call2()
    UNLOCK(&mutex_b);
}

func_call2()
{
    LOCK(&mutex_a);
    ...
    UNLOCK(&mutex_b);
    ...
}

其实避免死锁的方法非常简单,其基本原则就是保证各个线程加锁操作的执行顺序是全局一致的。例如,如果上例中的线程1和线程2都是先对mutex_a加锁再对mutex_b进行加锁就不会产生死锁了。在实际的软件开发中,除了严格遵守相同加锁顺序的原则防止死锁之外,我们还可以使用RAII(Resource Acquisition Is Initialization,即“资源获取即初始化”)的手段来封装加锁解锁操作,从而帮助减少死锁的发生[1]。

除死锁外,多个线程的加锁、解锁操作还可能造成活锁。在下例中,程序员为了防止死锁的产生而做了如下处理:当线程1在获取了mutex_a锁之后再尝试获取mutex_b时,线程1通过调用一个非阻塞的加锁操作(类似pthread_mutex_trylock)来尝试进行获得mutex_b:如果线程1成功获得mutex_b,则trylock()加锁成功并返回true,如果失败则返回false。线程2也使用了类似的方法来保证不会出现死锁。不幸的是,这种方法虽然防止了死锁的产生,却可能造成活锁。例如,在线程1获得mutex_a锁之后尝试获取mutex_b失败,则线程1会释放mutex_a并进入下一次while循环;如果此时线程2在线程1进行TRYLOCK(&mutex_b)的同时执行TRYLOCK(&mutex_a),那么线程2也会获取mutex_a失败,并接着释放mutex_b及进入下一次while循环;如此反复,两个线程都可能在较长时间内不停的进行“获得一把锁、尝试获取另一把锁失败、再解锁之前已获得的锁“的循环,从而产生活锁现象。当然,在实际情况中,因为多个线程之间调度的不确定性,最终必定会有一个线程能同时获得两个锁,从而结束活锁。尽管如此,活锁现象确实会产生不必要的性能延迟,所以需要大家格外注意。
例6:

// 线程 1 					
void func1() 					
{ 						
    int done = 0;					
    while(!done) {				 
        LOCK(&mutex_a); 	    	   		 
        if (TRYLOCK(&mutex_b)) {		 	   
            counter++; 				     
            UNLOCK(&mutex_b); 	    	     	     
            UNLOCK(&mutex_a); 	    	     	     
            done = 1;					     
        }						   
        else {					   
            UNLOCK(&mutex_a);		     	    
        }						   
    }						 
} 						

// 线程 2
void func2()
{
    int done = 0;
    while(!done) {
        LOCK(&mutex_b);
        if (TRYLOCK(&mutex_a)) {
            counter++;
            UNLOCK(&mutex_a);
            UNLOCK(&mutex_b);
            done = 1; 
        }
        else {
            UNLOCK(&mutex_b);
        }
    }
}

3. 锁竞争性能瓶颈

在多线程程序中锁竞争是最主要的性能瓶颈之一。在前面我们也提到过,通过使用锁来保护共享变量能防止数据竞跑,保证同一时刻只能有一个线程访问该临界区。但是我们也注意到,正是因为锁造成的对临界区的串行执行导致了并行程序的性能瓶颈。

3.1阿姆达尔法则(Amdahl’s Law)

在介绍锁竞争引起的性能瓶颈之前,让我们先来了解一下阿姆达尔法则。我们知道,一个并行程序是由两部分组成的:串行执行的部分和可以并行执行的部分。假设串行部分的执行时间为S,可并行执行部分的执行时间为P,则整个并行程序使用单线程(单核)串行执行的时间为S+P。阿姆达尔法则规定,可并行执行部分的执行时间与线程数目成反比:即如果有N个线程(N核CPU)并行执行这个可并行的部分,则该部分的执行时间为P/N。由此我们可以得到并行程序总体执行时间的公式:

总体执行时间T = S + P/N

根据这个公式,我们可以得到一些非常有意思的结论。例如,如果一个程序全部代码都可以被并行执行,那么它的加速比会非常好,即随着线程数(CPU核数)的增多该程序的加速比会线性递增。换句话说,如果单线程执行该程序需要16秒钟,用16个线程执行该程序就只需要1秒钟。
然而,如果这个程序只有80%的代码可以被并行执行,它的加速比却会急剧下降。根据阿姆达尔法则,如果用16个线程并行执行次程序可并行的部分,该程序的总体执行时间T = S + P/N = (16*0.2) + (16*0.8)/16 = 4秒,这比完全并行化的情况(只需1秒)足足慢了4倍!实际上,如果该程序只有50%的代码可以被并行执行,在使用16个线程时该程序的执行时间仍然需要8.5秒!
从阿姆达尔法则我们可以看到,并行程序的性能很大程度上被只能串行执行的部分给限制住了,而由锁竞争引起的串行执行正是造成串行性能瓶颈的主要原因之一。

3.2锁竞争的常用解决办法

3.2.1 避免使用锁

为了提高程序的并行性,最好的办法自然是不使用锁。从设计角度上来讲,锁的使用无非是为了保护共享资源。如果我们可以避免使用共享资源的话那自然就避免了锁竞争造成的性能损失。幸运的是,在很多情况下我们都可以通过资源复制的方法让每个线程都拥有一份该资源的副本,从而避免资源的共享。如果有需要的话,我们也可以让每个线程先访问自己的资源副本,只在程序的后讲各个线程的资源副本合并成一个共享资源。例如,如果我们需要在多线程程序中使用计数器,那么我们可以让每个线程先维护一个自己的计数器,只在程序的最后将各个计数器两两归并(类比二叉树),从而最大程度提高并行度,减少锁竞争。

3.2.2 使用读写锁

如果对共享资源的访问多数为读操作,少数为写操作,而且写操作的时间非常短,我们就可以考虑使用读写锁来减少锁竞争。读写锁的基本原则是同一时刻多个读线程可以同时拥有读者锁并进行读操作;另一方面,同一时刻只有一个写进程可以拥有写者锁并进行写操作。读者锁和写者锁各自维护一份等待队列。当拥有写者锁的写进程释放写者锁时,所有正处于读者锁等待队列里的读线程全部被唤醒并被授予读者锁以进行读操作;当这些读线程完成读操作并释放读者锁时,写者锁中的第一个写进程被唤醒并被授予写者锁以进行写操作,如此反复。换句话说,多个读线程和一个写线程将交替拥有读写锁以完成相应操作。这里需要额外补充的一点是锁的公平调度问题。例如,如果在写者锁等待队列中有一个或多个写线程正在等待获得写者锁时,新加入的读线程会被放入读者锁的等待队列。这是因为,尽管这个新加入的读线程能与正在进行读操作的那些读线程并发读取共享资源,但是也不能赋予他们读权限,这样就防止了写线程被新到来的读线程无休止的阻塞。
需要注意的是,并不是所有的场合读写锁都具备更好的性能,大家应该根据Profling的测试结果来判断使用读写锁是否能真的提高性能,特别是要注意写操作虽然很少但很耗时的情况。

3.2.3 保护数据而不是操作

在实际程序中,有不少程序员在使用锁时图方便而把一些不必要的操作放在临界区中。例如,如果需要对一个共享数据结构进行删除和销毁操作,我们只需要把删除操作放在临界区中即可,资源销毁操作完全可以在临界区之外单独进行,以此增加并行度。
正是因为临界区的执行时间大大影响了并行程序的整体性能,我们必须尽量少在临界区中做耗时的操作,例如函数调用,数据查询,I/O操作等。简而言之,我们需要保护的只是那些共享资源,而不是对这些共享资源的操作,尽可能的把对共享资源的操作放到临界区之外执行有助于减少锁竞争带来的性能损失。

3.2.4 尽量使用轻量级的原子操作

在例3中,我们使用了mutex锁来保护counter++操作。实际上,counter++操作完全可以使用更轻量级的原子操作来实现,根本不需要使用mutex锁这样相对较昂贵的机制来实现。在今年程序员第四期的《volatile与多线程的那些事儿》中我们就有对Java和C/C++中的原子操作做过相应的介绍。

3.2.5 粗粒度锁与细粒度锁

为了减少串行部分的执行时间,我们可以通过把单个锁拆成多个锁的办法来较小临界区的执行时间,从而降低锁竞争的性能损耗,即把“粗粒度锁”转换成“细粒度锁”。但是,细粒度锁并不一定更好。这是因为粗粒度锁编程简单,不易出现死锁等Bug,而细粒度锁编程复杂,容易出错;而且锁的使用是有开销的(例如一个加锁操作一般需要100个CPU时钟周期),使用多个细粒度的锁无疑会增加加锁解锁操作的开销。在实际编程中,我们往往需要从编程复杂度、性能等多个方面来权衡自己的设计方案。事实上,在计算机系统设计领域,没有哪种设计是没有缺点的,只有仔细权衡不同方案的利弊才能得到最适合自己当前需求的解决办法。例如,Linux内核在初期使用了Big Kernel Lock(粗粒度锁)来实现并行化。从性能上来讲,使用一个大锁把所有操作都保护起来无疑带来了很大的性能损失,但是它却极大的简化了并行整个内核的难度。当然,随着Linux内核的发展,Big Kernel Lock已经逐渐消失并被细粒度锁而取代,以取得更好的性能。

3.2.6 使用无锁算法、数据结构

首先要强调的是,笔者并不推荐大家自己去实现无锁算法。为什么别去造无锁算法的轮子呢?因为高性能无锁算法的正确实现实在是太难了。有多难呢?Doug Lea提到java.util.concurrent库中一个Non Blocking的算法的实现大概需要1个人年,总共约500行代码。事实上,我推荐大家直接去使用一些并行库中已经实现好了的无锁算法、无锁数据结构,以提高并行程序的性能。典型的无锁算法的库有java.util.concurrent,Intel TBB等,它们都提供了诸如Non-blocking concurrent queue之类的数据结构以供使用。

参考

[1] 陈硕.多线程服务器的常用编程模型.
[2] Darryl Gove. Multicore Application Programming
[3] 并行实验室. 多线程队列的算法优化.

[已经招到了,谢谢大家!]IBM中国研究院招聘Hadoop实习生

我们组最近有一个实习生的名额,做Hadoop性能优化相关的研究工作,如果大家感兴趣的话请给我发邮件:)

IBM Research China is looking for graduate computer science/engineering students who are interested in Hadoop performance optimizations works.

Location: Beijing
Job Tile: Research Intern
Job Openings: 1
Expected Duration: at least 3 months (full-time preferred)

Job responsibilities:
– Write MapReduce program and analyze Hadoop performance model.
– Tune and optimize the performance of Hadoop workloads.
– Publish high quality research papers to report your work.

Requirements:
– Creative and Self-motivated
– Knowledge of Parallel Computing and Distributed Systems.
– Knowledge of Java.
– Familiarity with Linux as development and testing environments.
– Knowledge of Apache Hadoop is a plus.
– Past research experience is a plus.

If you’re interested, please feel free to send your Chinese or English resume with the mail title of “Intern_Your Name_University_Major_Grade” (e.g. Intern_Zhang San_XXU_CS_Master) to chengc_at_cn.ibm.com.

我们组最近有一个实习生的名额,做Hadoop性能优化相关的研究工作,如果大家感兴趣的话请给我发邮件:)

IBM Research China is looking for graduate computer science/engineering students who are interested in Hadoop performance optimizations works.

Location: Beijing
Job Tile: Research Intern
Job Openings: 1
Expected Duration: at least 3 months (full-time preferred)

Job responsibilities:
– Write MapReduce program and analyze Hadoop performance model.
– Tune and optimize the performance of Hadoop workloads.
– Publish high quality research papers to report your work.

Requirements:
– Creative and Self-motivated
– Knowledge of Parallel Computing and Distributed Systems.
– Knowledge of Java.
– Familiarity with Linux as development and testing environments.
– Knowledge of Apache Hadoop is a plus.
– Past research experience is a plus.

If you’re interested, please feel free to send your Chinese or English resume with the mail title of “Intern_Your Name_University_Major_Grade” (e.g. Intern_Zhang San_XXU_CS_Master) to chengc_at_cn.ibm.com.

IBM中国研究院招聘大规模数据分析实习生

帮同事发文,招聘实习生:

IBM Research China is looking for undergraduate and graduate computer science/engineering students who are interested in Big Data Analytics development and performance optimizations works.

Location: Beijing
Job Tile: Research Intern
Job Openings: 1-2
Expected Duration: at least 3 months (full time)

Job responsibilities:
– Develop text mining solutions such as Topic Detection and Tracking (TDT).
– Write Apache MapReduce user function code to implement Social Network Analysis (SNA), Machine Learning and Text Mining algorithms.
– Tune and optimize the performance of Apache MapReduce/HDFS based analytics workload on POWER7.
– Publish high quality research papers to report your work.

Required skills:
– Knowledge of 1) Parallel Computing and Distributed Systems or 2) Machine Learning and Data Mining
– Knowledge of Java
– Familiarity with Linux as development and testing environments.
– Experience of Apache Hadoop will be a plus.

We also encourage exceptional students to generate and implement their own ideas about Big Data Analytics related works over the course of internship.

If you’re interested, please feel free to drop us an email to jwshi_at_cn.ibm.com with your resume.

浅析C++多线程内存模型

注:本文发表于《程序员》2011年第6期并行编程专栏,略有删改。

在即将到来的C++1x标准中,一个重大的更新就是引入了C++多线程内存模型。本文的主要目的在于介绍C++多线程内存模型涉及到的一些原理和概念,以帮助大家理解C++多线程内存模型的作用和意义。

阅读全文>>

注:本文发表于《程序员》2011年第6期并行编程专栏,略有删改。

在即将到来的C++1x标准中,一个重大的更新就是引入了C++多线程内存模型。本文的主要目的在于介绍C++多线程内存模型涉及到的一些原理和概念,以帮助大家理解C++多线程内存模型的作用和意义。

1. 顺序一致性模型(Sequential Consistency)

在介绍C++多线程模型之前,让我们先介绍一下最基本的顺序一致性模型。对多线程程序来说,最直观,最容易被理解的执行方式就是顺序一致性模型。顺序一致性的提出者Lamport给出的定义是:
“… the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program.”
从这个定义中我们可以看出,顺序一致性主要约定了两件事情:
(1)从单个线程的角度来看,每个线程内部的指令都是按照程序规定的顺序(program order)来执行的;
(2)从整个多线程程序的角度来看,整个多线程程序的执行顺序是按照某种交错顺序来执行的,且是全局一致的;

下面我们通过一个例子来理解顺序一致性。假设我们有两个线程(线程1和线程2),它们分别运行在两个CPU核上,有两个初始值为0的全局共享变量x和y,两个线程分别执行下面两条指令:
初始条件: x = y = 0;

线程 1 线程 2
x = 1; y=1;
r1 = y; r2 = x;

因为多线程程序交错执行的顺序是不确定的,所以该程序可能有如下几种执行顺序:

顺序 1 顺序 2 顺序 3
x = 1;
r1 = y;
y = 1;
r2 = x;
结果:r1==0 and r2 == 1
y = 1;
r2 = x;
x = 1;
r1 = y;
结果: r1 == 1 and r2 == 0
x = 1;
y = 1;
r1 = y;
r2 = x;
结果: r1 == 1 and r2 == 1

顺序一致性模型的第一个约定要求每个线程内部的语句都是按照程序规定的顺序执行,例如,线程1里面的两条语句在该线程中一定是x=1先执行,r1=y后执行。顺序一致性的第二个约定要求多线程程序按照某种顺序执行,且所有线程看见的整体执行顺序必须一致,即该多线程程序可以按照顺序1、顺序2或者顺序3(以及其他可能的执行顺序)执行,且线程1和线程2所观察到的整个程序的执行顺序是一致的(例如,如果线程1“看见”整个程序的执行顺序是顺序 1,那么线程2“看见”的整个程序的执行顺序也必须是顺序1,而不能是顺序2或者顺序3)。依照顺序一致性模型,虽然这个程序还可能按其他的交错顺序执行,但是r1和r2的值却只可能出现上面三种结果,而不可能出现r1和r2同时为0的情况。

然而,尽管顺序一致性模型非常易于理解,但是它却对CPU和编译器的性能优化做出了很大的限制,所以常见的多核CPU和编译器大都没有实现顺序一致性模型。例如,编译器可能会为了隐藏一部分读操作的延迟而做如下优化,把线程1中对y的读操作(即r1=y)调换到x=1之前执行:

初始条件:x=y=0;

线程 1 线程 2
r1 = y; y=1;
x = 1; r2 = x;

在这种情况下,该程序如果按下面的顺序执行就可能就会出现r1和r2都为0这样的违反顺序一致性的结果:

顺序 4
r1 = y;
y = 1;
r2 = x;
x = 1;

那么为什么编译器会做这样的乱序优化呢?因为读一个在内存中而不是在cache中的共享变量需要较长的时钟周期,所以编译器就“自作聪明”的让读操作先执行,从而隐藏掉一些指令执行的延迟,从而提高程序的性能。实际上,这种优化是串行时代非常普遍的,因为它对单线程程序的语义是没有影响的。但是在进入多核时代后,编译器缺少语言级的内存模型的约束,导致其可能做出违法顺序一致性规定的多线程语义的错误优化。同样的,多核CPU中的写缓冲区(store buffer)也可能实施乱序优化:它会把要写入内存的值先在缓冲区中缓存起来,以便让该写操作之后的指令先执行,进而出现违反顺序一致性的执行顺序。

因为现有的多核CPU和编译器都没有遵守顺序一致模型,而且C/C++的现有标准中都没有把多线程考虑在内,所以给编写多线程程序带来了一些问题。例如,为了正确地用C++实现Double-Checked Locking,我们需要使用非常底层的内存栅栏(Memory Barrier)指令来显式地规定代码的内存顺序性(memory ordering)[5]。然而,这种方案依赖于具体的硬件,因此可移植性很差;而且它过于底层,不方便使用。

2. C++多线程内存模型

为了更容易的进行多线程编程,程序员希望程序能按照顺序一致性模型执行;但是顺序一致性对性能的损失太大了,CPU和编译器为了提高性能就必须要做优化。为了在易编程性和性能间取得一个平衡,一个新的模型出炉了:sequential consistency for data race free programs,它就是即将到来的C++1x标准中多线程内存模型的基础。对C++程序员来说,随着C++1x标准的到来,我们终于可以依赖高级语言内建的多线程内存模型来编写正确的、高性能的多线程程序。

C++内存模型可以被看作是C++程序和计算机系统(包括编译器,多核CPU等可能对程序进行乱序优化的软硬件)之间的契约,它规定了多个线程访问同一个内存地址时的语义,以及某个线程对内存地址的更新何时能被其它线程看见。这个模型约定:没有数据竞跑的程序是遵循顺序一致性的。该模型的核心思想就是由程序员用同步原语(例如锁或者C++1x中新引入的atomic类型的共享变量)来保证你程序是没有数据竞跑的,这样CPU和编译器就会保证程序是按程序员所想的那样执行的(即顺序一致性)。换句话说,程序员只需要恰当地使用具有同步语义的指令来标记那些真正需要同步的变量和操作,就相当于告诉CPU和编译器不要对这些标记好的同步操作和变量做违反顺序一致性的优化,而其它未被标记的地方可以做原有的优化。编译器和CPU的大部分优化手段都可以继续实施,只是在同步原语处需要对优化做出相应的限制;而且程序员只需要保证正确地使用同步原语即可,因为它们最终表现出来的执行效果与顺序一致性模型一致。由此,C++多线程内存模型帮助我们在易编程性和性能之间取得了一个平衡。

在C++1x标准之前,C++是在建立在单线程语义上的。为了进行多线程编程,C++程序员通过使用诸如Pthreads,Windows Thread等C++语言标准之外的线程库来完成代码设计。以Pthreads为例,它提供了类似pthread_mutex_lock这样的函数来保证对共享变量的互斥访问,以防止数据竞跑。人们不禁会问,Pthreads这样的线程库我用的好好的,干嘛需要C++引入的多线程,这不是多此一举么?其实,以线程库的形式进行多线程编程在绝大多数应用场景下都是没有问题的。然而,线程库的解决方案也有其先天缺陷。第一,如果没有在编程语言中定义内存模型的话,我们就不能清楚的定义到底什么样的编译器/CPU优化是合法的,而程序员也不能确定程序到底会怎么样被优化执行。例如,Pthreads标准中并未对什么是数据竞跑(Data Race)做出精确定义,因此C++编译器可能会进行一些错误优化从而导致数据竞跑[3]。第二,绝大多数情况下线程库能正确的完成任务,而在极少数对性能有更高要求的情况下(尤其是需要利用底层的硬件特性来实现高性能Lock Free算法时)需要更精确的内存模型以规定好程序的行为。简而言之,把内存模型集成到编程语言中去是比线程库更好的选择。

3. C++1x中引入的atomic类型

C++作为一种高性能的系统语言,其设计目标之一就在于提供足够底层的操作,以满足对高性能的需求。在这个前提之下,C++1x除了提供传统的锁、条件变量等同步机制之外,还引入了新的atomic类型。相对于传统的mutex锁来说,atomic类型更底层,具备更好的性能,因此能用于实现诸如Lock Free等高性能并行算法。有了atomic类型,C++程序员就不需要像原来一样使用汇编代码来实现高性能的多线程程序了。而且,把atomic类型集成到C++语言中之后,程序员就可以更容易地实现可移植的多线程程序,而不用再依赖那些平台相关的汇编语句或者线程库。

对常见的数据类型,C++1x都提供了与之相对应的atomic类型。以bool类型举例,与之相对应的atomic_bool类型具备两个新属性:原子性与顺序性。顾名思义,原子性的意思是说atomic_bool的操作都是不可分割的,原子的;而顺序性则指定了对该变量的操作何时对其他线程可见。在C++1x中,为了满足对性能的追求,atomic类型提供了三种顺序属性:sequential consistency ordering(即顺序一致性),acquire release ordering以及relaxed ordering。因为sequential consistency是最易理解的模型,所以默认情况下所有atomic类型的操作都会使sequential consistency顺序。当然,顺序一致性的性能相对来说比较差,所以程序员还可以使用对顺序性要求稍弱一些的acquire release ordering与最弱的relaxed ordering。

在下面这个例子中,atomic_bool类型的变量data_ready就被用来实现两个线程间的同步操作。需要注意的是,对data_ready的写操作仍然可以通过直接使用赋值操作符(即“=”)来进行,但是对其的读操作就必须调用load()函数来进行。在默认的情况下,所有atomic类型变量的顺序性都是顺序一致性(即sequential consistency)。在这个例子中,因为data_ready的顺序性被规定为顺序一致性,所以线程1中对data_ready的写操作会与线程2中对data_ready的读操作构建起synchronize-with的同步关系,即#2->#3。又因为writer_thread()中的代码顺序规定了#1在#2之前发生,即#1->#2;而且reader_thread中的代码顺序规定了#3->#4,所以就有了#1->#2->#3->#4这样的顺序关系,从而可以保证在#4中读取data的值时,#1已经执行完毕,即#4一定能读到#1写入的值(10)。

#include <atomic>
#include <vector>
#include <iostream>

std::vector<int> data;
std::atomic_bool data_ready(false);

// 线程1
void writer_thread()
{
data.push_back(10); // #1:对data的写操作
data_ready = true; // #2:对data_ready的写操作
}

// 线程2
void reader_thread()
{
while(!data_ready.load()) // #3:对data_ready的读操作
{
std::this_thread::sleep(std::milliseconds(10));
}
std::cout << ”data is ” << data[0] << ”\n”; // #4:对data的读操作
}

相信很多朋友会纳闷,这样的执行顺序不是显然的么?其实不然。如果我们把data_ready的顺序性制定为relaxed ordering的话,编译器和CPU就可以自由地做违反顺序一致性的乱序优化,从而导致#1不一定在#2之前被执行,最终导致#4中读到的data的值不为10。

简单的来说,在atomic类型提供的三种顺序属性中,acquire release ordering对顺序性的约束程度介于sequential consistency(顺序一致性)和relaxed ordering之间,因为它不要求全局一致性,但是具有synchronized with的关系。Relaxed ordering最弱,因为它对顺序性不做任何要求。由此可见,除非非常必要,我们一般不建议使用relaxed ordering,因为这不能保证任何顺序性。关于这三种属性更详细的信息大家可以参考[1]。

通过上面的例子我们可以看到,C++1x中的多线程内存模型为了通过atomic类型提供足够的灵活性和性能,最大限度地将底层细节(三种不同的顺序属性)暴露给了程序员。这样的设计原则一方面给程序员提供了实现高性能多线程算法的可能,但却也大大增加了使用上的难度。我个人的建议是,如果常规的mutex锁、条件变量、future信号能满足您的设计需求,那么您完全不需要使用atomic变量。如果您决定使用atomic变量,请尽量使用默认的顺序一致性属性。

4. 总结

本文对C++1x标准中新引入的多线程内存模型进行了简要介绍。C++1x多线程内存模型的引入使得广大C++程序员可以享受语言原生支持的多线程机制,并为实现高性能多线程算法提供了足够丰富的工具(例如atomic类型)。但是,多线程内存模型本身的复杂性,以及一些底层机制(例如不同的顺序性属性)的引入也给使用C++进行多线程编程带来了不小的复杂度。如何高效、可靠的利用好这些新引入的多线程机制将会成为一个新的挑战。

参考资料

[1] C++ Concurrency in Action
[2] C++1x standard draft
[3] Threads cannot be implemented as a library
[4] Memory Models: A Case for Rethinking Parallel Languages and Hardware
[5] The “Double-Checked Locking is Broken” Declaration

Facebook的Realtime Hadoop及其应用

在今年的SIGMOD‘11上,Facebook又发了一篇新paper(点此下载),讲述了它们在提高Hadoop实时性上的工作及其应用。简单来讲,他们的项目需求主要有:

1. Elasticity(伸缩性)
2. High write throughput(高写吞吐量)
3. Efficient and low-latency strong consistency semantics within a data center(单个data center内高性能、低延迟的强一致性)
4. Efficient random reads from disk(disk的高性能随机读)
5. High Availability and Disaster Recovery(高可靠性、灾后恢复能力)
6. Fault Isolation(错误隔离)
7. Atomic read-modify-write primitives(read-modify-write原子操作)
8. Range Scans(范围扫描)

阅读全文>>

在今年的SIGMOD‘11上,Facebook又发了一篇新paper(点此下载),讲述了它们在提高Hadoop实时性上的工作及其应用。简单来讲,他们的项目需求主要有:

1. Elasticity(伸缩性)
2. High write throughput(高写吞吐量)
3. Efficient and low-latency strong consistency semantics within a data center(单个data center内高性能、低延迟的强一致性)
4. Efficient random reads from disk(disk的高性能随机读)
5. High Availability and Disaster Recovery(高可靠性、灾后恢复能力)
6. Fault Isolation(错误隔离)
7. Atomic read-modify-write primitives(read-modify-write原子操作)
8. Range Scans(范围扫描)

最终他们选择了Hadoop和HBase作为解决方案的基石,因为HBase已经满足了上述需求中的大部分。与此同时,他们还做了如下三点改进以满足实时性需求:
1. File Appends
2. Name Node的高可靠性优化 (AvatarNode)
3. HBase的读性能的优化

文章还列举了三个基于此方案的应用:Facebook Message,Facebook Insight,Facebook Metric Systems,大家可以着重看看这三个应用的特点及需求是怎样被这个方案满足的。

在现在这个时代,只有大公司才有如此大的数据来做新东西,难怪Facebook,Google的paper被大量追捧了。

参考资料:
[1] Facebook’s New Realtime Analytics System: HBase To Process 20 Billion Events Per Day
[2] Real Time Analytics for Big Data: An Alternative Approach

下面是这篇文章的slides:

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

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

你好,2011!

2010年总结与2011年计划。

阅读全文>>

2010年总结

爱人。在08年8月24日踏上去瑞典的飞机时我曾跟我的女友说:“宝贝,你放心,等我回来”。今年我最大的成就之一就是实现了两年前的诺言。

家人。在暑假时我抽时间跟家人完成了一次欧洲游。“活在当下”是《追逐日光》作者的一句感慨,不要等到已经失去与你所爱的人相处的机会时再去后悔。

研究。10年大部分时间都用来做研究了。我非常庆幸能有机会与我的导师Per Stenström一起共事,从他身上我学到了非常非常多的东西,是他帮助我找到了自己的兴趣和方向,他给我的那句寄语更是让我终生受益。临别之际我跟他说,“现在我因你而骄傲,将来我一定努力使你因我而自豪。”

2010年最有感触的一句话:”仰望星空与脚踏实地”。前者提醒我想成为的是一个对社会有用的人;后者提醒我在特定的环境下该如何把事情做好。

2011年计划

自修。希望能全方面提升自己的修养。

研究。希望能发一篇顶级Paper。现在正在冲刺ICS。

工作。希望能在北京找到一份让我感到Exciting的工作,牛同事越多越好。

编程。希望今年至少能写三万行代码。

交际。希望能参加更多的线下聚会,认识更多的朋友。

读书。希望能读完12本书,至少3本非技术的。

博客。希望能写24篇博客。其实我觉得我写Wiki的形式更好,因为我的博客都很长。

锻炼。希望每周能锻炼一次。

效率。希望能全方面提升自己的个人效率。

感情,亲情。放在心中。

2011年的箴言:”Stay Hungry,Stay Foolish”。
郭去疾先生对这句话的解读我非常喜欢,特此与大家分享:

“乔布斯说stay hungry,我以为饥渴有三个层次:贪婪、成就动机、好奇心。三者分别关注:瞬间的结果,持续的过程,和远大的未知。三者也恰好对应了三种人:卑劣的投机者,艰辛的攀登者,与幸福的探索者。

乔布斯说的stay foolish,放在语言环境中(斯坦福毕业典礼),我觉得很有针对性的,是特别说给这些所谓名校毕业生听的,因为他们比较容易持才放旷,不可一世,或者投机取巧,追求捷径。翻译成中文,就是:切不要聪明反被聪明误。”

祝大家新年里幸福,平安,健康,开心!