条件変数とデッドロック・パズル（出題編）

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

スレッド間の非同期データ送受信機構mt_slot<T>として*1、C++11標準ライブラリによる下記実装を考える。

• スレッド間でT型の単一データを保持／取得するクラス。putで設定値を保持し、getで値を取得する。
• データ未保持状態でgetを呼び出すと、別スレッドがputするまでブロッキングする。
• データ保持状態でputを呼び出すと、別スレッドがgetするまでブロッキングする。

// mt_slot実装
#include <utility>
#include <mutex>
#include <condition_variable>

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_);
    while (hold_)
      cv_.wait(lk);
    slot_ = std::move(data);
    hold_ = true;
    cv_.notify_one();
  }
  T get() {
    Lock lk(mtx_);
    while (!hold_)
      cv_.wait(lk);
    cv_.notify_one();
    hold_ = false;
    return std::move(slot_);
  }
};

mt_slotクラスは、生産者−消費者問題(Producer-Consumer problem)の同期機構として利用できる。この設計パターンでは、生産者スレッドでデータのputを順次行い、消費者スレッドはデータをgetし続けることになる。

問題：

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

実行可能コード：https://gist.github.com/yohhoy/191757eaa0fe8dfa39e8 （C++11版, Pthreads版）

解答編 → id:yohhoy:20140930

*1:最大要素数が1のスレッドセーフ・キューとみなせる。