多线程程序常见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剖析(下)》有15个想法

  1. 常见的解决方案中加锁进行同步是有效方法,也想对最费额外性能;
    进行条件检查,可能会引入新的潜在危险,如 Ad Hoc Synchronization造成的。
    个人浅见

    1. 同意。加锁不是万能的,除了容易带来死锁等问题外,性能的损失也是最大的;
      引入条件判断确实会带来新的问题,事实上修复多线程Bug的过程中很多最开始的修复方案都带来了新的bug:)

  2. 请问博主,目前并发算法的proof of correctness是否都是基于Lamport 77年的论文的?

    1. Lamport大神当然是这个方向的先驱 验证并行算法正确性用的最多的是Model Check 例如这篇文章:http://research.microsoft.com/en-us/um/people/lamport/pubs/dcas.pdf

  3. 现在lock很高效了。
    如果特殊地方(这里指的特殊就要看需求了)lock设计的好,lock的性能损失将不是特别大,
    还是可以接受的

    1. 恩 看能不能满足性能需求了。lock想要提高性能就得用细粒度的,但是会带来两个问题:1是锁本身的overhead会增加,2是容易出死锁、活锁、护航之类的bug

  4. 我这有一个例子,涉及volatile的使用以及多核并发的问题。
    TICK模块本身有一个线程,每隔一段时间调用TickRolling更新tick;
    同时提供TickGet接口供其它线程使用。
    它使用两个读缓冲区互相交换来避免使用锁保护共享变量,但存在两个问题;
    有人能看出来吗?

    unsigned int m_uiRollingTickHigh[2];
    unsigned int m_uiRollingTick[2];
    unsigned int m_uiTickIndex;

    int TickGet(unsigned int *puiHigh, unsigned int *puiLow)
    {
    unsigned int uiIndex;

    uiIndex = m_uiTickIndex;
    *puiHigh = m_uiRollingTickHigh[uiIndex];
    *puiLow = m_uiRollingTick[uiIndex];
    /*
    {
    unsigned int uiOther;
    uiOther = m_uiRollingTick[1 – uiIndex];

    m_uiTickDebugRecIdx[m_uiTickDebugRecIndex] = uiIndex;
    m_uiTickDebugRecMine[m_uiTickDebugRecIndex] = *puiLow;
    m_uiTickDebugRecOther[m_uiTickDebugRecIndex] = uiOther;
    m_uiTickDebugRecIndex = (m_uiTickDebugRecIndex + 1) & (TICK_REC_MAX – 1);
    }
    */

    return 0;
    }

    void TickRolling(unsigned int uiMillSec)
    {
    unsigned int uiRollingTickAndLost;
    unsigned int uiLostTicks = uiMillSec/1000;
    m_uiRollingTickHigh[1] = m_uiRollingTickHigh[0];
    m_uiRollingTick[1] = m_uiRollingTick[0];
    m_uiTickIndex = 1;

    uiRollingTickAndLost = m_uiRollingTick[0] + uiLostTicks;
    if(m_uiRollingTick[0] > uiRollingTickAndLost)
    {
    m_uiRollingTickHigh[0]++;
    }
    m_uiRollingTick[0] += uiLostTicks;
    m_uiTickIndex = 0;
    }

    1. 如果TickRolling和TickGet这两个函数都会被多个线程同时调用,则必须保证对m_uiRollingTickHigh[2], m_uiRollingTick[2],m_uiTickIndex这几个共享变量的读写操作是原子的

  5. hi ,您好。非常感谢您的分享,今天看了您的BLOG后受益匪浅,再次谢谢了哈。向您请教一个问题,即“什么样的数据结构及其操作具有多线程安全性”。就目前所知,单入单出的queue在读写模型里具有线程安全(一个线程读,一个线程写)。但是除了您介绍关于多线程的BUG外,我总结不出较好的判定条件,希望得到您的帮助,谢谢了!

    1. Hi,谢谢你的问题。如果你用C++,请直接使用boost或者C++1x中加入的线程安全的数据结构,如果你使用Java,请直接使用线程安全的queue等数据结构。千万不要自己去写,直接用就好了:)

  6. 加锁会带来死锁问题我遇到过。比如有个数据结构包括一个状态机和一个callback指针,在Running阶段会循环调用callback,若不用锁同步会在Reset操作中使得callback被清零,加锁又会导致库死锁。后来的解决方案没有用所,而是reset操作不对callback指针清零,仅仅清除状态机,并且在另一个线程加上状态机的条件判断即可避免(当然还要确保此时callback中的数据仍是有效的)。

发表评论

电子邮件地址不会被公开。 必填项已用*标注