Detection of Potential Deadlock
by John Mount

Listing One
#ifndef Synchronizer_h_included
#define Synchronizer_h_included

typedef pthread_t threadId;
typedef int synchronizerId;

class Synchronizer {
public:
  Synchronizer();
  virtual ~Synchronizer();
  virtual void acquire();
  virtual void release();
private:
  pthread_mutex_t M;
  // deliberately not implemented
  Synchronizer(const Synchronizer &);
  Synchronizer &operator=(const Synchronizer &);
};
class instrumentedSynchronizer : public Synchronizer {
public:
  instrumentedSynchronizer();
  ~instrumentedSynchronizer();
  void acquire();
  void release();
private:
  synchronizerId myid;
  // deliberately not implemented
  instrumentedSynchronizer(const instrumentedSynchronizer &);
  instrumentedSynchronizer &operator=(const instrumentedSynchronizer &);
};
extern threadId CurThreadId();
extern bool havePotentialDeadlock();
#endif

Listing Two
#include <map>
#include <set>
#include <vector>
using std::map;
using std::set;
using std::vector;

#include <iostream.h>
#include <pthread.h>
#include <sys/types.h>

#include "incidenceMap.h"
#include "Synchronizer.h"

Synchronizer::Synchronizer() {
  pthread_mutex_init(&M,NULL);
}
Synchronizer::~Synchronizer() {
  pthread_mutex_destroy(&M);
}
void Synchronizer::acquire() {
  pthread_mutex_lock(&M);
}
void Synchronizer::release() {
  pthread_mutex_unlock(&M);
}
threadId CurThreadId() {
  pthread_self();
}
class LockMonitor : private Synchronizer {
public:
  LockMonitor() {
    nextId = 1;
  };
  bool isAcyclic() {
    acquire();
    bool rv = priorSyncMap.isAcyclic();
    release();
    return rv;
  };
  int assignId() {
    acquire();
    int rv = nextId++;
    release();
    return rv;
  };
  void observeAcquireAttempt(synchronizerId sid, threadId t) {
    acquire();
    if(!syncOwnedBy.isPair(sid,t)) {
      vector<synchronizerId> *u = syncOwnedBy.left(t);
      if(u!=NULL) {
        for(unsigned int i = 0;i<u->size();++i) {
          priorSyncMap.insertPair(sid,(*u)[i]);
        }
        delete u;
      }
      syncOwnedBy.insertPair(sid,t);
    }
    release();
  };
  void observeRelease(synchronizerId sid, threadId t) {
    acquire();
    syncOwnedBy.erasePair(sid,t);
    release();
  };
private:
  directedGraph<synchronizerId> priorSyncMap;
  synchronizerId nextId;
  incidenceMap<synchronizerId,threadId> syncOwnedBy;
  // deliberately not implemented
  LockMonitor(const LockMonitor &);
  const LockMonitor &operator=(const LockMonitor &);
};
// Singleton pattern (guarantees initialization order). Assumes this is called
// before we have gone multithreaded, so there is no race condition on new-
// command. Deliberately leak monitor on heap, so it outlasts non-heap objects
static LockMonitor *GlobalLockMonitor() {
  static LockMonitor *GLM = NULL;
  if(GLM==NULL) {
    GLM = new LockMonitor;
  }
  return GLM;
}
bool havePotentialDeadlock() {
  return !GlobalLockMonitor()->isAcyclic();
}
instrumentedSynchronizer::instrumentedSynchronizer() {
  myid = GlobalLockMonitor()->assignId();
}
instrumentedSynchronizer::~instrumentedSynchronizer() {
}
void instrumentedSynchronizer::acquire() {
  threadId t = CurThreadId();
  GlobalLockMonitor()->observeAcquireAttempt(myid,t);
  Synchronizer::acquire();
}
void instrumentedSynchronizer::release() {
  threadId t = CurThreadId();
  GlobalLockMonitor()->observeRelease(myid,t);
  Synchronizer::release();
}

Listing Three
#include <iostream.h>
#include <pthread.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include "Synchronizer.h"

static void dumpstat() {
  if(havePotentialDeadlock()) {
    cout << "see potential deadlock\n";
  } else {
    cout << "do not see potential deadlock\n";
  }
}
// These are created before main is entered, guaranteeing that
// the global monitor is built before we create new threads.
static instrumentedSynchronizer a,b,c;
static void *R1(void *) {
  cout << "R1 Thread " << CurThreadId() << " try a.acquire();\n";
  a.acquire();
  cout << "R1 Thread " << CurThreadId() << " try b.acquire();\n";
  b.acquire();
  sleep(2);
  cout << "R1 Thread " << CurThreadId() << " try a.release();\n";
  a.release();
  cout << "R1 Thread " << CurThreadId() << " try b.release();\n";
  b.release();
  return NULL;
}
static void *R2(void *) {
  sleep(1);
  cout << "R2 Thread " << CurThreadId() << " try b.acquire();\n";
  b.acquire();
  cout << "R2 Thread " << CurThreadId() << " try c.acquire();\n";
  c.acquire();
  cout << "R2 Thread " << CurThreadId() << " try c.release();\n";
  c.release();
  cout << "R2 Thread " << CurThreadId() << " try b.release();\n";
  b.release();
  return NULL;
}
static void *R3(void *) {
  sleep(1);
  cout << "R3 Thread " << CurThreadId() << " try a.acquire();\n";
  a.acquire();
  cout << "R3 Thread " << CurThreadId() << " try c.acquire();\n";
  c.acquire();
  cout << "R3 Thread " << CurThreadId() << " try c.release();\n";
  c.release();
  cout << "R3 Thread " << CurThreadId() << " try a.release();\n";
  a.release();
  return NULL;
}
static void *R4(void *) {
  sleep(3);
  cout << "R4 Thread " << CurThreadId() << " try c.acquire();\n";
  c.acquire();
  cout << "R4 Thread " << CurThreadId() << " try a.acquire();\n";
  a.acquire();
  cout << "R4 Thread " << CurThreadId() << " try c.release();\n";
  c.release();
  cout << "R4 Thread " << CurThreadId() << " try a.release();\n";
  a.release();
  return NULL;
}
int main(int argc, char *argv[]) {
  bool fail = (argc>1);
  pthread_t T1,T2,TX;
  pthread_create(&T1,NULL,R1,NULL);
  pthread_create(&T2,NULL,R2,NULL);
  if(!fail) {
    pthread_create(&TX,NULL,R3,NULL);
  } else {
    pthread_create(&TX,NULL,R4,NULL);
  }
  sleep(5);
  dumpstat();
  return 0;
}



Example 1: 
R1 Thread 1026 try a->acquire();
R1 Thread 1026 try b->acquire();
R2 Thread 2051 try b->acquire();
R3 Thread 3076 try a->acquire();
R1 Thread 1026 try a->release();
R1 Thread 1026 try b->release();
R2 Thread 2051 try c->acquire();
R2 Thread 2051 try c->release();
R2 Thread 2051 try b->release();
R3 Thread 3076 try c->acquire();
R3 Thread 3076 try c->release();
R3 Thread 3076 try a->release();
do not see potential deadlock

Example 2 
R1 Thread 1026 try a->acquire();
R1 Thread 1026 try b->acquire();
R2 Thread 2051 try b->acquire();
R1 Thread 1026 try a->release();
R1 Thread 1026 try b->release();
R2 Thread 2051 try c->acquire();
R2 Thread 2051 try c->release();
R2 Thread 2051 try b->release();
R4 Thread 3076 try c->acquire();
R4 Thread 3076 try a->acquire();
R4 Thread 3076 try c->release();
R4 Thread 3076 try a->release();
see potential deadlock



5