yohhoyの日記

2014-09-30

条件変数とデッドロック・パズル(解答編)

条件変数(condition variable)同期プリミティブの利用に関して、不適切な単一スレッド通知処理の使用によるデッドロック(dead lock)発生についてメモ。(条件変数 Step-by-Step入門のおまけ記事)

問題:

  • 1生産者スレッド−1消費者スレッドのとき、mt_slotクラス内でデッドロックを引き起こす可能性はあるか?
  • 2生産者スレッド−2消費者スレッドではどうか?デッドロックの可能性があるならば、どのような実行が行われた時か?

実行可能コード:https://gist.github.com/yohhoy/191757eaa0fe8dfa39e8C++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)を表す。太字表記は該当ステップにて状態変化したことを表す。

#C1C2P1P2hold_mtx_備考
0 falsen/a初期状態
1L6 -C1
2L7 falseC1
3L8 -n/aC1はcv通知を待機
4cv L6 -C2
5cv L7 falseC2
6cv L8 -n/aC2はcv通知を待機
7cv cv L1 -P1
8cv cv L2 falseP1
9mtxcvL4 trueP1P1通知→C1/C2のうちC1受信、ロック獲得待ちに遷移
10mtxcv L5 -n/a
11mtxcv L1-P2C1/P2のうちP2がロック獲得に成功
12mtxcv L2trueP2
13mtxcv L3-n/aP2はcv通知を待機
14L8 cv cv-C1C1がロック獲得しcv待機から制御を戻す
15L7 cv cvtrueC1
16L9 mtx cv-C1C1通知→C2/P2のうちC2受信、ロック獲得待ちに遷移
17L10mtx cvfalsen/a
18 L8 cv-C2C2がロック獲得しcv待機から制御を戻す
19 L7 cvfalseC2
20 L8 cv-n/aC2はcv通知を待機
21 cv cvfalsen/aC2,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

条件変数によるデッドロック状態のリスク

このようなnotify_all()からnotify_one()への書き換えは、i)通知先が最大で1スレッド かつ ii)通知を受信するスレッドの待機条件を常に満たす場合 にのみ安全に行えます。(中略) 特に条件ii)を正しく考慮していないと、デッドロックといった並行性バグの原因となるため十分注意してください。

条件変数 Step-by-Step入門 - yohhoyの日記(別館)

条件変数の不適切な通知/待機による“デッドロック状態”は、ミューテックス(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では、その原因解析およびコード修正は困難を極める。

(本記事では修正コードまで提示しない。対応策は主記事参照。)

*1:複数ミューテックスのロック順不整合によるデッドロックとは性質が異なるため、本文中では“デッドロック状態”と表記する。詳細は記事後半で説明する。

*2:mt_slotクラス外部仕様のスレッド安全性に関して、非常に注意深くドキュメンテーションを行うという対応もありえる。ただし、並行性バグの発生リスクをクラス利用者に転嫁しているだけであり、汎用クラスライブラリとしては好ましくないであろう。

*3wikipedia:ja:特異なバグ

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/yohhoy/20140930/p1
リンク元