多线程程序常见Bug剖析（上）

trackback: http://www.parallellabs.com/2010/11/13/concurrency-bugs-1/

编写多线程程序的第一准则是先保证正确性，再考虑优化性能。本文重点分析多线程编程中除死锁之外的另两种常见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）

何谓原子性？简单的说就是不可被其他线程分割的操作。大部分程序员在编写多线程程序员时仍然是按照串行思维来思考，他们习惯性的认为一些简单的代码肯定是原子的。

例如：

01 02 03 04 05

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++”这样的操作了。这条语句本身不是原子的，因为它在大部分硬件平台上其实是由三条语句实现的：

01 02 03

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”组成的。

01 02 03 04 05 06 07

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看似很正常：

01 02

Parallel.For(0, 10000, i => {a[i] = new Foo();})

实际上，如果我们去看看Foo的实现：

01 02 03 04 05 06 07 08

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[]中不同的元素；

01 02 03 04

Parallel.For(1,1000, i => { a[i] = x; });

例如下面这个例子在构造函数中给x和y赋值（此时别的线程不能访问它们），保证了isolation；一旦构造完毕x和y就是只读的了，保证了immutability。

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17

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！）。被锁保护起来的临界区在别的线程看来就是“原子”的，不可以被打断的。

01 02 03 04 05 06 07

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），例如：

01 02 03

if(!queue.isEmpty()) { queue.poll(obj); }

事实情况就是在调用isEmpty()之后，poll()之前，这个queue没有被其他线程修改是不确定的，所以对于这种情况，我们还是需要自己同步，用加锁的方式来保证原子性（虽然这样很损害性能）：

01 02 03 04 05

synchronized(queue) { if(!queue.isEmpty()) { queue.poll(obj); } }

但是注意了，使用锁也会造成一堆Bug，死锁就先不说了，先看看初学者容易犯的一个错误（是的，我曾经也犯过这个错误），x在两个不同的临界区中被修改，加了锁跟没加一样，因为还是有数据竞争：

01 02 03 04 05 06 07 08 09 10 11 12

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的教授了