条件変数(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
http://msdn.microsoft.com/en-us/magazine/cc817398.aspx
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.
さらに待機側の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?
http://www.chromium.org/developers/lock-and-condition-variable
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.
回避策#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での対処状況は不明。
関連URL
*1:この「条件変数に対するブロック解除→ロック獲得失敗による再ブロック」は、実際には待機関数(POSIXならば pthread_cond_wait 関数)の内部実装で行われる。言語処理系やライブラリに依らず、条件変数に対する待機関数の仕様では必ず「ミューテックスのロックが保持されていること」が事後条件として指定されている。
*2:wikipedia:en:Thundering herd problemも参照。直訳すると「大規模な動物の群れ問題」。あるイベント発生をきっかけに大量のスレッドが一斉に実行開始され限られたリソースに群がる様子から来ている。
*3:wikipedia:en:Lock convoyも参照。直訳すると「ロック護送船団」。単一ミューテックスのロック獲得/解放によって実行スレッドが順番に連なる様子から来ている。