MT-safe queue/Dead-lock senario

mt_queue_deadlock1.cpp

//
// Dead-lock senario under wrong implementation (capacity == 1)
//
// Precondition:
//   1-Procuder thread(P1) and 2-Consumer threads(C1,C2)
//   Thread status = Running->Blocked->Waiting->Running
//
// Step:
//   (queue q_ is empty)
//   C1: call pop() and blocked at cv_.wait()  [C1: Running->Blocked]
//   C2: call pop() and blocked at cv_.wait()  [C2: Running->Blocked]
//   P1: 1st push() and signal to C1           [C1: Blocked->Waiting]
//   (queue q_ is full)
//   P1: 2nd push() and blocked at cv_.wait()  [P1: Running->Blocked]
//   C1: return from cv_.wait(),               [C1: Waiting->Running]
//       and signal to *C2*                    [C2: Blocked->Waiting]
//   (queue q_ is empty)
//   C2: return from cv_.wait(),               [C2: Waiting->Running]
//       and re-blocked at cv_.wait()          [C2: Running->Blocked]
//
// Postcondition:
//   P1 are Blocked in push(), despite queue is not full... DEAD-LOCK.
//
class mt_queue {
  static const int capacity = 1;
  std::queue<int> q_;
  std::mutex mtx_;
  std::condition_variable cv_;
public:
  void push(int data)
  {
    std::unique_lock<std::mutex> lk(mtx_);    
    cv_.wait(lk, [&]{
      return (q_.size() < capacity);
    });
    q_.push(data);
    cv_.notify_one();  // ??
  }
  int pop()
  {
    std::unique_lock<std::mutex> lk(mtx_);
    cv_.wait(lk, [&]{
      return !q_.empty();
    });
    int data = q_.front();
    q_.pop();
    cv_.notify_one();  // ??
    return data;
  }
};

//
// Dead-lock senario under wrong implementation (capacity == 2)
//
// Precondition:
//   1-Procuder thread(P1) and 4-Consumer threads(C1...C4)
//   Thread status = Running->Blocked->Waiting->Running
//
// Step:
//   (queue q_ is empty)
//   C1: call pop() and blocked at cv_.wait()  [C1: Running->Blocked]
//   C2: call pop() and blocked at cv_.wait()  [C2: Running->Blocked]
//   C3: call pop() and blocked at cv_.wait()  [C3: Running->Blocked]
//   C4: call pop() and blocked at cv_.wait()  [C4: Running->Blocked]
//   P1: 1st push() and signal to C1           [C1: Blocked->Waiting]
//   P1: 2nd push() and signal to C2           [C2: Blocked->Waiting]
//   (queue q_ is full)
//   P1: 3rd push() and blocked at cv_.wait()  [P1: Running->Blocked]
//   C1: return from cv_.wait(),               [C1: Waiting->Running]
//       and signal to *C3*                    [C3: Blocked->Waiting]
//   C2: return from cv_.wait(),               [C2: Waiting->Running]
//       and signal to *C4*                    [C4: Blocked->Waiting]
//   (queue q_ is empty)
//   C3: return from cv_.wait(),               [C3: Waiting->Running]
//       and re-blocked at cv_.wait()          [C3: Running->Blocked]
//   C4: return from cv_.wait(),               [C4: Waiting->Running]
//       and re-blocked at cv_.wait()          [C4: Running->Blocked]
//
// Postcondition:
//   P1 are Blocked in push(), despite queue is not full... DEAD-LOCK.
//