Deadlock detection

deadlock-detection.cc

#include <cassert>
#include <condition_variable>
#include <iostream>
#include <mutex>
#include <thread>

using namespace std;

condition_variable tester;
mutex sync0, sync1, a, b, graph_sync;
bool graph_updated;
int biparte_graph[2][2];

// deadlock is definitely reached therefore there's no need to update graph with the released state
void request(int p, int r) {
  {
    lock_guard<mutex> lock(graph_sync);
    biparte_graph[p][r] = 1;
    graph_updated = true;
  }
  tester.notify_all();
}
void occupy(int p, int r) {
  {
    lock_guard<mutex> lock(graph_sync);
    biparte_graph[p][r] = 2;
    graph_updated = true;
  }
  tester.notify_all();
}

void worker0() {
  cout << "Worker 0 is attempting to lock A.\n";
  request(0, 0);
  lock_guard<mutex> guard_a(a);
  cout << "Worker 0 locks A.\n";
  occupy(0, 0);
  sync0.unlock();
  lock_guard<mutex> guard1(sync1);
  cout << "Worker 0 is attempting to lock B.\n";
  request(0, 1);
  lock_guard<mutex> guard_b(b);
  assert(false);  // cout << "Worker 0 locks B and enters critical area.\n";
}

void worker1() {
  lock_guard<mutex> guard0(sync0);
  cout << "Worker 1 is attempting to lock B.\n";
  request(1, 1);
  lock_guard<mutex> guard_b(b);
  cout << "Worker 1 locks B.\n";
  occupy(1, 1);
  sync1.unlock();
  cout << "Worker 1 is attempting to lock A.\n";
  request(1, 0);
  lock_guard<mutex> guard_a(a);
  assert(false);  // cout << "Worker 1 locks A and enters critical area.\n";
}

int main() {
  sync0.lock();
  sync1.lock();
  thread thread0(worker0), thread1(worker1);
  for (;;) {
    cout << "Detecting deadlock...\n";
    {
      lock_guard<mutex> lock(graph_sync);
      if (biparte_graph[0][0] == 2 && biparte_graph[0][1] == 1 &&
          biparte_graph[1][1] == 2 && biparte_graph[1][0] == 1) { // a simplified version for detecting loops
        cout << "Deadlock detected. Terminating...\n";
        terminate();
      } else cout << "No deadlock detected.\n";
      graph_updated = false;
    }
    unique_lock<mutex> lock(graph_sync);
    tester.wait(lock, [] { return graph_updated; });
  }
  assert(false);  // this line is never reached
}