多线程程序常见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的内存模型，敬请期待。