页面

分类

关于spurious wakeup的坑

2016/10/11, by wingfire ; 分类: 计算机技术, 代码相关, 程序设计; 0 comments

最近新开了一个叫mui的项目,打算用来写material的管理界面。这里面要实现一个跨线程的同步事件处理,和SendMessage类似,但是要求允许从任意线程发起SendMessage,但是对应的事件处理必须在事件循环所在的线程中被执行。让事件处理在特定线程中执行,这个挺常见,boost.asio也是这么保证的。但是,这种执行都是异步的,而我需要的是同步的。即线程递送事件后就被阻塞住,直到该事件的响应在主线程中处理完毕。

当然,这个完全可以直接使用mutex和condition_variable来实现。但是代码未免有些啰嗦,测试是不是正确也不方便。golang的channel恰好特别适合这个场景,反正也觊觎了golang的channel许久,既然用在这里正好,那就山寨一个吧。

channel默认是不带缓冲的,其中有个关键特性传递数据时producer和consumer的同步。网上很多的山寨都搞错了,把线程安全的queue当作了channel,这是不对的。除非queue满了(如果实现有此限制的话),否则往queue中push数据是不必等待有人接收的,不会被阻塞。channel则不同,producer输出数据的过程是被阻塞的,直到被consumer取走。这样,channel的数据传递过程就可以被当作同步点来使用,queue是没有这个功能的。channel的这个同步特性是非常重要的特点,来源于CSP。

带缓冲的channel呢?和queue有什么区别?我觉得是没有本质区别的。所以我觉得golang的设计在l概念上是很分裂的,带不带缓冲应该是完全不同的东西。带了缓冲,同步点机制就没有了。我没看golang的实现代码,但是我很怀疑内部其实也是两套实现,两者的差别其实是很大的。希望golang专家有兴趣可以指点一下。

背景交代完毕。

    void push(T* t) {
        std::unique_lock<std::mutex> lock(this->mutex);

        this->cv_producer.wait(lock, 
             [&] {return this->tmp == nullptr; });  // line 1

        this->tmp = t;
        this->cv_consumer.notify_one();

        this->cv_sync_producer.wait(lock, 
             [&] {return this->tmp == nullptr; });   // Line 2

        this->cv_producer.notify_one();  // line 3
    }

    T pull() {
        std::unique_lock<std::mutex> lock(this->mutex);

        this->cv_consumer.wait(lock, 
             [&] {return this->tmp != nullptr; }); // line 4

        T ret = *this->tmp;
        this->tmp = nullptr;

        this->cv_sync_producer.notify_one();  // Line 5
        return ret;
    }

和queue不同,放置完数据后,push动作会阻塞在line 2处,直到pull中取走数据。当push线程离开语句line 2时,pull线程也几乎同时离开其语句5. 这里就是所需要的同步点。queue的push是不必有语句 2和3,直接返回就好。

简单吧?悲剧的是,因为spurious wakeup的缘故,这段代码有错误。所谓的虚假唤醒,就是condition variable并没有收到通知时,也被唤醒了。虚假唤醒的解释参见维基:https://en.wikipedia.org/wiki/Spurious_wakeup

当然,虽说发生虚假唤醒的条件无法断言,但实际上也不是完全不可捉摸的。就我在windows平台上所观察到的现象而言,似乎只有发生线程切换,且等待在同一个mutex上才会导致虚假唤醒。

假设有两个push线程A和B,当A等待在语句2处时,假设B等待在语句1. 这时pull线程进入,执行到语句5,企图通过cv_sync_producer唤醒线程A,然后自己返回了。本来期待的是A线程会被唤醒,然后把B释放,让下一个传输得以开始。然而因为虚假唤醒,偶然地,等在1处的线程B被唤醒了。B唤醒后,有可能抢在A之前被执行,于是也到等在了语句2处,释放了锁。A当然也会被唤醒 --本来唤醒目标就是它么--,但是因为B在等待前设置了tmp,A的条件检测失败,又重新进入等待。于是A、B都等在了语句2处。这是程序状态已经错误了。

接下来,又来了一个pull线程,消费掉了tmp,然后notify,释放出了一个等在2处的push线程,假设是A,那B线程还得等。此时的tmp将是null,导致pull进不来,但是此时2处的push也出不去,死锁。只要调用次数足够多,最终所有的push都会被积压在语句2处,而所有的pull则被堵在语句4,系统停摆 -- 当然,停摆之前的行为就已经错误了,所以停摆是好事,暴露了问题。

按照解决spurious wakeup的一般建议,设立一个条件变量的伴生标记,从条件变量被唤醒后,必须检查伴生的标记,以确保不是虚假唤醒。这段代码貌似也检查了标记tmp,但是这个标记是被两个条件变量共享了,因此出了问题。知道了原因和解决方案,纠正起来就很容易了:

    void push(T* t) {
        std::unique_lock<std::mutex> lock(this->mutex);

        this->cv_producer.wait(lock, 
             [&] {return this->tmp == nullptr; });

this->entered = true;

        this->tmp = const_cast<T*>(t);
        this->cv_consumer.notify_one();

        this->cv_sync_producer.wait(lock, 
             [&] {return this->tmp == nullptr; });

this->entered = false;

        this->cv_producer.notify_one();
    }

这是我第二次遭遇到虚假唤醒的问题了。但仔细回忆起来,恐怕很多年前在使用boost的时候似乎也遇到过一次,当时并没有搞明白具体原因,而是换了个实现消除bug了事。这次乘机查了一下boost 1.35的文档,果然里面是有提到虚假唤醒的问题的。这么说来,我其实已经是第三次掉同一个坑里了......

问题虽然解决了,但是不能不好奇为什么会存在虚假唤醒这样奇特的行为。掉进坑里三次固然是我的错,但这个坑本身显然是违背程序员人性的存在。从使用条件变量的角度来说,我看不出虚假唤醒有任何的利用价值,这个行为完全是负面的,为什么至今没有被消除呢?据此推测,这个特性存在的根源可能有两种可能,一种可能是技术上的限制,使得消除虚假唤醒不可能或者代价高昂。另一种可能,这就是一个早期的设计错误,只不过由于历史原因和技术壁垒,它被固化了。某个强势领域的错误渐渐地被固化成一种特性,这样的事情本来也是屡见不鲜的。

维基上的解释是,在某些架构上,要实现一个没有虚假唤醒条件变量可能大幅度拖慢条件变量的操作。看上去我的前一个猜测对了,那不难推测,这很可能和CPU的体系结构有关系。

那么,到底是哪些架构有这个问题?消除这个问题又会怎么付出性能代价的呢?这个链接 提出了同样的问题。这里有讨论,主要有两点理由,只涉及Linux。一个原因为signal,为了响应EINTR,按照惯例,系统调用是可能被EINTR中断并取消的,需要用户重新进入。第二个原因也和signal有关,Linux的内核通过系统调用futex实现signal,但是很难实现从内核代码回调signal handler,因此只好先返回用户空间。

我觉得这两个原因虽然是事实,但理由都很勉强。首先,系统调用响应signal是惯例,但并非真理。如果这是必须的话,难道lock操作也得响应signal?boost.thread的作者似乎也是这么认为的,代码是这样写的:

    BOOST_FORCEINLINE int pthread_mutex_lock(pthread_mutex_t* m)
    {
      int ret;
      do
      {
          ret = ::pthread_mutex_lock(m);
      } while (ret == EINTR);
      return ret;
    }

假设有多个pthread_mutex_lock已经被阻塞住了,因为signal要返回,这将导致惊群效应。这两个解释似乎并不那么可靠。正如猜测的,pthread_mutex_lock并不存在类似虚假唤醒的问题,手册明确写道:

If a signal is delivered to a thread waiting for a mutex, upon return from the signal handler the thread shall resume waiting for the mutex as if it was not interrupted.

并且

These functions shall not return an error code of [EINTR].

pthread_cond_wait的文档则说:

These functions shall not return an error code of [EINTR].

对于signal,

If a signal is delivered to a thread waiting for a condition variable, upon return from the signal handler the thread resumes waiting for the condition variable as if it was not interrupted, or it shall return zero due to spurious wakeup.

至此,我知道lock和wait都是同样经由futex实现的,从技术上来说,没有道理lock可以工作得仿佛不存在中断,而条件变量就不行。看来,虚假唤醒的根本原因并非是futex,毕竟windows平台上也有着同样的问题。

到目前为止,我还是没有找到有说服力的解释,倒是搜到一本书 《Programming with POSIX Threads》

添加评论:

 
 the email would not displayed
 

您可以使用 Markdown 语法。

您必须启用浏览器的 JavaScript 功能才能发表评论。