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

上一篇文章我们专门针对违反原子性(Atomicity Violation)的多线程程序Bug做了剖析,现在我们再来看看另一种常见的多线程程序Bug:违反执行顺序(Ordering Violation)。

简单来说,多线程程序各个线程之间交错执行的顺序的不确定性(Non-deterministic)是造成违反执行顺序Bug的根源[注1]。正是因为这个原因,程序员在编写多线程程序时就不能假设程序会按照你设想的某个顺序去执行,而是应该充分考虑到各种可能的顺序组合,从而采取正确的同步措施。

阅读全文>>

上一篇文章我们专门针对违反原子性(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的常见形式和常见解决办法。

阅读全文>>

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