条件変数とダンス(Two-Step Dance)を

条件変数(condition variable)同期プリミティブに対する待機／通知で発生する現象と回避策のメモ。

条件変数とミューテックスを使ったコードにおいて次のような現象が生じる。

スレッドAが条件変数cvに対して通知を行う。
条件変数cvに対してブロックされていたスレッドBのブロックが解除される。ただし、ミューテックスmtxはスレッドAにロック保持されたままのため、再びスレッドBはミューテックスmtxに対してブロックされる*1。
スレッドAがミューテックスmtxのロックを解放する。
ミューテックスmtxに対してブロックされていたスレッドBがブロック解除され、同ミューテックスのロック獲得に成功する。

#include <pthread.h>
int data = 0;  // 待機条件: 非0になるまで待機
pthread_mutex_t mtx;
pthread_cond_t cv;

int process();

void threadA()
{
  pthread_mutex_lock(&mtx);
  data = process();
  if (data) {
    pthread_cond_broadcast(&cv);  // (1)
  }
  pthread_mutex_unlock(&mtx);  // (3)
}

void threadB()
{
  pthread_mutex_lock(&mtx);
  while (data == 0) {
    pthread_cond_wait(&cv, &mtx);  // (2)
  }
  // (4) dataを用いた処理
  pthread_mutex_unlock(&mtx);
}

スレッドBの処理(4)が実行されるまでにブロック解除 → 再ブロック → ブロック解除（“Two-Step Dance”）が行われるため、処理系による不要なスレッドコンテキストスイッチ処理といった無駄が生じる。

Two-Step Dance
Sometimes you need to signal an event while holding a lock. This can be unfortunate if the waking thread needs to acquire the lock held, because it will be awakened only to find out that it must wait again. This is wasteful and increases the number of overall context switches. This situation is called the two-step dance, and can extend far beyond just two steps if many locks and events are involved.
Both Win32 and the CLR's condition variable support inherently suffers from the two-step dance problem. It is often unavoidable, or prohibitively difficult to work around.
http://msdn.microsoft.com/en-us/magazine/cc817398.aspx

さらに待機側のthreadB関数が多数のスレッドで実行される場合、条件変数cvに対してブロックされていたスレッド群が一斉に実行開始され、結果として単一ミューテックスmtxに対する高いロック競合(lock contention)が発生する（“Thundering Herd Problem”*2または “Lock Convoy”*3）。

回避策#1：条件変数通知をクリティカルセクション外で行う

条件変数cvへの通知をクリティカルセクション外、つまりミューテックスmtxのロック解放後とする。この移動により、スレッドBでは条件変数cvでのブロック解除 → ミューテックスmtxのロック獲得が再ブロック無しに行えるようになる。

void threadA()
{
  bool do_signal = false;
  pthread_mutex_lock(&mtx);
  data = process();
  do_signal = (data != 0);
  pthread_mutex_unlock(&mtx);
  // ロック解放後に条件変数に通知
  if (do_signal) {
    pthread_cond_broadcast(&cv);
  }
}

回避策#1の注意点

ただし、この回避策「条件変数通知をクリティカルセクション外への移動」は常に安全に実施できるとは限らない。安全でない具体例として、下記コードのような「条件変数で待機 → 条件変数オブジェクト自体を破棄」処理が挙げられる。スレッドスケジューリングによって不具合を引き起こす実行順序を数字で示す（単純化のため同時実行されるスレッドは1つと仮定している）。

// C++11
#include <mutex>
#include <condition_variable>

class X {
  std::mutex mtx_;
  std::condition_variable cv_;
  int refcount_;
  //...

public:
  X() : refcount_(1) {}

  void release()
  {
    {
      std::lock_guard<std::mutex> lk(mtx_);  // (2)
      --refcount_;                           // (3)
    }                                        // (4)
    // (ここでコンテキストスイッチ）
    cv_.notify_all();  // (10) BUG: X::cvは破棄されている!!
  }

  void wait()
  {
    std::unique_lock<std::mutex> lk(mtx_);       // (6)
    cv_.wait(lk, [=]{ return refcount_ == 0; })  // (7)
  }                                              // (8)
};

X* x = new X;

void threadA()
{
  x->release();  // (1)
}

void threadB()
{
  x->wait();  // (5)
  delete x;   // (9)
}

例えばChromiumプロジェクトの開発者向け文書 "Chrome C++ Lock and ConditionVariable" では下記のように指摘している。

Why put Signal() inside the critical section?
In most cases, it is correct to put Signal() after the critical section, but in Chrome code it is always both safe and efficient to put it inside the critical section. (TODO: verify this)
Some texts recommend putting Signal() after the critical section because this makes it more likely that the mutex is free when a thread attempts to reacquire it on return from Wait(). If the Signal() were inside the critical section, a naive implementation might wake the thread which could then block once more on the mutex held by the very thread that woke it.
Chrome's condition variables (and most reasonable implementations) detect this case, and delay waking the waiting thread until the mutex is free. (TODO: verify this) Hence, there is no performance penalty for calling Signal() inside the critical section.
http://www.chromium.org/developers/lock-and-condition-variable

回避策#2：処理系側での対処

先の "Chrome C++ Lock and ConditionVariable" でも指摘している（引用の後半）ように、汎用的にはライブラリ実装やカーネルスケジューラといった処理系側で対処する必要がある。

GNU/Linux でのスレッドプログラミング - NPTL (Native POSIX Thread Library) Programmingによれば、Linux上のfutexによる PThread 実装ではFUTEX_REQUEUE, FUTEX_CMP_REQUEUEフラグを導入してこの問題に対処している模様。

Solving 11 Likely Problems In Your Multithreaded CodeではWin32／CLRの条件変数もこの問題の影響を受けるとしか言及しておらず、Windows APIでの対処状況は不明。

yohhoyの日記

技術的メモをしていきたい日記

条件変数とダンス(Two-Step Dance)を

回避策#1：条件変数通知をクリティカルセクション外で行う

回避策#1の注意点

回避策#2：処理系側での対処