条件変数(condition variable)同期プリミティブの利用に関して、不適切な単一スレッド通知notify_oneの使用によるデッドロック(dead lock)発生についてメモ。（条件変数 Step-by-Step入門のおまけ記事）
問題：
- 1生産者スレッド−1消費者スレッドのとき、
mt_slotクラス内でデッドロックを引き起こす可能性はあるか？- 2生産者スレッド−2消費者スレッドではどうか？デッドロックの可能性があるならば、どのような実行が行われた時か？
実行可能コード：https://gist.github.com/yohhoy/191757eaa0fe8dfa39e8 （C++11版, Pthreads版）
条件変数とデッドロック・パズル（出題編）
動作解析と説明のために、実行ライン識別ラベルL1〜L10を付与する。なお生産者スレッドはputのみを、消費者スレッドはgetのみを呼び出す。
template<typename T> class mt_slot { T slot_; bool hold_ = false; std::mutex mtx_; std::condition_variable cv_; typedef std::unique_lock<std::mutex> Lock; public: void put(T data) { Lock lk(mtx_); // L1 while (hold_) // L2 cv_.wait(lk); // L3 slot_ = std::move(data); hold_ = true; cv_.notify_one(); // L4 } // L5 T get() { Lock lk(mtx_); // L6 while (!hold_) // L7 cv_.wait(lk); // L8 cv_.notify_one(); // L9 hold_ = false; return std::move(slot_); } // L10 };
デッドロックへの路
「2生産者スレッド−2消費者スレッド」のとき、上記mt_slotクラス実装ではデッドロック状態*1に陥る可能性がある。
デッドロック状態となるまでの実行ステップ例を下表に示す。最左列は説明用のステップ番号を、C1/C2/P1/P2列は各スレッドの実行ライン(Ln)または待機中の同期オブジェクト(cv, mtx)を表す。hold列は同変数の値(下線=値の参照)を、mtx列はロック所有権保持スレッドまたは未ロック状態(n/a)を表す。太字表記は該当ステップにて状態変化したことを表す。
| # | C1 | C2 | P1 | P2 | hold | mtx | 備考 |
|---|---|---|---|---|---|---|---|
| 0 | false | n/a | 初期状態 | ||||
| 1 | L6 | - | C1 | ||||
| 2 | L7 | false | C1 | ||||
| 3 | L8 | - | n/a | C1はcv通知を待機 | |||
| 4 | cv | L6 | - | C2 | |||
| 5 | cv | L7 | false | C2 | |||
| 6 | cv | L8 | - | n/a | C2はcv通知を待機 | ||
| 7 | cv | cv | L1 | - | P1 | ||
| 8 | cv | cv | L2 | false | P1 | ||
| 9 | mtx | cv | L4 | true | P1 | P1通知→C1/C2のうちC1受信、ロック獲得待ちに遷移 | |
| 10 | mtx | cv | L5 | - | n/a | ||
| 11 | mtx | cv | L1 | - | P2 | C1/P2のうちP2がロック獲得に成功 | |
| 12 | mtx | cv | L2 | true | P2 | ||
| 13 | mtx | cv | L3 | - | n/a | P2はcv通知を待機 | |
| 14 | L8 | cv | cv | - | C1 | C1がロック獲得しcv待機から制御を戻す | |
| 15 | L7 | cv | cv | true | C1 | ||
| 16 | L9 | mtx | cv | - | C1 | C1通知→C2/P2のうちC2受信、ロック獲得待ちに遷移 | |
| 17 | L10 | mtx | cv | false | n/a | ||
| 18 | L8 | cv | - | C2 | C2がロック獲得しcv待機から制御を戻す | ||
| 19 | L7 | cv | false | C2 | |||
| 20 | L8 | cv | - | n/a | C2はcv通知を待機 | ||
| 21 | cv | cv | false | n/a | C2,P2両方でcv通知待ち |
最終状態#21では、生産／消費側の両スレッド(C2, P2)ともに条件変数に対して互いに待機状態となっており、全体処理をこれ以上進行できないデッドロック状態となっている。値を未保持(hold_==false)で進行停止しているため、消費者→生産者への通知／待機解除が正しく機能しなかったことを意味する。これはステップ#16にて、消費者スレッド(C1)からのcv通知を生産者スレッド(P2)ではなく、同じ消費者スレッド(C2)が受信したことが直接原因である。
さらに、1生産者スレッド−2消費者スレッド条件を考えた場合、前掲の実行ステップ例示でP1, P2を同一スレッドと見なせば、これもやはりデッドロック状態に陥る。またput/getの状況を反転すると、2生産者スレッド−1消費者スレッド条件でも同様にデッドロック状態に陥る実行パスが存在する。
「1生産者スレッド−1消費者スレッド(Single-Producer/Single-Consumer)」の場合でのみ、他に通知受信する候補スレッドが存在しないため、L4, L9の通知notify_oneを必ず対向スレッドが受信することになり、デッドロック状態に陥ることは決してない。つまり問題のmt_slotクラス実装では、生産者／消費者スレッドが各1個づつ以外の利用パターンに対して安全でない。*2
条件変数によるデッドロック状態のリスク
このような
条件変数 Step-by-Step入門 - yohhoyの日記（別館）notify_allからnotify_oneへの書き換えは、i) 通知先が最大で1スレッド かつ ii) 通知を受信するスレッドの待機条件を常に満たす場合 にのみ安全に行えます。（中略） 特に条件 ii) を正しく考慮していないと、デッドロックといった並行性バグの原因となるため十分注意してください。
条件変数の不適切な通知／待機による “デッドロック状態” は、ミューテックス(mutex)ロックで引き起こされる単純なデッドロック（下記コード例示）とは性質が異なる。
// BUG: デッドロック可能性のあるコード例 std::mutex m1, m2; typedef std::unique_lock<std::mutex> Lock; void thread1() { Lock lk1(m1), lk2(m2); //... } void thread2() { Lock lk2(m2), lk1(m1); //... }
ミューテックスにより引き起こされる通常のデッドロックでは、事象発生後に当事スレッド進行が再開されることは決してない。一方、条件変数により引き起こされたデッドロック状態では、1) 第3スレッドによるcv通知を受信して待機状態から復帰する、2) Spurious Wakeup発生により待機状態から復帰する（→id:yohhoy:20120326）といった、外部要因によって偶発的に当事スレッド進行が再開することもある。
このようなデッドロック状態からの復旧可能性は決して望ましい特性ではなく、むしろ再現率が悪く検出困難な並行性バグとして潜在化するリスク要因となる。これらは、原因不明の動作スループット低下や処理ストール(stall; 停止)といった不具合を引き起こすであろう。このような並行性バグ*3では、その原因解析およびコード修正は困難を極める。
（本記事では修正コードまで提示しない。対応策は主記事参照。）
