并行编程中的“锁”难题

注:本文发表于《程序员》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] 并行实验室. 多线程队列的算法优化.

多线程程序常见Bug剖析(上)

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

多线程队列的算法优化

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